[seqfan] Re: A002094 from 1875 needs more terms

[Sascha Kurz]

Via Polya's method I got
2, 5, 10, 25, 56, 139, 338, 852, 2145, 5513, 14196, 36962, 96641, 254279, 
671640, 1781840, 4742295, 12662282, 33898923, 90981264, 244720490,
659591378, 1781048728, 4817420360, 13050525328, 35405239155, 96180222540,
261603173201, 712364210543, 1941916439374, 5299055085732, 14473680632265,
39568320566768, 108263489215149, 296456994986748, 812396235518147,
2227836596224839, 6113530314272249, 16787243216291347, 46124496243759499,
126804940153648061, 348803817717911513, 959965987872231310, ...

Let A(x) denote A000598 (Number of rooted ternary trees with n nodes),
i.e., A(x) = 1+(1/6)*x*(A(x)^3+3*A(x)*A(x^2)+2*A(x^3)), and set
B(x)=(A(x)^2+A(x^2))/2. With D_k(x) being the cycle polynomial of the
regular k-gon for k>=2, the final generating function is then given by
sum_{k>=2} x^k*D_k(B(x)), which can be evaluated very quickly and, of
course, coincides with the terms stated below.

ATB Sascha


> I get by explicit computation
>
> 2, 5, 10, 25, 56, 139, 338, 852, 2145, 5513, 14196, 36962, 96641, 254279,
> 671640, 1781840
>
> Computed by using nauty to generate trees of maximum degree 4, then either
> adding one edge making a multigraph or one edge to make a cycle.  This
> matches the more extensive set of terms computed by R. J. Mathar.
>
> Sean.