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,2

Comments

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

Links

Table of n, a(n) for n=0..50.

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

Example

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

Prog

(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

Crossrefs

Cf. A123552.

Sequence in context: A074715 A325350 A027585 * A005434 A027589 A039851

Adjacent sequences: A123012 A123013 A123014 * A123016 A123017 A123018

Keyword

nonn,easy

Author

Simon Strandgaard, Nov 12 2006

Status

approved