0,3

Take the standard rooted binary tree of depth n, with 2^(n+1) - 1 labeled nodes. Here is a poor picture of the tree of depth 3:

.......R

...../...\

..../.....\

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

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

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

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

o o o o o o o o

Let the number of rooted subtrees be s(n). For example, for n = 1 the s(2) = 4 subtrees are:

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

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

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

Then s(n+1) = 1 + 2*s(n) + s(n)^2 = (1+s(n))^2, and so s(n) = a(n+1).

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

Index entries for sequences of form a(n+1)=a(n)^2 + ...

Index entries for sequences related to rooted trees

a(n) = A003095(n)^2 = A003095(n+1) - 1 = A056207(n+1) + 1.

It follows from Aho and Sloane that there is a constant c such that a(n) is the nearest integer to c^(2^n). In fact a(n+1) = nearest integer to b^(2^n) - 1 where b = 2.25851845058946539883779624006373187243427469718511465966.... - Henry Bottomley, Aug 30 2005.

Cf. A001699, A056207.

Adjacent sequences: A004016 A004017 A004018 this_sequence A004020 A004021 A004022

Sequence in context: A086216 A123129 A075577 this_sequence A072882 A014253 A132553

nonn,easy,nice

njas

One more term from Henry Bottomley (se16(AT)btinternet.com), Jul 24 2000

Additional comments from Max Alekseyev (maxal(AT)cs.ucsd.edu), Aug 30 2005