A123015 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, 2, 3, 4, 6, 8, 10, 13, 17, 21, 26, 33, 41, 50, 62, 77, 94, 115, 142, 174, 212, 260, 319, 389, 475, 582, 711, 867, 1060, 1296, 1581, 1930, 2359, 2880, 3514, 4292, 5242, 6397, 7809, 9537, 11642, 14209, 17349, 21182, 25854, 31561, 38534, 47039, 57418, 70098, 85576
Offset: 0
Examples
step #0: ..1 step #1: ..2 step #2: ..3 step #3: ..3 ./ 1 step #4: ..3 ./.\ 2...1 step #5: ..3 ./.\ 3...2 step #6: ....3 .../.\ ..3...3 ./ 1 step #7: ......3 ..../...\ ..3.......3 ./.\...../ 2...1...1 step #8: ......3 ..../...\ ..3.......3 ./.\...../.\ 3...2...2...1
Crossrefs
Cf. A123552.
Programs
-
Ruby
class Node; def initialize; @n = 1; @c = [] end def count; @c.inject(@n){|n,c| n + c.count} end def grow; return @n += 1 if @n < 3; @c.each{|c| c.grow } @c << Node.new if @c.size < 2; end; end; r = []; node = Node.new 30.times { r << node.count; node.grow }; p r
Formula
a(n) = a(n-3)+a(n-4)+3. - Ralf Stephan, Nov 12 2006
G.f.: (1+x+x^2)/(1-x-x^3+x^5). - Christian G. Bower, Nov 13 2006
Comments