A125051 The sub-Fibonacci tree; a rooted tree in which every node with label k and parent node with label g has g child nodes that are assigned labels beginning with k+1 through k+g; the tree starts at generation n=0 with a root node labeled '1' and a child node labeled '2'.

1, 2, 3, 4, 5, 5, 6, 7, 6, 7, 8, 6, 7, 8, 9, 7, 8, 9, 10, 8, 9, 10, 11, 7, 8, 9, 10, 11, 8, 9, 10, 11, 12, 9, 10, 11, 12, 13, 7, 8, 9, 10, 11, 8, 9, 10, 11, 12, 9, 10, 11, 12, 13, 10, 11, 12, 13, 14, 8, 9, 10, 11, 12, 13, 9, 10, 11, 12, 13, 14, 10, 11, 12, 13, 14, 15, 11, 12, 13, 14, 15, 16, 9

Offset: 0

Author

Paul D. Hanna, Nov 19 2006

Keywords

• nonn
• look

Comments

The maximum label for nodes in generation n is Fibonacci(n+2) for n>=0. The total number of nodes in generation n equals A005270(n+2) for n>=0. The sum of the labels for nodes in generation n equals A125052(n).

Examples

			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] of gen.2 since the parent of node [3] has label 2;
likewise, there are 3 child nodes for nodes [4] and [5] of gen.3 since the parent of both nodes has label 3.
The number of nodes in generation n begins:
1, 1, 1, 2, 6, 27, 177, 1680, 23009, 455368, 13067353, ...
The sum of the labels for nodes in generation n begins:
1, 2, 3, 9, 39, 252, 2361, 32077, 631058, 18035534, ...
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..24903 (generations 0..8)
• Peter C. Fishburn and Fred S. Roberts, Elementary sequences, sub-Fibonacci sequences, Discrete Appl. Math. 44 (1993), no. 1-3, 261-281.

Crossrefs

Cf. A005270, A125052.

Programs

Maple

g:= proc(n) option remember; `if`(n=0, [[1, 1]],
      map(x-> seq([x[2], x[2]+i], i=1..x[1]), g(n-1)))
    end:
T:= n-> map(x-> x[2], g(n)):
a:= proc() local i, l; i, l:= -1, []; proc(n) while
      nops(l)<=n do i:=i+1; l:=[l[], T(i)[]] od; l[n+1] end
    end():
seq(a(n), n=0..200);  # Alois P. Heinz, Feb 08 2013