A000106 2nd power of rooted tree enumerator; number of linear forests of 2 rooted trees. (Formerly M1415 N0553)

1, 2, 5, 12, 30, 74, 188, 478, 1235, 3214, 8450, 22370, 59676, 160140, 432237, 1172436, 3194870, 8741442, 24007045, 66154654, 182864692, 506909562, 1408854940, 3925075510, 10959698606, 30665337738, 85967279447, 241433975446, 679192039401, 1913681367936, 5399924120339

Offset

2,2

References

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 150.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

Links

Alois P. Heinz, Table of n, a(n) for n = 2..1000 (terms n = 2..200 from T. D. Noe)

Vsevolod Gubarev, Rota-Baxter operators on a sum of fields, arXiv:1811.08219 [math.RA], 2018.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 385

Index entries for sequences related to rooted trees

Formula

Self-convolution of rooted trees A000081.

a(n) ~ c * d^n / n^(3/2), where d = A051491 = 2.9557652856519949747148..., c = 0.87984802514205060808180678... . - Vaclav Kotesovec, Sep 11 2014

In the asymptotics above the constant c = 2 * A187770. - Vladimir Reshetnikov, Aug 13 2016

Maple

b:= proc(n) option remember; if n<=1 then n else add(k*b(k)* s(n-1, k), k=1..n-1)/(n-1) fi end: s:= proc(n, k) option remember; add(b(n+1-j*k), j=1..iquo(n, k)) end: B:= proc(n) option remember; add(b(k)*x^k, k=1..n) end: a:= n-> coeff(series(B(n-1)^2, x=0, n+1), x, n): seq(a(n), n=2..35); # Alois P. Heinz, Aug 21 2008

Mathematica

<<NumericalDifferentialEquationAnalysis`; btc = ButcherTreeCount[max = 30]; Flatten[ Table[ ListConvolve[t=Take[btc, n], t], {n, 1, max}]] (* Jean-François Alcover, Nov 02 2011 *)
b[n_] := b[n] = If[n <= 1, n, Sum[k*b[k]*s[n-1, k], {k, 1, n-1}]/(n-1)]; s[n_, k_] := s[n, k] = Sum[b[n+1-j*k], {j, 1, Quotient[n, k]}]; B[n_] := B[n] = Sum[b[k]*x^k, {k, 1, n}]; a[n_] := SeriesCoefficient[B[n-1]^2, {x, 0, n}]; Table[a[n], {n, 2, 35}] (* Jean-François Alcover, Dec 01 2016, after Alois P. Heinz *)

Prog

(Haskell)
a000106 n = a000106_list !! (n-2)
a000106_list = drop 2 $ conv a000081_list [] where
   conv (v:vs) ws = (sum $ zipWith (*) ws' $ reverse ws') : conv vs ws'
                    where ws' = v : ws
-- Reinhard Zumkeller, Jun 17 2013

Crossrefs

Column d=1 of A335362.

Column 2 of A339067.

Cf. A000081, A000242, A000300, A000343, A000395, A027852 (forests of 2 rooted trees).

Sequence in context: A118649 A033482 A054341 * A076883 A140832 A326793

Adjacent sequences: A000103 A000104 A000105 * A000107 A000108 A000109

Keyword

nonn,nice,easy

Author

N. J. A. Sloane

Extensions

More terms from Christian G. Bower, Nov 15 1999

Status

approved