The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
The OEIS is supported by the many generous donors to the OEIS Foundation.

 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 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? 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 Cf. A033185, A106240. Rows reflected give A138464. - Alois P. Heinz, Sep 10 2008 Columns k=1-10 give: A000272, A083483, A239910, A240681, A240682, A240683, A240684, A240685, A240686, A240687. T(2n,n) gives A302112. Sequence in context: A001497 A123244 A364505 * A239895 A106210 A033842 Adjacent sequences: A105596 A105597 A105598 * A105600 A105601 A105602 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.

Last modified June 17 06:41 EDT 2024. Contains 373432 sequences. (Running on oeis4.)