𝑞-Eulerian polynomials: Excedance number and major index

Shareshian, John; Wachs, Michelle

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

Previous volume | This volume | All volumes | Previous article | Next article

$q$-Eulerian polynomials: Excedance number and major index

Authors: John Shareshian and Michelle L. Wachs
Journal: Electron. Res. Announc. Amer. Math. Soc. 13 (2007), 33-45
MSC (2000): Primary 05A30, 05E05, 05E25
DOI: https://doi.org/10.1090/S1079-6762-07-00172-2
Published electronically: April 12, 2007
MathSciNet review: 2300004
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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.

Eric Babson and Einar Steingrímsson, Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Lothar. Combin. 44 (2000), Art. B44b, 18. MR 1758852
Desiree A. Beck and Jeffrey B. Remmel, Permutation enumeration of the symmetric group and the combinatorics of symmetric functions, J. Combin. Theory Ser. A 72 (1995), no. 1, 1–49. MR 1354966, DOI https://doi.org/10.1016/0097-3165%2895%2990027-6
Anders Björner, Shellable and Cohen-Macaulay partially ordered sets, Trans. Amer. Math. Soc. 260 (1980), no. 1, 159–183. MR 570784, DOI https://doi.org/10.1090/S0002-9947-1980-0570784-2
Anders Björner and Volkmar Welker, Segre and Rees products of posets, with ring-theoretic applications, J. Pure Appl. Algebra 198 (2005), no. 1-3, 43–55. MR 2132872, DOI https://doi.org/10.1016/j.jpaa.2004.11.013
L. Carlitz, A combinatorial property of $q$-Eulerian numbers, Amer. Math. Monthly 82 (1975), 51–54. MR 366683, DOI https://doi.org/10.2307/2319133
L. Carlitz, Richard Scoville, and Theresa Vaughan, Enumeration of pairs of sequences by rises, falls and levels, Manuscripta Math. 19 (1976), no. 3, 211–243. MR 432472, DOI https://doi.org/10.1007/BF01170773
Robert J. Clarke, Einar Steingrímsson, and Jiang Zeng, New Euler-Mahonian statistics on permutations and words, Adv. in Appl. Math. 18 (1997), no. 3, 237–270. MR 1436481, DOI https://doi.org/10.1006/aama.1996.0506
Jacques Désarménien and Michelle L. Wachs, Descent classes of permutations with a given number of fixed points, J. Combin. Theory Ser. A 64 (1993), no. 2, 311–328. MR 1245164, DOI https://doi.org/10.1016/0097-3165%2893%2990100-M
Igor Dolgachev and Valery Lunts, A character formula for the representation of a Weyl group in the cohomology of the associated toric variety, J. Algebra 168 (1994), no. 3, 741–772. MR 1293622, DOI https://doi.org/10.1006/jabr.1994.1251
John Dollhopf, Ian Goulden, and Curtis Greene, Words avoiding a reflexive acyclic relation, Electron. J. Combin. 11 (2004/06), no. 2, Research Paper 28, 32. MR 2224941
Dominique Foata, Sur un énoncé de MacMahon, C. R. Acad. Sci. Paris 258 (1964), 1672–1675 (French). MR 158834
Dominique Foata, On the Netto inversion number of a sequence, Proc. Amer. Math. Soc. 19 (1968), 236–240. MR 223256, DOI https://doi.org/10.1090/S0002-9939-1968-0223256-9
Dominique Foata, Distributions eulériennes et mahoniennes sur le groupe des permutations, Higher combinatorics (Proc. NATO Advanced Study Inst., Berlin, 1976), NATO Adv. Study Inst. Ser., Ser. C: Math. Phys. Sci., vol. 31, Reidel, Dordrecht-Boston, Mass., 1977, pp. 27–49 (French). With a comment by Richard P. Stanley. MR 519777
M. Lothaire, Combinatorics on words, Encyclopedia of Mathematics and its Applications, vol. 17, Addison-Wesley Publishing Co., Reading, Mass., 1983. A collective work by Dominique Perrin, Jean Berstel, Christian Choffrut, Robert Cori, Dominique Foata, Jean Eric Pin, Guiseppe Pirillo, Christophe Reutenauer, Marcel-P. Schützenberger, Jacques Sakarovitch and Imre Simon; With a foreword by Roger Lyndon; Edited and with a preface by Perrin. MR 675953
Dominique Foata and Marcel-P. Schützenberger, Théorie géométrique des polynômes eulériens, Lecture Notes in Mathematics, Vol. 138, Springer-Verlag, Berlin-New York, 1970 (French). MR 0272642
Dominique Foata and Marcel-Paul Schützenberger, Major index and inversion number of permutations, Math. Nachr. 83 (1978), 143–159. MR 506852, DOI https://doi.org/10.1002/mana.19780830111
Dominique Foata and Doron Zeilberger, Denert’s permutation statistic is indeed Euler-Mahonian, Stud. Appl. Math. 83 (1990), no. 1, 31–59. MR 1061147, DOI https://doi.org/10.1002/sapm199083131
A. M. Garsia and I. Gessel, Permutation statistics and partitions, Adv. in Math. 31 (1979), no. 3, 288–305. MR 532836, DOI https://doi.org/10.1016/0001-8708%2879%2990046-X
Ira M. Gessel and Christophe Reutenauer, Counting permutations with given cycle structure and descent set, J. Combin. Theory Ser. A 64 (1993), no. 2, 189–215. MR 1245159, DOI https://doi.org/10.1016/0097-3165%2893%2990095-P
James Haglund, $q$-rook polynomials and matrices over finite fields, Adv. in Appl. Math. 20 (1998), no. 4, 450–487. MR 1612854, DOI https://doi.org/10.1006/aama.1998.0582
Donald E. Knuth, The art of computer programming. Volume 3, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching; Addison-Wesley Series in Computer Science and Information Processing. MR 0445948
Percy A. MacMahon, Combinatory analysis, Chelsea Publishing Co., New York, 1960. Two volumes (bound as one). MR 0141605
P. A. MacMahon, 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. 35 (1913), no. 3, 281–322. MR 1506186, DOI https://doi.org/10.2307/2370312
M. Lothaire, Combinatorics on words, Encyclopedia of Mathematics and its Applications, vol. 17, Addison-Wesley Publishing Co., Reading, Mass., 1983. A collective work by Dominique Perrin, Jean Berstel, Christian Choffrut, Robert Cori, Dominique Foata, Jean Eric Pin, Guiseppe Pirillo, Christophe Reutenauer, Marcel-P. Schützenberger, Jacques Sakarovitch and Imre Simon; With a foreword by Roger Lyndon; Edited and with a preface by Perrin. MR 675953
C. Procesi, The toric variety associated to Weyl chambers, Mots, Lang. Raison. Calc., Hermès, Paris, 1990, pp. 153–161. MR 1252661
Arun Ram, Jeffrey B. Remmel, and Tamsen Whitehead, Combinatorics of the $q$-basis of symmetric functions, J. Combin. Theory Ser. A 76 (1996), no. 2, 231–271. MR 1416016, DOI https://doi.org/10.1006/jcta.1996.0103
Don Rawlings, Enumeration of permutations by descents, idescents, imajor index, and basic components, J. Combin. Theory Ser. A 36 (1984), no. 1, 1–14. MR 728499, DOI https://doi.org/10.1016/0097-3165%2884%2990074-8

