|
%I #16 Mar 03 2020 09:58:10
%S 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,
%T 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,
%U 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
%N 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'.
%C 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).
%H Alois P. Heinz, <a href="/A125051/b125051.txt">Table of n, a(n) for n = 0..24903</a> (generations 0..8)
%H Peter C. Fishburn and Fred S. Roberts, <a href="https://doi.org/10.1016/0166-218X(93)90236-H">Elementary sequences, sub-Fibonacci sequences</a>, Discrete Appl. Math. 44 (1993), no. 1-3, 261-281.
%e The initial nodes of the tree for generations 0..5 are:
%e gen.0: [1];
%e gen.1: [2];
%e gen.2: [3];
%e gen.3: [4,5];
%e gen.4: (4)->[5,6,7],(5)->[6,7,8];
%e gen.5: (5)->[6,7,8,9],(6)->[7,8,9,10],(7)->[8,9,10,11],
%e (6)->[7,8,9,10,11],(7)->[8,9,10,11,12],(8)->[9,10,11,12,13].
%e By definition, there are 2 child nodes for node [3] of gen.2 since the parent of node [3] has label 2;
%e likewise, there are 3 child nodes for nodes [4] and [5] of gen.3 since the parent of both nodes has label 3.
%e The number of nodes in generation n begins:
%e 1, 1, 1, 2, 6, 27, 177, 1680, 23009, 455368, 13067353, ...
%e The sum of the labels for nodes in generation n begins:
%e 1, 2, 3, 9, 39, 252, 2361, 32077, 631058, 18035534, ...
%p g:= proc(n) option remember; `if`(n=0, [[1, 1]],
%p map(x-> seq([x[2], x[2]+i], i=1..x[1]), g(n-1)))
%p end:
%p T:= n-> map(x-> x[2], g(n)):
%p a:= proc() local i, l; i, l:= -1, []; proc(n) while
%p nops(l)<=n do i:=i+1; l:=[l[], T(i)[]] od; l[n+1] end
%p end():
%p seq(a(n), n=0..200); # _Alois P. Heinz_, Feb 08 2013
%Y Cf. A005270, A125052.
%K nonn,look
%O 0,2
%A _Paul D. Hanna_, Nov 19 2006
|
