A221864 Number of forests (sets) of rooted labeled trees on {1,2,...,n} such that the node with label 1 is in the same rooted tree as the node with label 2.

0, 0, 2, 11, 88, 930, 12254, 193736, 3576564, 75552560, 1797906490, 47601571968, 1388102588048, 44210926113536, 1527152437488150, 56867807937459200, 2271048787266451756, 96826981390532388864, 4389830567318703987314, 210886652765343862784000

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..200

Formula

a(n) = Sum_{k=0..n-2} C(n-2,k)*(k+2)^(k+1)*(n-k-1)^(n-k-3).

E.g.f.: Double integral of T''(x)*exp(T(x)) dx^2 where T(x) is the e.g.f. for A000169.

a(n) ~ exp(1) * n^(n-1) * (1 - sqrt(Pi/(2*n))). - Vaclav Kotesovec, Aug 31 2014

Example

a(3) = 9 + 2 = 11 because we have A000169(3) = 9 forests composed of a single rooted tree and 2 forests composed of two rooted trees:
1'-2  3,  2'-1  3 where the root is indicated with '.

Maple

a:= n-> add(binomial(n-2, k)*(k+2)^(k+1)*(n-k-1)^(n-k-3), k=0..n-2):
seq(a(n), n=0..20);  # Alois P. Heinz, Apr 11 2013

Mathematica

nn=20; t=Sum[n^(n-1)x^n/n!, {n, 1, nn}]; Range[0, nn]!CoefficientList[ Series[Integrate[Integrate[D[D[t, x], x]Exp[t], x], x], {x, 0, nn}], x]
Flatten[{0, 0, CoefficientList[Series[-(2 + LambertW[-x]) / (x^3*(1 + 1/LambertW[-x])^3), {x, 0, 20}], x] * Range[0, 20]!}] (* Vaclav Kotesovec, Aug 31 2014 *)

Crossrefs

Cf. A000169, A000272.

Sequence in context: A361599 A138739 A216831 * A197900 A106961 A215623

Adjacent sequences: A221861 A221862 A221863 * A221865 A221866 A221867

Keyword

nonn

Author

Geoffrey Critzer, Apr 10 2013

Status

approved