×

A combinatorial interpretation for certain relatives of the Conolly sequence. (English) Zbl 1148.05005

Summary: For any integer \(s\geq 0\), we derive a combinatorial interpretation for the family of sequences generated by the recursion (parameterized by \(s\)) \[ h_s(n)=h_s(n-s-h_s(n-1))+h_s(n-2-s-h_s(n-3)),\quad n > s+3, \] with the initial conditions \(h_s(1) = h_s(2) = \cdots = h_s(s+2) = 1\) and \(h_s(s+3) = 2\). We show how these sequences count the number of leaves of a certain infinite tree structure. Using this interpretation we prove that \(h_{s}\) sequences are “slowly growing”, that is, \(h_{s}\) sequences are monotone nondecreasing, with successive terms increasing by 0 or 1, so each sequence hits every positive integer. Further, for fixed \(s\) the sequence \(h_s(n)\) hits every positive integer twice except for powers of 2, all of which are hit \(s+2\) times. Our combinatorial interpretation provides a simple approach for deriving the ordinary generating functions for these sequences.

MSC:

05A15 Exact enumeration problems, generating functions
11B37 Recurrences
11B39 Fibonacci and Lucas numbers and polynomials and generalizations

Software:

OEIS
PDFBibTeX XMLCite
Full Text: arXiv EuDML EMIS