Complete k-ary trees and generalized meta-Fibonacci sequences

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 sequ...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics and theoretical computer science 2006-01, Vol.DMTCS Proceedings vol. AG,... (Proceedings), p.203-214
Main Authors: Deugau, Chris, Ruskey, Frank
Format: Article
Language:English
Subjects:
[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
[info.info-ds] computer science [cs]/data structures and algorithms [cs.ds]
[info.info-hc] computer science [cs]/human-computer interaction [cs.hc]
[math.math-co] mathematics [math]/combinatorics [math.co]
Combinatorics
Computer Science
Data Structures and Algorithms
Discrete Mathematics
generating function
Human-Computer Interaction
k-ary tree
Mathematics
meta-fibonacci sequence
recurrence relation
ruler function
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1365-8050
1462-7264
1365-8050
DOI:10.46298/dmtcs.3514