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).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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.

Sequence in context: A167041 A123129 A075577 this_sequence A072882 A014253 A132553

Adjacent sequences: A004016 A004017 A004018 this_sequence A004020 A004021 A004022

nonn,easy,nice

N. J. A. Sloane (njas(AT)research.att.com).

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

Additional comments from Max Alekseyev (maxale(AT)gmail.com), Aug 30 2005