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

Author

N. J. A. Sloane, May 09 2008

Keywords

• nonn
• tabl
• look

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

Examples

			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;
		

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

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

Programs

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

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]

Extensions

More terms from Alois P. Heinz, Sep 02 2008