Geodesic
A combinatorial interpretation for certain relatives of the Conolly sequence
Journal of integer sequences, Tome 11 (2008) no. 2.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: 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.
Classification : 05A15
Keywords: meta-Fibonacci recursion, hofstadter sequence 
@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},
     publisher = {mathdoc},
     volume = {11},
     number = {2},
     year = {2008},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JIS_2008__11_2_a3/}
}
TY  - JOUR
AU  - Balamohan, B.
AU  - Li, Zhiqiang
AU  - Tanny, Stephen
TI  - A combinatorial interpretation for certain relatives of the Conolly sequence
JO  - Journal of integer sequences
PY  - 2008
VL  - 11
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JIS_2008__11_2_a3/
LA  - en
ID  - JIS_2008__11_2_a3
ER  - 
%0 Journal Article
%A Balamohan, B.
%A Li, Zhiqiang
%A Tanny, Stephen
%T A combinatorial interpretation for certain relatives of the Conolly sequence
%J Journal of integer sequences
%D 2008
%V 11
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JIS_2008__11_2_a3/
%G en
%F 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/