A052121 Triangle of coefficients of polynomials enumerating trees with n labeled nodes by inversions.
1, 1, 2, 1, 6, 6, 3, 1, 24, 36, 30, 20, 10, 4, 1, 120, 240, 270, 240, 180, 120, 70, 35, 15, 5, 1, 720, 1800, 2520, 2730, 2520, 2100, 1610, 1140, 750, 455, 252, 126, 56, 21, 6, 1, 5040, 15120, 25200, 31920, 34230, 32970, 29400, 24640, 19600, 14840, 10696, 7336
Offset: 1
Examples
1 : 1; 2 : 1; 3 : 2, 1; 4 : 6, 6, 3, 1; 5 : 24, 36, 30, 20, 10, 4, 1; 6 : 120, 240, 270, 240, 180, 120, 70, 35, 15, 5, 1; 7 : 720, 1800, 2520, 2730, 2520, 2100, 1610, 1140, 750, 455, 252, 126, 56, 21, 6, 1; ...
References
- I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983.
- R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.48.
Links
- Alois P. Heinz, Rows n = 1..50, flattened
- I. Gessel and B. Sagan, The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions, The Elect. Jrn. of Comb., Vol. 3, Issue 2, 1996.
- I. M. Gessel, B. E. Sagan, and Y.-N. Yeh, Enumeration of trees by inversions, J. Graph Theory 19 (4) (1995) 435-459
- Ira Gessel and Da-Lun Wang, Depth-first search as a combinatorial correspondence, J. Combin. Theory Ser. A 26 (1979), 308-313.
- C. L. Mallows and J. Riordan, The inversion enumerator for labeled trees, Bull. Am. Math. Soc. 74 (1) (1968) 92-94, eq. (5).
- J. W. Moon, Counting labelled trees, Canad. Math. Monographs No 1 (1970) Section 4.5.
Programs
-
Maple
for n from 2 to 10 do add( J[i]*(x^i-1)/(x-1)*y^i/i! ,i=1..n-1) ; exp(%) ; coeftayl(%,y=0,n-1)*(n-1)! ; expand(%) ; J[n] := factor(convert(%,polynom)) ; for t from 0 to (n-1)*(n-2)/2 do printf("%d,",coeff(J[n],x,t)) ; end do: printf("\n") ; end do: # R. J. Mathar, Jul 02 2018 -
Mathematica
rows = 8; egf = (y - 1)*Log[Sum[(y^Binomial[n, 2]*(x^n/n!))/(y - 1)^n, {n, 0, rows + 1}]]; t = CoefficientList[ Series[egf, {x, 0, rows}, {y, 0, 3*rows}], {x, y}] ; Table[(n - 1)!*t[[n, k]], {n, 2, rows + 1}, {k, 1, Binomial[n - 2, 2] + 1}] // Flatten (* Jean-François Alcover, Dec 10 2012, after Vladeta Jovovic *)
Formula
Sum_{k=0..binomial(n-1,2)} T(n,k) = A000272(n).
Sum_{k=0..binomial(n-1,2)} (-1)^k*T(n,k) = A000111(n-1).
E.g.f.: (y-1)*log(Sum_{n>=0} (y-1)^(-n)*y^binomial(n, 2)*x^n/n!).
Sum_{k=0..binomial(n-1,2)} k*T(n,k) = A057500(n). - Alois P. Heinz, Nov 29 2015
Equals the coefficient [x^t] of the polynomial J_n(x) which satisfies sum_{>=0} J_{n+1}(x)*y^n/n! = exp[ sum_{n>=1} J_n(x) (x^n-1)/(x-1)*y^n/n!]. - R. J. Mathar, Jul 02 2018
Extensions
Formulae and more terms from Vladeta Jovovic, Apr 06 2001
Comments