Journal of Integer Sequences, Vol. 12 (2009), Article 09.4.3

The Combinatorics of Certain k-ary Meta-Fibonacci Sequences

Frank Ruskey and Chris Deugau
University of Victoria
Victoria, BC V8W3P6


This paper is concerned with a family of $k$-ary meta-Fibonacci sequences described by the recurrence relation

a(n) = \sum_{i=1}^k a(n{-}i - (s{-}1) - a(n{-}i)),

where $s$ may be any integer, positive or negative. If $s \ge 0$, then the initial conditions are $a(n) = 1$ for $1 \le n \le s+1$ and $a(n) = n-s$ for $s+1 < n \le s+k$. If $s \le 0$, then the initial conditions are $a(n) = n$ for $1 \le n \le k(-s+1)$. We show that these sequences arise as the solutions of two natural counting problems: The number of leaves at the largest level in certain infinite $k$-ary trees, and (for $s \ge 0$) certain restricted compositions of an integer. For this family of generalized meta-Fibonacci sequences and two families of related sequences we derive combinatorial bijections, ordinary generating functions, recurrence relations, and asymptotics ( $a(n) \sim n(k-1)/k$). We also show that these sequences are related to a ``self-describing" sequence of Cloitre and Sloane.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A001511 A002572 A004128 A006949 A045412 A046699 A053735 A079559 A091090 A096346 A101925 A120501 A120502 A120503 A120504 A120505 A120506 A120507 A120508 A120509 A120510 A120511 A120512 A120513 A120514 A120515 A120516 A120517 A120518 A120519 A120520 A120521 A120522 A120523 A120524 A120525 A120526 A120527 A120528 A120529 A120530 A120531 and A120532.)

Received March 24 2009; revised version received May 1 2009. Published in Journal of Integer Sequences, May 12 2009.

Return to Journal of Integer Sequences home page