A218688 Number of ways to linearly arrange the trees over all forests on n labeled nodes.

1, 1, 3, 15, 106, 975, 11106, 151501, 2415960, 44221869, 915826600, 21211128411, 544126606992, 15334985416075, 471495297242256, 15719617534811625, 565271886957356416, 21820620411482896089, 900398349688515500160, 39564926462522623540519, 1845034125763359894240000

Offset: 0

Author

Geoffrey Critzer, Nov 04 2012

Keywords

• nonn

Links

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

Crossrefs

Cf. A101313.

Programs

Maple

T:= -LambertW(-x):
egf:= 1/(1-T+T^2/2):
a:= n-> n! * coeff(series(egf, x, n+1), x, n):
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 04 2012

Mathematica

nn=20;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];Range[0,nn]!CoefficientList[ Series[1/(1-t+t^2/2),{x,0,nn}],x]

PARI

A218688_vec(n,A=List(1))={until(#A>n,listput(A,sum(k=1,#A,binomial(#A,k)*k^(k-2)*A[#A-k+1])));Vec(A)} \\ M. F. Hasler, Jan 26 2020

Formula

E.g.f.: 1/(1- T(x) + T(x)^2/2) where T(x) is e.g.f. for A000169.

a(n) = Sum_{m=1..n} A105599(n,m)*m!.

a(n) ~ 4*n^(n-2). - Vaclav Kotesovec, Aug 16 2013

a(0) = 1; a(n) = Sum_{k=1..n} binomial(n,k) * k^(k-2) * a(n-k). - Ilya Gutkovskiy, Jan 26 2020