help needed counting rooted trees

[Max]

It's easy to see that the number of subtrees satisfies a recurrence:

s(n+1) = 1 + 2*s(n) + s(n)^2 = (1+s(n))^2

So the sequence is
  1 4 25 676 458329 210066388900 44127887745906175987801 1947270476915296449559703445493848930452791204

that is A004019, not A007830.

Max

N. J. A. Sloane wrote:
> 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.  
> 
>        o
>      /   \ 
>     /     \
>    o       o
>   / \     / \
>  o   o   o   o
> / \ / \ / \ / \
> o o o o o o o  o
> 
> My question is, how many rooted subtrees are there?
> (All rooted at the original root, of course.)
> 
> For n = 1 the 4 subtrees are:
> o   o   o      o
>    /     \    / \
>   o       o  o   o
> 
> I get:
> 
> n: 0  1  2
> #: 1  4  25
> 
> Is this A007830?
> 
> NJAS
> 
>