login
Grow a binary tree using the following rules. Initially there is a single node labeled 1. At each step we add 1 to all labels less than 3. If a node has label 3 and zero or one descendants we add a new descendant labeled 1. Sequence gives sum of all labels at step n.
1

%I #7 May 03 2020 09:14:22

%S 1,2,3,4,6,8,10,13,17,21,26,33,41,50,62,77,94,115,142,174,212,260,319,

%T 389,475,582,711,867,1060,1296,1581,1930,2359,2880,3514,4292,5242,

%U 6397,7809,9537,11642,14209,17349,21182,25854,31561,38534,47039,57418,70098,85576

%N Grow a binary tree using the following rules. Initially there is a single node labeled 1. At each step we add 1 to all labels less than 3. If a node has label 3 and zero or one descendants we add a new descendant labeled 1. Sequence gives sum of all labels at step n.

%C An analog of Fibonacci's rabbits. The behavior of the node is given by its age. A node of age 0 or 1 grows and one of age 2 or 3 produces a new node. - _Christian G. Bower_, Nov 13 2006

%F a(n) = a(n-3)+a(n-4)+3. - _Ralf Stephan_, Nov 12 2006

%F G.f.: (1+x+x^2)/(1-x-x^3+x^5). - _Christian G. Bower_, Nov 13 2006

%e step #0:

%e ..1

%e step #1:

%e ..2

%e step #2:

%e ..3

%e step #3:

%e ..3

%e ./

%e 1

%e step #4:

%e ..3

%e ./.\

%e 2...1

%e step #5:

%e ..3

%e ./.\

%e 3...2

%e step #6:

%e ....3

%e .../.\

%e ..3...3

%e ./

%e 1

%e step #7:

%e ......3

%e ..../...\

%e ..3.......3

%e ./.\...../

%e 2...1...1

%e step #8:

%e ......3

%e ..../...\

%e ..3.......3

%e ./.\...../.\

%e 3...2...2...1

%o (Ruby) class Node; def initialize; @n = 1; @c = [] end

%o def count; @c.inject(@n){|n,c| n + c.count} end

%o def grow; return @n += 1 if @n < 3; @c.each{|c| c.grow }

%o @c << Node.new if @c.size < 2; end; end; r = []; node = Node.new

%o 30.times { r << node.count; node.grow }; p r

%Y Cf. A123552.

%K nonn,easy

%O 0,2

%A _Simon Strandgaard_, Nov 12 2006