A138464 Triangle read by rows: T(n, k) is the number of forests on n labeled nodes with k edges. T(n, k) for n >= 1 and 0 <= k <= n-1.

1, 1, 1, 1, 3, 3, 1, 6, 15, 16, 1, 10, 45, 110, 125, 1, 15, 105, 435, 1080, 1296, 1, 21, 210, 1295, 5250, 13377, 16807, 1, 28, 378, 3220, 18865, 76608, 200704, 262144, 1, 36, 630, 7056, 55755, 320544, 1316574, 3542940, 4782969, 1, 45, 990, 14070, 143325, 1092105, 6258000, 26100000, 72000000, 100000000

Offset

1,5

Comments

The rows of the triangle give the coefficients of the Ehrhart polynomials of integral Coxeter permutahedra of type A. These polynomials count lattice points in a dilated lattice polytope. For a definition see Ardila et al. (p. 1158), the generating functions of these polynomials for the classical root systems are given in theorem 5.2 (p. 1163). - Peter Luschny, May 01 2021

Links

Alois P. Heinz, Rows n = 1..141, flattened

Federico Ardila, Matthias Beck, and Jodi McWhirter, The arithmetic of Coxeter permutahedra, Rev. Acad. Colomb. Cienc. Ex. Fis. Nat. 44(173):1152-1166, 2020.

John Riordan and N. J. A. Sloane, Correspondence, 1974

Formula

From Peter Bala, Aug 14 2012: (Start)

T(n+1,k) = Sum_{i=0..k} (i+1)^(i-1)*binomial(n,i)*T(n-i,k-i) with T(0,0)=1.

Recurrence equation for row polynomials R(n,t): R(n,t) = Sum_{k=0..n-1} (k+1)^(k-1)*binomial(n-1,k)*t^k*R(n-k-1,t) with R(0,t) = R(1,t) = 1.

The production matrix for the row polynomials of the triangle is obtained from A088956 and starts:

1 t

1 1 t

3 2 1 t

16 9 3 1 t

125 64 18 4 1 t

(End)

E.g.f.: exp( Sum_{n >= 1} n^(n-2)*t^(n-1)*x^n/n! ). - Peter Bala, Nov 08 2015

T(n, k) = [t^k] n! [x^n] exp(-W(-t*x)/t - W(-t*x)^2/(2*t)), where W denotes the Lambert function. - Peter Luschny, Apr 30 2021 [Typo corrected after note from Andrew Howroyd, Peter Luschny, Jun 20 2021]

Example

Triangle begins:
[1]  1;
[2]  1,  1;
[3]  1,  3,   3;
[4]  1,  6,  15,   16;
[5]  1, 10,  45,  110,  125;
[6]  1, 15, 105,  435, 1080,  1296;
[7]  1, 21, 210, 1295, 5250, 13377, 16807;

Maple

T:= proc(n) option remember; if n=0 then 0 else T(n-1) +n^(n-1) *x^n/n! fi end: TT:= proc(n) option remember; expand(T(n) -T(n)^2/2) end: f:= proc(k) option remember; if k=0 then 1 else unapply(f(k-1)(x) +x^k/k!, x) fi end: A:= proc(n, k) option remember; series(f(k)(TT(n)), x, n+1) end: aa:= (n, k)-> coeff(A(n, k), x, n) *n!: a:= (n, k)-> aa(n, n-k) -aa(n, n-k-1): seq(seq(a(n, k), k=0..n-1), n=1..10);  # Alois P. Heinz, Sep 02 2008
alias(W = LambertW): EhrA := exp(-W(-t*x)/t - W(-t*x)^2/(2*t)):
ser := series(EhrA, x, 12): cx := n -> n!*coeff(ser, x, n):
T := n -> seq(coeff(cx(n), t, k), k=0..n-1):
seq(T(n), n = 1..10); # Peter Luschny, Apr 30 2021

Mathematica

t[0, 0] = 1; t[n_ /; n >= 1, k_] /; (0 <= k <= n-1) := t[n, k] = Sum[(i+1)^(i-1)*Binomial[n-1, i]*t[n-i-1, k-i], {i, 0, k}]; t[_, _] = 0; Table[t[n, k], {n, 1, 10}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, Jan 14 2014, after Peter Bala *)
gf := E^(-(ProductLog[-(t x)] (2 + ProductLog[-(t x)]))/(2 t));
ser := Series[gf, {x, 0, 12}]; cx[n_] := n! Coefficient[ser, x, n];
Table[CoefficientList[cx[n], t], {n, 1, 10}] // Flatten  (* Peter Luschny, May 01 2021 *)

Crossrefs

Row sums give A001858. Rightmost diagonal gives A000272. Cf. A136605.

Rows reflected give A105599. - Alois P. Heinz, Oct 28 2011

Cf. A088956.

Lower diagonals give: A083483, A239910, A240681, A240682, A240683, A240684, A240685, A240686, A240687. - Alois P. Heinz, Apr 11 2014

T(2n,n) gives A302112.

For Ehrhart polynomials of integral Coxeter permutahedra of classical type cf. this sequence (type A), A343805 (type B), A343806 (type C), A343807 (type D).

Sequence in context: A240439 A243211 A199034 * A117279 A234251 A049323

Adjacent sequences: A138461 A138462 A138463 * A138465 A138466 A138467

Keyword

nonn,tabl,look

Author

N. J. A. Sloane, May 09 2008

Extensions

More terms from Alois P. Heinz, Sep 02 2008

Status

approved