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.
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
Offset: 1
Examples
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;
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).
- Mathoverflow, Is there a formula for the number of labeled forests with k components on n vertices?
Crossrefs
Programs
-
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
-
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 *) -
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 */
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
Comments