Complete k-ary trees and generalized meta-Fibonacci sequences

Abstract

We show that a family of generalized meta-Fibonacci sequences arise when counting the number of leaves at the largest level in certain infinite sequences of k-ary trees and restricted compositions of an integer. For this family of generalized meta-Fibonacci sequences and two families of related sequences we derive ordinary generating functions and recurrence relations.

Keywords

• meta-fibonacci sequence
• k-ary tree
• recurrence relation
• generating function
• ruler function.
• [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds]
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
• [math.math-co] mathematics [math]/combinatorics [math.co]
• [info.info-hc] computer science [cs]/human-computer interaction [cs.hc]