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.
