A combinatorial interpretation for certain relatives of the Conolly sequence
Journal of integer sequences, Tome 11 (2008) no. 2
For any integer $s\geq0$, 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)), 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.
@article{JIS_2008__11_2_a3,
author = {Balamohan, B. and Li, Zhiqiang and Tanny, Stephen},
title = {A combinatorial interpretation for certain relatives of the {Conolly} sequence},
journal = {Journal of integer sequences},
year = {2008},
volume = {11},
number = {2},
zbl = {1148.05005},
language = {en},
url = {http://geodesic.mathdoc.fr/item/JIS_2008__11_2_a3/}
}
Balamohan, B.; Li, Zhiqiang; Tanny, Stephen. A combinatorial interpretation for certain relatives of the Conolly sequence. Journal of integer sequences, Tome 11 (2008) no. 2. http://geodesic.mathdoc.fr/item/JIS_2008__11_2_a3/