rod O. Rodrigues, Note sur les inversions, ou derangements produits dans les permutations, Journal de Mathematiques 4 (1839), 236–240.

Mark Skandera, An Eulerian partner for inversions, Sém. Lothar. Combin. 46 (2001/02), Art. B46d, 19. MR 1848722
Richard P. Stanley, Ordered structures and partitions, American Mathematical Society, Providence, R.I., 1972. Memoirs of the American Mathematical Society, No. 119. MR 0332509
Richard P. Stanley, Binomial posets, Möbius inversion, and permutation enumeration, J. Combinatorial Theory Ser. A 20 (1976), no. 3, 336–356. MR 409206, DOI https://doi.org/10.1016/0097-3165%2876%2990028-5
Richard P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Graph theory and its applications: East and West (Jinan, 1986) Ann. New York Acad. Sci., vol. 576, New York Acad. Sci., New York, 1989, pp. 500–535. MR 1110850, DOI https://doi.org/10.1111/j.1749-6632.1989.tb16434.x
Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. MR 1676282
Richard P. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Adv. Math. 111 (1995), no. 1, 166–194. MR 1317387, DOI https://doi.org/10.1006/aima.1995.1020
John R. Stembridge, Eulerian numbers, tableaux, and the Betti numbers of a toric variety, Discrete Math. 99 (1992), no. 1-3, 307–320. MR 1158793, DOI https://doi.org/10.1016/0012-365X%2892%2990378-S
John R. Stembridge, Some permutation representations of Weyl groups associated with the cohomology of toric varieties, Adv. Math. 106 (1994), no. 2, 244–301. MR 1279220, DOI https://doi.org/10.1006/aima.1994.1058

w1 M.L. Wachs, Poset topology: tools and applications, to appear as chapter of Geometric Combinatorics volume of PCMI lecture notes series. ArXiv math.CO/0602226.

Jacques Désarménien and Dominique Foata, The signed Eulerian numbers, Discrete Math. 99 (1992), no. 1-3, 49–58. MR 1158779, DOI https://doi.org/10.1016/0012-365X%2892%2990364-L