login
Triangle of coefficients of polynomials enumerating trees with n labeled nodes by inversions.
2

%I #27 Aug 04 2018 11:22:18

%S 1,1,2,1,6,6,3,1,24,36,30,20,10,4,1,120,240,270,240,180,120,70,35,15,

%T 5,1,720,1800,2520,2730,2520,2100,1610,1140,750,455,252,126,56,21,6,1,

%U 5040,15120,25200,31920,34230,32970,29400,24640,19600,14840,10696,7336

%N Triangle of coefficients of polynomials enumerating trees with n labeled nodes by inversions.

%C Specialization of Tutte polynomials for complete graphs. See the Gessel and Sagan paper. - _Tom Copeland_, Jan 17 2017

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

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

%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.48.

%H Alois P. Heinz, <a href="/A052121/b052121.txt">Rows n = 1..50, flattened</a>

%H I. Gessel and B. Sagan, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v3i2r9">The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions</a>, The Elect. Jrn. of Comb., Vol. 3, Issue 2, 1996.

%H I. M. Gessel, B. E. Sagan, Y.-N. Yeh, <a href="http://doi.org/10.1002/jgt.3190190402">Enumeration of trees by inversions</a>, J. Graph Theory 19 (4) (1995) 435-459

%H C. L. Mallows, J. Riordan, <a href="https://projecteuclid.org/euclid.bams/1183529387">The inversion enumerator for labeled trees</a>, Bull. Am. Math. Soc. 74 (1) (1968) 92-94, eq. (5)

%F Sum_{k=0..binomial(n-1,2)} T(n,k) = A000272(n).

%F Sum_{k=0..binomial(n-1,2)} (-1)^k*T(n,k) = A000111(n-1).

%F E.g.f.: (y-1)*log(Sum_{n>=0} (y-1)^(-n)*y^binomial(n, 2)*x^n/n!).

%F Sum_{k=0..binomial(n-1,2)} k*T(n,k) = A057500(n). - _Alois P. Heinz_, Nov 29 2015

%F 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

%e 1 : 1;

%e 2 : 1;

%e 3 : 2, 1;

%e 4 : 6, 6, 3, 1;

%e 5 : 24, 36, 30, 20, 10, 4, 1;

%e 6 : 120, 240, 270, 240, 180, 120, 70, 35, 15, 5, 1;

%e 7 : 720, 1800, 2520, 2730, 2520, 2100, 1610, 1140, 750, 455, 252, 126, 56, 21, 6, 1;

%e ...

%p for n from 2 to 10 do

%p add( J[i]*(x^i-1)/(x-1)*y^i/i! ,i=1..n-1) ;

%p exp(%) ;

%p coeftayl(%,y=0,n-1)*(n-1)! ;

%p expand(%) ;

%p J[n] := factor(convert(%,polynom)) ;

%p for t from 0 to (n-1)*(n-2)/2 do

%p printf("%d,",coeff(J[n],x,t)) ;

%p end do:

%p printf("\n") ;

%p end do: # _R. J. Mathar_, Jul 02 2018

%t 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_ *)

%Y Cf. A000272, A000111, A057500.

%K nonn,easy,nice,tabf

%O 1,3

%A _N. J. A. Sloane_, Jan 23 2000

%E Formulae and more terms from _Vladeta Jovovic_, Apr 06 2001