Sub-Fibonacci Tree

Paul D. Hanna pauldhanna at juno.com
Fri Nov 17 07:13:46 CET 2006


Seqfans, 
     Consider the following "sub-Fibonacci tree" and in particular 
its associated sequence defined by: 
 
Sum of labels of nodes in generation n of a rooted tree in which a node 
with label k has child nodes assigned labels of successive integers 
beginning with k+1 such that the number of child nodes for each node 
is given by the label of the parent node, starting at generation n=0 
with a root node with label '1' followed by a child node with label '2'. 
 
(Perhaps someone could make this description more concise?!)
 
EXAMPLE.
The initial nodes of the tree for generations 0..5 are: 
gen 0: [1];
gen 1: [2];
gen 2: [3];
gen 3: [4,5];
gen 4: (4)->[5,6,7],(5)->[6,7,8];
gen 5: (5)->[6,7,8,9],(6)->[7,8,9,10],(7)->[8,9,10,11], 
(6)->[7,8,9,10,11],(7)->[8,9,10,11,12],(8)->[9,10,11,12,13];
  
By definition, there are 2 child nodes for node [3] since 
the parent of node [3] is [2]; likewise, 
there are 3 child nodes for nodes [4] and [5] (in gen.3) 
since the parent of both nodes has label [3] (in gen.2). 
 
Notice the minimum label in generation n is n+1, and 
the maximum label in generation n is Fibonacci(n+2).  
  
 From this tree I am interested in gleaning 2 sequences. 
  
SEQUENCE 1. 
I compute the number of nodes in generation n to begin: 
[1, 1, 1, 2, 6, 27, 177, 1680, 23009, 455368, ...]
 
which is equal (with offset) to A005270:
"Sub-Fibonacci sequences of length n."
1, 1, 1, 1, 2, 6, 27, 177, 1680, 23009, 455368 
 
SEQUENCE 2. 
But the following related sequence is NOT found in the OEIS: 
 
Sum of labels of nodes in generation n:
[1, 2, 3, 9, 39, 252, 2361, 32077, 631058, ...]
 
EXTENSION?
Could someone compute more terms of sequences 1 and 2? 
 
Thanks,
    Paul






More information about the SeqFan mailing list