tailieunhanh - Báo cáo toán học: "Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes. | Meta-Fibonacci Sequences Binary Trees and Extremal Compact Codes Brad Jackson Dept. of Mathematics San Jose State University USA jackson@ Frank Ruskey Dept. of Computer Science University of Victoria CANADA http ruskey Submitted Jun 14 2005 Accepted Mar 13 2006 Published Mar 21 2006 Mathematics Subject Classifications 05A15 05A19 68P30 Abstract We consider a family of meta-Fibonacci sequences which arise in studying the number of leaves at the largest level in certain infinite sequences of binary trees restricted compositions of an integer and binary compact codes. For this family of meta-Fibonacci sequences and two families of related sequences we derive ordinary generating functions and recurrence relations. Included in these families of sequences are several well-known sequences in the Online Encyclopedia of Integer Sequences OEIS . 1 Introduction In a remarkable paper Emily Norwood studied the number of compact codes 7 . A compact code can be thought of as the sorted sequence of level numbers of the leaves of an extended binary tree. She provided a recurrence relation and table of the number of trees classified according to their height and their number of leaves. We will prove that if the outline of this table is considered as an increasing sequence of integers then one of the meta-fibonacci numbers arises namely the one that satisfies the recurrence relation a n a x n a n 1 a y n a n 2 with x n n 1 and y n n 2. Sequences satisfying this recurrence but with different linear functions for x n and y n have been investigated by several authors in recent years but the general behavior of these sequences remains rather mysterious . Guy 4 Problem E31 Pinn 9 . Perhaps the most well-behaved sequences in the family Research supported in part by NSERC. THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R26 1 15 25 3 7 10 18 22 Q 0 Figure 1 The tree Fo. occur when x n n and y n n 1. For a given parameter s 0 we will show that the sequences .