Journal of Integer Sequences, Vol. 11 (2008), Article 08.2.1

A Combinatorial Interpretation for Certain Relatives of the Conolly Sequence

B. Balamohan, Zhiqiang Li, and Stephen Tanny
Department of Mathematics
University of Toronto
Toronto, Ontario M5S 2E4


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.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A008619 and A109964 .)

Received January 4 2008; revised version received May 22 2008. Published in Journal of Integer Sequences, May 23 2008.

Return to Journal of Integer Sequences home page