The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

 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. 22
 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 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 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: A112292 A001497 A123244 * A239895 A106210 A033842 Adjacent sequences:  A105596 A105597 A105598 * A105600 A105601 A105602 KEYWORD nonn,tabl,changed 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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified January 23 22:36 EST 2020. Contains 331177 sequences. (Running on oeis4.)