Signed words and permutations, I: A fundamental transformation
HTML articles powered by AMS MathViewer
- by Dominique Foata and Guo-Niu Han PDF
- Proc. Amer. Math. Soc. 135 (2007), 31-40 Request permission
Abstract:
The statistics major index and inversion number, usually defined on ordinary words, have their counterparts in signed words, namely the so-called flag-major index and flag-inversion number. We give the construction of a new transformation on those signed words that maps the former statistic onto the latter one. It is proved that the transformation also preserves two other set-statistics: the inverse ligne of route and the lower records.References
- Ron M. Adin and Yuval Roichman, The flag major index and group actions on polynomial rings, European J. Combin. 22 (2001), no. 4, 431–446. MR 1829737, DOI 10.1006/eujc.2000.0469
- Ron M. Adinh, Francesco Brenti, and Yuval Roichman, Descent numbers and major indices for the hyperoctahedral group, Adv. in Appl. Math. 27 (2001), no. 2-3, 210–224. Special issue in honor of Dominique Foata’s 65th birthday (Philadelphia, PA, 2000). MR 1868962, DOI 10.1006/aama.2001.0731
- Riccardo Biagioli, Major and descent statistics for the even-signed permutation group, Adv. in Appl. Math. 31 (2003), no. 1, 163–179. MR 1985826, DOI 10.1016/S0196-8858(02)00561-4
- Riccardo Biagioli and Fabrizio Caselli, Invariant algebras and major indices for classical Weyl groups, Proc. London Math. Soc. (3) 88 (2004), no. 3, 603–631. MR 2044051, DOI 10.1112/S0024611503014552
- Anders Björner and Michelle L. Wachs, Permutation statistics and linear extensions of posets, J. Combin. Theory Ser. A 58 (1991), no. 1, 85–114. MR 1119703, DOI 10.1016/0097-3165(91)90075-R
- N. Bourbaki, Éléments de mathématique. Fasc. XXXIV. Groupes et algèbres de Lie. Chapitre IV: Groupes de Coxeter et systèmes de Tits. Chapitre V: Groupes engendrés par des réflexions. Chapitre VI: systèmes de racines, Actualités Scientifiques et Industrielles [Current Scientific and Industrial Topics], No. 1337, Hermann, Paris, 1968 (French). MR 0240238
- Francesco Brenti, $q$-Eulerian polynomials arising from Coxeter groups, European J. Combin. 15 (1994), no. 5, 417–441. MR 1292954, DOI 10.1006/eujc.1994.1046
- Dominique Foata, On the Netto inversion number of a sequence, Proc. Amer. Math. Soc. 19 (1968), 236–240. MR 223256, DOI 10.1090/S0002-9939-1968-0223256-9
- Dominique Foata and Guo-Niu Han, Signed words and permutations. II. The Euler-Mahonian polynomials, Electron. J. Combin. 11 (2004/06), no. 2, Research Paper 22, 18. MR 2195428
- Dominique Foata and Marcel-Paul Schützenberger, Major index and inversion number of permutations, Math. Nachr. 83 (1978), 143–159. MR 506852, DOI 10.1002/mana.19780830111
- H. O. Foulkes, Tangent and secant numbers and representations of symmetric groups, Discrete Math. 15 (1976), no. 4, 311–324. MR 406810, DOI 10.1016/0012-365X(76)90045-5
- H. O. Foulkes, Eulerian numbers, Newcomb’s problem and representations of symmetric groups, Discrete Math. 30 (1980), no. 1, 3–49. MR 561763, DOI 10.1016/0012-365X(80)90061-8
- Ira Gessel, Generating functions and enumeration of sequences, Ph.D. thesis, Dept. Math., M.I.T., Cambridge, Mass., 111 pp., 1977.
- James E. Humphreys, Reflection groups and Coxeter groups, Cambridge Studies in Advanced Mathematics, vol. 29, Cambridge University Press, Cambridge, 1990. MR 1066460, DOI 10.1017/CBO9780511623646
- Donald E. Knuth, The art of computer programming. Volume 3, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching. MR 0445948
- 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
- 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 10.2307/2370312
- Percy Alexander MacMahon, Combinatory Analysis, vol. 1 and 2, Cambridge, Cambridge Univ. Press, 1915 (Reprinted by Chelsea, New York, 1995).
- Percy Alexander MacMahon, Collected papers. Vol. I, Mathematicians of Our Time, MIT Press, Cambridge, Mass.-London, 1978. Combinatorics; Edited and with a preface by George E. Andrews; With an introduction by Gian-Carlo Rota. MR 514405
- Victor Reiner, Signed permutation statistics, European J. Combin. 14 (1993), no. 6, 553–567. MR 1248063, DOI 10.1006/eujc.1993.1058
- Victor Reiner, Signed permutation statistics and cycle type, European J. Combin. 14 (1993), no. 6, 569–579. MR 1248064, DOI 10.1006/eujc.1993.1059
- Victor Reiner, Upper binomial posets and signed permutation statistics, European J. Combin. 14 (1993), no. 6, 581–588. MR 1248065, DOI 10.1006/eujc.1993.1060
- Victor Reiner, Descents and one-dimensional characters for classical Weyl groups, Discrete Math. 140 (1995), no. 1-3, 129–140. MR 1333715, DOI 10.1016/0012-365X(93)E0179-8
- Victor Reiner, The distribution of descents and length in a Coxeter group, Electron. J. Combin. 2 (1995), Research Paper 25, approx. 20. MR 1359412
- Richard P. Stanley, Ordered structures and partitions, Memoirs of the American Mathematical Society, No. 119, American Mathematical Society, Providence, R.I., 1972. 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 10.1016/0097-3165(76)90028-5
- 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 10.1016/0012-365X(92)90378-S
Additional Information
- Dominique Foata
- Affiliation: Institut Lothaire, 1 rue Murner, F-67000 Strasbourg, France
- Email: foata@math.u-strasbg.fr
- Guo-Niu Han
- Affiliation: I.R.M.A. UMR 7501, Université Louis Pasteur et CNRS, 7 rue René-Descartes, F-67084 Strasbourg, France
- MR Author ID: 272629
- Email: guoniu@math.u-strasbg.fr
- Received by editor(s): April 11, 2005
- Received by editor(s) in revised form: August 4, 2005
- Published electronically: June 29, 2006
- Communicated by: John R. Stembridge
- © Copyright 2006
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc. 135 (2007), 31-40
- MSC (2000): Primary 05A15, 05A30, 05E15
- DOI: https://doi.org/10.1090/S0002-9939-06-08436-X
- MathSciNet review: 2280171
Dedicated: This paper is dedicated to the memory of Percy Alexander MacMahon