This paper is concerned with a family of
![$k$](img1.gif)
-ary meta-Fibonacci sequences
described by the recurrence relation
where
![$s$](img3.gif)
may be any integer, positive or negative.
If
![$s \ge 0$](img4.gif)
, then the initial conditions are
![$a(n) = 1$](img5.gif)
for
![$1 \le n \le s+1$](img6.gif)
and
![$a(n) = n-s$](img7.gif)
for
![$s+1 < n \le s+k$](img8.gif)
.
If
![$s \le 0$](img9.gif)
, then the initial conditions are
![$a(n) = n$](img10.gif)
for
![$1 \le n \le k(-s+1)$](img11.gif)
.
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$](img1.gif)
-ary trees, and (for
![$s \ge 0$](img4.gif)
)
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$](img12.gif)
).
We also show that these sequences are related to a
``self-describing" sequence of Cloitre and Sloane.