%I A004019 M3611
%S A004019 0,1,4,25,676,458329,210066388900,44127887745906175987801,
%T A004019 1947270476915296449559703445493848930452791204,
%U A004019 3791862310265926082868235028027893277370233152247388584761734150717768254410341175325352025
%N A004019 a(0) = 0; for n>0, a(n) = (a(n-1) + 1)^2.
%C A004019 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:
%C A004019 .......R
%C A004019 ...../...\
%C A004019 ..../.....\
%C A004019 ...o.......o
%C A004019 ../.\...../.\
%C A004019 .o...o...o...o
%C A004019 /.\./.\./.\./.\
%C A004019 o o o o o o o o
%C A004019 Let the number of rooted subtrees be s(n). For example, for n = 1 the 
               s(2) = 4 subtrees are:
%C A004019 R...R...R......R
%C A004019 .../.....\..../.\
%C A004019 ..o.......o..o...o
%C A004019 Then s(n+1) = 1 + 2*s(n) + s(n)^2 = (1+s(n))^2 and so s(n) = a(n+1).
%D A004019 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%H A004019 A. V. Aho and N. J. A. Sloane, <a href="http://www.research.att.com/~njas/
               doc/doubly.html">Some doubly exponential sequences</a>, Fib. Quart., 
               11 (1973), 429-437.
%H A004019 <a href="Sindx_Aa.html#AHSL">Index entries for sequences of form a(n+1)=a(n)^2 
               + ...</a>
%H A004019 <a href="Sindx_Ro.html#rooted">Index entries for sequences related to 
               rooted trees</a>
%F A004019 a(n) = A003095(n)^2 = A003095(n+1) - 1 = A056207(n+1) + 1.
%F A004019 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.
%Y A004019 Cf. A001699, A056207.
%Y A004019 Sequence in context: A167041 A123129 A075577 this_sequence A072882 A014253 
               A132553
%Y A004019 Adjacent sequences: A004016 A004017 A004018 this_sequence A004020 A004021 
               A004022
%K A004019 nonn,easy,nice
%O A004019 0,3
%A A004019 N. J. A. Sloane (njas(AT)research.att.com).
%E A004019 One more term from Henry Bottomley (se16(AT)btinternet.com), Jul 24 2000
%E A004019 Additional comments from Max Alekseyev (maxale(AT)gmail.com), Aug 30 
               2005