login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A105599 Triangle read by rows: T(n, m) = number of forests with n nodes and m labeled trees. Also number of forests with exactly n - m edges on n labeled nodes. 23
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, 262144, 200704, 76608, 18865, 3220, 378, 28, 1, 4782969, 3542940, 1316574, 320544, 55755, 7056, 630, 36, 1, 100000000, 72000000, 26100000, 6258000, 1092105, 143325, 14070, 990, 45, 1 (list; table; graph; refs; listen; history; text; internal format)
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
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
Rows reflected give A138464. - Alois P. Heinz, Sep 10 2008
T(2n,n) gives A302112.
Sequence in context: A001497 A123244 A364505 * A239895 A106210 A033842
KEYWORD
nonn,tabl
AUTHOR
Washington Bomfim, Apr 14 2005; revised May 19 2005
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 06:32 EDT 2024. Contains 370953 sequences. (Running on oeis4.)