|
%I #74 Apr 18 2020 22:13:31
%S 1,1,1,3,3,1,16,15,6,1,125,110,45,10,1,1296,1080,435,105,15,1,16807,
%T 13377,5250,1295,210,21,1,262144,200704,76608,18865,3220,378,28,1,
%U 4782969,3542940,1316574,320544,55755,7056,630,36,1,100000000,72000000,26100000,6258000,1092105,143325,14070,990,45,1
%N 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.
%C Row sums equal A001858 (number of forests of labeled trees with n nodes).
%C Also the Bell transform of A000272(n+1). For the definition of the Bell transform see A264428. - _Peter Luschny_, Jan 27 2016
%C 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
%D B. Bollobas, Graph Theory - An Introductory Course (Springer-Verlag, New York, 1979)
%H Alois P. Heinz, <a href="/A105599/b105599.txt">Rows n = 1..141, flattened</a>
%H E. Britikov, <a href="http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=mzm&paperid=4331&option_lang=eng">Asymptotic number of forests from unrooted trees</a>, Mat. Zametki (1988).
%H Mathoverflow, <a href="http://mathoverflow.net/questions/182797/is-there-a-formula-for-the-number-of-labeled-forests-with-k-components-on-n">Is there a formula for the number of labeled forests with k components on n vertices?</a>
%F 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_
%F 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) ).
%F From _Peter Bala_, Aug 14 2012: (Start)
%F 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.
%F 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.
%F (End)
%F 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
%F 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
%e T(3, 2) = 3 because there are 3 such forests with 3 nodes and 2 trees.
%e Triangle begins:
%e 1;
%e 1, 1;
%e 3, 3, 1;
%e 16, 15, 6, 1;
%e 125, 110, 45, 10, 1;
%e 1296, 1080, 435, 105, 15, 1;
%e 16807, 13377, 5250, 1295, 210, 21, 1;
%p T:= proc(n,m) option remember;
%p if n<0 then 0
%p elif n=m then 1
%p elif m<1 or m>n then 0
%p else add(binomial(n-1,j-1)*j^(j-2)*T(n-j,m-1), j=1..n-m+1)
%p fi
%p end:
%p seq(seq(T(n, m), m=1..n), n=1..12); # _Alois P. Heinz_, Sep 10 2008
%p # The function BellMatrix is defined in A264428.
%p # Adds (1,0,0,0, ..) as column 0.
%p BellMatrix(n -> (n+1)^(n-1), 9); # _Peter Luschny_, Jan 27 2016
%t 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 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_ *)
%t rows = 10;
%t t = Table[(n+1)^(n-1), {n, 0, rows}];
%t T[n_, k_] := BellY[n, k, t];
%t Table[T[n, k], {n, 1, rows}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Jun 22 2018, after _Peter Luschny_ *)
%o (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 */
%o (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
%Y Cf. A033185, A106240.
%Y Rows reflected give A138464. - _Alois P. Heinz_, Sep 10 2008
%Y Columns k=1-10 give: A000272, A083483, A239910, A240681, A240682, A240683, A240684, A240685, A240686, A240687.
%Y T(2n,n) gives A302112.
%K nonn,tabl
%O 1,4
%A _Washington Bomfim_, Apr 14 2005; revised May 19 2005
|
