OFFSET
1,4
COMMENTS
Row sums equal A001858 (number of forests of labeled trees with n nodes).
Also the Bell transform of A000272(n+1). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 27 2016
The permutohedron (convex hull of permutations on 1,...,n in R^n) has Ehrhart polynomial Sum_{k=0..n-1} T(n,n-k) t^k. - Matthieu Josuat-Vergès, Mar 31 2018
REFERENCES
B. Bollobas, Graph Theory - An Introductory Course (Springer-Verlag, New York, 1979)
LINKS
Alois P. Heinz, Rows n = 1..141, flattened
E. Britikov, Asymptotic number of forests from unrooted trees, Mat. Zametki (1988).
FORMULA
T(n,m) = Sum_{k=1..n-m+1} binomial(n-1,k-1)*k^(k-2)*T(n-k,m-1), T(n,0) = 0 if n > 0, T(0,0) = 1. - Vladeta Jovovic and Washington Bomfim
The value of T(n, m) can be calculated by the formula in Bollobas, pp. 172, exercise 44. Also T(n, m) = sum N/D over the partitions of n, 1*K(1) + 2*K(2) + ... + n*K(n), with exactly m parts, where N = n! * Product_{i = 1..n} i^( (i-2) * K(i) ) and D = Product_{i = 1..n} ( K(i)! * (i!)^K(i) ).
From Peter Bala, Aug 14 2012: (Start)
E.g.f.: A(x,t) := exp(t*F(x)) = 1 + t*x + (t + t^2)*x^2/2! + (3*t + 3*t^2 + t^3)*x^3/3! + ..., where F(x) = sum {n >= 1} n^(n-2)*x^n/n! is the e.g.f. for labeled trees (see A000272). The row polynomials R(n,t) are thus a sequence of binomial type polynomials.
Differentiating A(x,t) w.r.t. x yields A'(x,t) = t*A(x,t)*F'(x) leading to the recurrence equation for the row polynomials R(n,t) = t*sum {k = 0..n-1} (k+1)^(k-1)*binomial(n-1,k)*R(n-k-1,t) with R(0,t) = 1 and R(1,t) = t: the above recurrence for the table entries follows from this.
(End)
T(n,m) = (1/m!) * Sum_{j=0..m} (-1/2)^j * binomial(m,j) * binomial(n-1,m+j-1) * n^(n-m-j)* (m+j)!. Due to A. Renyi. - Max Alekseyev, Oct 08 2014
T(n,m) = (n!/m!)*Sum_{k_1+...+k_m=n, k_i>=1} Product_{j=1..m} k_j^(k_j-2)/k_j!. See Britikov reference. - Roland Vincze, Apr 18 2020
EXAMPLE
T(3, 2) = 3 because there are 3 such forests with 3 nodes and 2 trees.
Triangle begins:
1;
1, 1;
3, 3, 1;
16, 15, 6, 1;
125, 110, 45, 10, 1;
1296, 1080, 435, 105, 15, 1;
16807, 13377, 5250, 1295, 210, 21, 1;
MAPLE
T:= proc(n, m) option remember;
if n<0 then 0
elif n=m then 1
elif m<1 or m>n then 0
else add(binomial(n-1, j-1)*j^(j-2)*T(n-j, m-1), j=1..n-m+1)
fi
end:
seq(seq(T(n, m), m=1..n), n=1..12); # Alois P. Heinz, Sep 10 2008
# The function BellMatrix is defined in A264428.
# Adds (1, 0, 0, 0, ..) as column 0.
BellMatrix(n -> (n+1)^(n-1), 9); # Peter Luschny, Jan 27 2016
MATHEMATICA
f[list_]:=Select[list, #>0&]; Flatten[Map[f, Transpose[Table[t = Sum[n^(n - 2) x^n/n!, {n, 1, 20}]; Drop[Range[0, 8]! CoefficientList[Series[t^k/k!, {x, 0, 8}], x], 1], {k, 1, 8}]]]] (* Geoffrey Critzer, Nov 22 2011 *)
T[n_, m_] := Sum[(-1/2)^j*Binomial[m, j]*Binomial[n-1, m+j-1]*n^(n-m-j)*(m + j)!, {j, 0, m}]/m!; Table[T[n, m], {n, 1, 10}, {m, 1, n}] // Flatten (* Jean-François Alcover, Jan 09 2016, after Max Alekseyev *)
rows = 10;
t = Table[(n+1)^(n-1), {n, 0, rows}];
T[n_, k_] := BellY[n, k, t];
Table[T[n, k], {n, 1, rows}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 22 2018, after Peter Luschny *)
PROG
(PARI) { T(n, m) = sum(j=0, m, (-1/2)^j * binomial(m, j) * binomial(n-1, m+j-1) * n^(n-m-j)* (m+j)! )/m! } /* Max Alekseyev, Oct 08 2014 */
(GAP) Flat(List([1..11], n->List([1..n], m->(1/Factorial(m)*Sum([0..m], j->(-1/2)^j*Binomial(m, j)*Binomial(n-1, m+j-1)*n^(n-m-j)*Factorial(m+j)))))); # Muniru A Asiru, Apr 01 2018
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Washington Bomfim, Apr 14 2005; revised May 19 2005
STATUS
approved