##
The Combinatorics of Certain k-ary Meta-Fibonacci Sequences

*Frank Ruskey*,
Department of Computer Science,
University of Victoria, Canada.

*Chris Deugau*,
Department of Computer Science,
University of Victoria, Canada.

### Abstract:

This paper is concerned with a family of *k*-ary meta-Fibonacci sequences
described by the recurrence relation
*a*(*n*) = SUM( *a*( *n-i-s-a*( *n-i* )), i=1..k ),

where *s* may be any integer, positive or negative.
If *s *__>__ 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* __<__
*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.

Back to list of publications.