𝑞-Eulerian polynomials: Excedance number and major index

Shareshian, John¹ ; Wachs, Michelle²

¹ Department of Mathematics, Washington University, St. Louis, Missouri 63130
² Department of Mathematics, University of Miami, Coral Gables, Florida 33124

Electronic research announcements of the American Mathematical Society, Tome 13 (2007), pp. 33-45.

Résumé

In this research announcement we present a new $q$-analog of a classical formula for the exponential generating function of the Eulerian polynomials. The Eulerian polynomials enumerate permutations according to their number of descents or their number of excedances. Our $q$-Eulerian polynomials are the enumerators for the joint distribution of the excedance statistic and the major index. There is a vast literature on $q$-Eulerian polynomials that involves other combinations of Eulerian and Mahonian permutation statistics, but this is the first result to address the combination of excedance number and major index. We use symmetric function theory to prove our formula. In particular, we prove a symmetric function version of our formula, which involves an intriguing new class of symmetric functions. We also discuss connections with (1) the representation of the symmetric group on the homology of a poset introduced by Björner and Welker; (2) the representation of the symmetric group on the cohomology of the toric variety associated with the Coxeter complex of the symmetric group, studied by Procesi, Stanley, Stembridge, Dolgachev, and Lunts; (3) the enumeration of words with no adjacent repeats studied by Carlitz, Scoville, and Vaughan and by Dollhopf, Goulden, and Greene; and (4) Stanley’s chromatic symmetric functions.

Détail

DOI : 10.1090/S1079-6762-07-00172-2

Bibliographie

[1] Babson, Eric, Steingrímsson, Einar Generalized permutation patterns and a classification of the Mahonian statistics Sém. Lothar. Combin. 2000

[2] Beck, Desiree A., Remmel, Jeffrey B. Permutation enumeration of the symmetric group and the combinatorics of symmetric functions J. Combin. Theory Ser. A 1995 1 49

[3] Björner, Anders Shellable and Cohen-Macaulay partially ordered sets Trans. Amer. Math. Soc. 1980 159 183

[4] Björner, Anders, Welker, Volkmar Segre and Rees products of posets, with ring-theoretic applications J. Pure Appl. Algebra 2005 43 55

[5] Carlitz, L. A combinatorial property of 𝑞-Eulerian numbers Amer. Math. Monthly 1975 51 54

[6] Carlitz, L., Scoville, Richard, Vaughan, Theresa Enumeration of pairs of sequences by rises, falls and levels Manuscripta Math. 1976 211 243

[7] Clarke, Robert J., Steingrímsson, Einar, Zeng, Jiang New Euler-Mahonian statistics on permutations and words Adv. in Appl. Math. 1997 237 270

[8] Désarménien, Jacques, Wachs, Michelle L. Descent classes of permutations with a given number of fixed points J. Combin. Theory Ser. A 1993 311 328

[9] Dolgachev, Igor, Lunts, Valery A character formula for the representation of a Weyl group in the cohomology of the associated toric variety J. Algebra 1994 741 772

[10] Dollhopf, John, Goulden, Ian, Greene, Curtis Words avoiding a reflexive acyclic relation Electron. J. Combin. 2004/06

[11] Foata, Dominique Sur un énoncé de MacMahon C. R. Acad. Sci. Paris 1964 1672 1675

[12] Foata, Dominique On the Netto inversion number of a sequence Proc. Amer. Math. Soc. 1968 236 240

[13] Foata, Dominique Distributions eulériennes et mahoniennes sur le groupe des permutations 1977 27 49

[14] Lothaire, M. Combinatorics on words 1983

[15] Foata, Dominique, Schützenberger, Marcel-P. Théorie géométrique des polynômes eulériens 1970

[16] Foata, Dominique, Schützenberger, Marcel-Paul Major index and inversion number of permutations Math. Nachr. 1978 143 159

[17] Foata, Dominique, Zeilberger, Doron Denert’s permutation statistic is indeed Euler-Mahonian Stud. Appl. Math. 1990 31 59

[18] Garsia, A. M., Gessel, I. Permutation statistics and partitions Adv. in Math. 1979 288 305

[19] Gessel, Ira M., Reutenauer, Christophe Counting permutations with given cycle structure and descent set J. Combin. Theory Ser. A 1993 189 215

[20] Haglund, James 𝑞-rook polynomials and matrices over finite fields Adv. in Appl. Math. 1998 450 487

[21] Knuth, Donald E. The art of computer programming. Volume 3 1973

[22] Macmahon, Percy A. Combinatory analysis 1960

[23] Macmahon, P. A. The Indices of Permutations and the Derivation Therefrom of Functions of a Single Variable Associated with the Permutations of any Assemblage of Objects Amer. J. Math. 1913 281 322

[24] Lothaire, M. Combinatorics on words 1983

[25] Procesi, C. The toric variety associated to Weyl chambers 1990 153 161

[26] Ram, Arun, Remmel, Jeffrey B., Whitehead, Tamsen Combinatorics of the 𝑞-basis of symmetric functions J. Combin. Theory Ser. A 1996 231 271

[27] Rawlings, Don Enumeration of permutations by descents, idescents, imajor index, and basic components J. Combin. Theory Ser. A 1984 1 14

[28] Skandera, Mark An Eulerian partner for inversions Sém. Lothar. Combin. 2001/02

[29] Stanley, Richard P. Ordered structures and partitions 1972

[30] Stanley, Richard P. Binomial posets, Möbius inversion, and permutation enumeration J. Combinatorial Theory Ser. A 1976 336 356

[31] Stanley, Richard P. Log-concave and unimodal sequences in algebra, combinatorics, and geometry 1989 500 535

[32] Stanley, Richard P. Enumerative combinatorics. Vol. 2 1999

[33] Stanley, Richard P. A symmetric function generalization of the chromatic polynomial of a graph Adv. Math. 1995 166 194

[34] Stembridge, John R. Eulerian numbers, tableaux, and the Betti numbers of a toric variety Discrete Math. 1992 307 320

[35] Stembridge, John R. Some permutation representations of Weyl groups associated with the cohomology of toric varieties Adv. Math. 1994 244 301

[36] Désarménien, Jacques, Foata, Dominique The signed Eulerian numbers Discrete Math. 1992 49 58