help needed counting rooted trees

[Henry in Rotherhithe]

> -----Original Message-----
> From: Max
> Sent: 30 August 2005 23:34
> To: njas at research.att.com
> Cc: seqfan at ext.jussieu.fr
> Subject: Re: help needed counting rooted trees
>
>
> 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.

Note that it is also essentially A003095-1 and A056207+1, both of which
refer to binary trees

So it can be approximated by b^(2^n)-1 where b is
1.50283680104975649975293642373216940873887174396357930699... in the
original and 2.25851845058946539883779624006373187243427469718511465966...
with the changed offset.

Henry Bottomley
--
No virus found in this outgoing message.
Checked by AVG Anti-Virus.
Version: 7.0.344 / Virus Database: 267.10.17/85 - Release Date: 30/08/2005