0,3

Take the complete binary tree with n labeled nodes. Here is a poor picture of the tree with 6 nodes:

.......R

...../...\

..../.....\

...o.......o

../.\...../

.o...o...o

Then the number of rooted subtrees of the graph is a(n).

A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fib. Quart., 11 (1973), 429-437.

Index entries for sequences related to rooted trees

a(0) = 0, a(1) = 1

a(n) = 1 + a(floor((n-1)/2) + a(ceiling((n-1)/2) + a(floor((n-1)/2)*a(ceiling((n-1)/2) = (1+a(floor((n-1)/2))*(1+a(ceiling((n-1)/2))

If b(n) is sequence A005468, then a(n)=b(n+1)-1. From the definition of A005468, a(n) = b(floor((n+1)/2)*b(ceiling((n+1)/2). So for every odd n a(n) is a square: a(2n-1)=b(n)^2.

If c(n) is sequence A004019, then c(n)=a(2^n-1).

A004019 (and Aho and Sloane) give a closed formula for c(n) that translates to a(n) = nearest integer to b^((n+1)/2) - 1" where b = 2.25851...; the formula gives the asymptotic behavior of this sequence, however it does not compute the correct values for a(n) unless n+1 is a power of two.

For example, for n = 3 the a(3) = 4 subtrees are:

R...R...R......R

.../.....\..../.\

..o.......o..o...o

Cf. A004019, A005468

Sequence in context: A127740 A024787 A076922 this_sequence A057602 A006498 A074677

Adjacent sequences: A157676 A157677 A157678 this_sequence A157680 A157681 A157682

easy,nice,nonn

Paolo Bonzini (bonzini(AT)gnu.org), Mar 04 2009, Mar 09 2009