Balamohan, B.; Li, Zhiqiang; Tanny, Stephen A combinatorial interpretation for certain relatives of the Conolly sequence. (English) Zbl 1148.05005 J. Integer Seq. 11, No. 2, Article ID 08.2.1, 13 p. (2008). 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. Cited in 3 Documents MSC: 05A15 Exact enumeration problems, generating functions 11B37 Recurrences 11B39 Fibonacci and Lucas numbers and polynomials and generalizations Keywords:meta-Fibonacci recursion; Hofstadter sequence; slowly growing sequences; ordinary generating function Software:OEIS PDFBibTeX XMLCite \textit{B. Balamohan} et al., J. Integer Seq. 11, No. 2, Article ID 08.2.1, 13 p. (2008; Zbl 1148.05005) Full Text: arXiv EuDML EMIS