Electronic Research Announcements

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1079-6762

-Eulerian polynomials: Excedance number and major index

Author(s): John Shareshian; Michelle L. Wachs
Journal: Electron. Res. Announc. Amer. Math. Soc. 13 (2007), 33-45.
MSC (2000): Primary 05A30, 05E05, 05E25
Posted: April 12, 2007
MathSciNet review: 2300004
Retrieve article in: PDF
This article is available free of charge

Abstract | References | Similar articles | Additional information

Abstract: In this research announcement we present a new -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 -Eulerian polynomials are the enumerators for the joint distribution of the excedance statistic and the major index. There is a vast literature on -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.

References:

1.: E. Babson and E. Steingrímsson, Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Lothar. Combin., B44b (2000), 18 pp. MR 1758852 (2002b:05006)
2.: D. Beck and J.B. Remmel, Permutation enumeration of the symmetric group and the combinatorics of symmetric functions, J. Combin. Theory Ser. A 72 (1995), 1-49. MR 1354966 (96j:05113)
3.: A. Björner, Shellable and Cohen-Macaulay partially ordered sets, Trans. AMS 260 (1980), 159-183. MR 570784 (81i:06001)
4.: A. Björner and V. Welker, Segre and Rees products of posets, with ring-theoretic applications, J. Pure Appl. Algebra 198 (2005), 43-55. MR 2132872 (2005m:06006)
5.: L. Carlitz, A combinatorial property of -Eulerian numbers, The American Mathematical Monthly 82 (1975), 51-54. MR 0366683 (51:2930)
6.: L. Carlitz, R. Scoville, and T. Vaughan, Enumeration of pairs of sequences by rises, falls and levels, Manuscripta Math. 19 (1976), 211-243. MR 0432472 (55:5460)
7.: R.J. Clarke, E. Steingrímsson, and J. Zeng, New Euler-Mahonian statistics on permutations and words, Adv. in Appl. Math. 18 (1997), 237-270. MR 1436481 (97m:05008)
8.: J. Désarménien and M.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 (95c:05008)
9.: I. Dolgachev and V. Lunts, A character formula for the representation of a Weyl group in the cohomology of the associated toric variety, J. Algebra 168 (1994), 741-772. MR 1293622 (95h:20008)
10.: J. Dollhopf, I. Goulden, and C. Greene, Words avoiding a reflexive acyclic relation, Electon. J. Combin. 11 (2006) #R28. MR 2224941 (2007b:05013)
11.: D. Foata, Sur un énoncé de MacMahon, C. R. Acad. Sci. Paris 258 (1964), 1672-1675. MR 0158834 (28:2057)
12.: D. Foata, On the Netto inversion number of a sequence, Proc. Amer. Math. Soc. 19 (1968), 236-240. MR 0223256 (36:6304)
13.: D. Foata, Distributions eulériennes et mahoniennes sur le groupe des permutations, NATO Adv. Study Inst. Ser., Ser. C: Math. Phys. Sci., 31, Higher combinatorics (Proc. NATO Advanced Study Inst., Berlin, 1976), pp. 27-49, Reidel, Dordrecht-Boston, Mass., 1977. MR 519777 (80e:05011)
14.: D. Foata, Rearrangements of words, in M. Lothaire, Combinatorics on Words, Ch. 10, Encyclopedia of Math. and its Appl., Vol. 17, Addison-Wesley, Reading, MA, 1983. MR 675953 (84g:05002)
15.: D. Foata and M.-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. MR 0272642 (42:7523)
16.: D. Foata and M.-P. Schützenberger, Major index and inversion number of permutations, Math. Nachr. 83 (1978), 143-159. MR 506852 (81d:05007)
17.: D. Foata and D. Zeilberger, Denert's permutation statistic is indeed Euler-Mahonian, Stud. Appl. Math. 83 (1990), 31-59. MR 1061147 (91h:05016)
18.: A.M. Garsia and I. Gessel, Permutation statistics and partitions, Adv. in Math. 31 (1979), 288-305. MR 532836 (80e:05013)
19.: I.M. Gessel and C. Reutenauer, Counting permutations with given cycle structure and descent set, J. Combin. Theory Ser. A 64 (1993), 189-215. MR 1245159 (95g:05006)
20.: J. Haglund, q-Rook polynomials and matrices over finite fields, Adv. in Appl. Math. 20 (1998), 450-487. MR 1612854 (99f:05004)
21.: D. Knuth, The Art of Computer Programming, Vol. 3. Sorting and Searching, Second Edition, Addison-Wesley, Reading, MA, 1998. MR 0445948 (56:4281)
22.: P.A. MacMahon, Combinatory Analysis, 2 volumes, Cambridge University Press, London, 1915-1916. Reprinted by Chelsea, New York, 1960. MR 0141605 (25:5003)
23.: 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
24.: D. Perrin, Factorizations of Free Monoids, in M. Lothaire, Combinatorics on Words, Ch. 5, Encyclopedia of Math. and its Appl., Vol. 17, Addison-Wesley, Reading, MA, 1983. MR 675953 (84g:05002)
25.: C. Procesi, The toric variety associated to Weyl chambers, Mots, 153-161, Lang. Raison. Calc., Hermès, Paris, 1990. MR 1252661 (94k:14045)
26.: A. Ram, J. Remmel, and T. Whitehead, Combinatorics of the -basis of symmetric functions, J. Combin. Theory Ser. A 76 (1996), 231-271. MR 1416016 (98g:05151)
27.: D. Rawlings, Enumeration of permutations by descents, idescents, imajor index, and basic components, J. Combin. Theory Ser. A 36 (1984), 1-14. MR 728499 (85k:05013)
28.: O. Rodrigues, Note sur les inversions, ou derangements produits dans les permutations, Journal de Mathematiques 4 (1839), 236-240.
29.: M. Skandera, An Eulerian partner for inversions, Sém. Lothar. Combin. 46 (2001/02), Art. B46d, 19 pp. (electronic). MR 1848722 (2002g:05010)
30.: R.P. Stanley, Ordered structures and partitions, Memoirs Amer. Math. Soc. 119 (1972). MR 0332509 (48:10836)
31.: R.P. Stanley, Binomial posets, Möbius inversion, and permutation enumeration, J. Combinatorial Theory Ser. A 20 (1976), 336-356. MR 0409206 (53:12968)
32.: R.P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Graph theory and its applications: East and West (Jinan, 1986), 500-535, Ann. New York Acad. Sci., 576, New York Acad. Sci., New York, 1989. MR 1110850 (92e:05124)
33.: R.P. Stanley, Enumerative combinatorics. Vol. 2. Cambridge Studies in Advanced Mathematics, 62. Cambridge University Press, Cambridge, 1999. MR 1676282 (2000k:05026)
34.: R.P. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Advances in Math. 111 (1995), 166-194. MR 1317387 (96b:05174)
35.: J.R. Stembridge, Eulerian numbers, tableaux, and the Betti numbers of a toric variety, Discrete Math. 99 (1992), 307-320. MR 1158793 (93f:05103)
36.: J.R. Stembridge, Some permutation representations of Weyl groups associated with the cohomology of toric varieties, Adv. Math. 106 (1994), 244-301. MR 1279220 (95f:20011)
37.: 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.
38.: M.L. Wachs, An involution for signed Eulerian numbers, Discrete Math. 99 (1992), 59-62. MR 1158780 (93e:11030b)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|