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,3

Comments

Specialization of Tutte polynomials for complete graphs. See the Gessel and Sagan paper. - Tom Copeland, Jan 17 2017

References

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983.

J. W. Moon, Counting labelled trees, Canad. Math. Monographs No 1 (1970) Section 4.5.

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, Y.-N. Yeh, Enumeration of trees by inversions, J. Graph Theory 19 (4) (1995) 435-459

C. L. Mallows, J. Riordan, The inversion enumerator for labeled trees, Bull. Am. Math. Soc. 74 (1) (1968) 92-94, eq. (5)

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

Example

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;
...

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 *)

Crossrefs

Cf. A000272, A000111, A057500.

Sequence in context: A182729 A260885 A075181 * A193895 A193561 A328349

Adjacent sequences: A052118 A052119 A052120 * A052122 A052123 A052124

Keyword

nonn,easy,nice,tabf

Author

N. J. A. Sloane, Jan 23 2000

Extensions

Formulae and more terms from Vladeta Jovovic, Apr 06 2001

Status

approved