A000106 2nd power of rooted tree enumerator; number of linear forests of 2 rooted trees.

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

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

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

Crossrefs

Column d=1 of A335362.

Column 2 of A339067.

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

Programs

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

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

<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 *)

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

Extensions

More terms from Christian G. Bower, Nov 15 1999