login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A052121 Triangle of coefficients of polynomials enumerating trees with n labeled nodes by inversions. 2
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 (list; graph; refs; listen; history; text; internal format)
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 A117965

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 23 03:21 EDT 2018. Contains 316519 sequences. (Running on oeis4.)