Combinatorial Statistics on Alternating Permutations
Serge Dulucq1
and Rodica Simion2
1Université Bordeaux I LaBRI 351 cours de la Libération 30455 Talence France
2The George Washington University Department of Mathematics Washington, DC 20052
2The George Washington University Department of Mathematics Washington, DC 20052
DOI: 10.1023/A:1008689811936
Abstract
We consider two combinatorial statistics on permutations. One is the genus. The other, [^(\text des)] \widehat{{\text{des}}} , is defined for alternating permutations, as the sum of the number of descents in the subwords formed by the peaks and the valleys. We investigate the distribution of [^(\text des)] \widehat{{\text{des}}} on genus zero permutations and Baxter permutations. Our q-enumerative results relate the [^(\text des)] \widehat{{\text{des}}} statistic to lattice path enumeration, the rank generating function and characteristic polynomial of noncrossing partition lattices, and polytopes obtained as face-figures of the associahedron.
Pages: 169–191
Keywords: lattice path; permutation; associahedron; Catalan; schröder
Full Text: PDF
References
1. G. Andrews, “A theorem on reciprocal polynomials with applications to permutations and compositions,” Amer. Math. Monthly 82 (1975), 830-833.
2. G. Baxter, “On fixed points of the composite of commuting functions,” Proc. Amer. Math. Soc. 15 (1967), 851-855.
3. A. Bj\ddot orner, “Shellable and Cohen-Macaulay partially ordered sets,” Trans. Amer. Math. Soc. 260 (1980), 159-183.
4. A. Bj\ddot orner, A. Garsia, and R. Stanley, “An introduction to Cohen-Macaulay partially ordered sets,” in Ordered Sets (NATO Adv. Study Inst. Ser. C: Math. Phys. Sci.), Ivan Rival (Ed.), Reidel, Dordrecht/Boston, 1982.
5. J. Bonin, L. Shapiro, and R. Simion, “Some q-analogues of the Schr\ddot oder numbers arising from combinatorial statistics on lattice paths,” J. Stat. Planning and Inference 34 (1993), 35-55.
6. F. Chung, R. Graham, V. Hoggatt, and M. Kleiman, “The number of Baxter permutations,” J. Combin. Theory Series A 24 (1978), 382-394.
7. L. Comtet, Advanced Combinatorics, Reidel, Dordrecht, 1974.
8. R. Cori, “Un code pour les graphes planaires et ses applications,” Asterisque 27, Société Mathématique de France, 1975.
9. R. Cori, S. Dulucq, and X. Viennot, “Shuffle of parenthesis systems and Baxter permutations,” J. Combin. Theory Series A 43 (1986), 1-22.
10. R. Cori and A. Machi, “Maps, hypermaps and their automorphisms: A survey, I, II, III,” Exposition. Math. 10 (1992), 403-427, 429-447, 449-467. P1: JSN/PCY P2: JVS Journal of Algebraic Combinatorics KL600-04-Dulucq June 30, 1998 10:14 COMBINATORIAL STATISTICS ON PERMUTATIONS 191
11. M. Delest, “Algebraic languages: A bridge between combinatorics and computer science,” in Algebraic Combinatorics-Formal Power Series and Algebraic Combinatorics/Séries Formelles et Combinatoire Algébrique 1994, L. Billera, C. Greene, R. Simion, and R. Stanley (Eds.), AMS/DIMACS, 24 (1996), 71-87.
12. P. Edelman, “Multichains, noncrossing partitions and trees,” Discr. Math. 40 (1982), 171-179.
13. P. Edelman and R. Simion, “Chains in the lattice of non-crossing partitions,” Discrete Math. 126 (1994), 107-119.
14. D. Jackson, “The lattice of noncrossing partitions and the Birkhoff-Lewis equations,” Waterloo Research Report #89-34, 1989, and European J. Combin. 15 (1994), 245-250.
15. G. Kreweras, “Sur les partitions noncroisées d'un cycle,” Discrete Math. 1 (1972), 333-350.
16. C. Lee, “The associahedron and triangulations of the n-gon,” European J. Combin. 10 (1989), 551-560.
17. C.L. Mallows, “Baxter permutations rise again,” J. Combin. Theory Series A 27 (1979), 394-396.
18. R. Mullin, “The enumeration of Hamiltonian polygons,” Pacific J. Math. 16 (1966), 139-145.
19. I. Niven, “A combinatorial problem of finite sequences,” Nieuw Arch. Wisk. 16 (1968), 116-123.
20. D.G. Rogers and L. Shapiro, “Dequeues, trees, and lattice paths,” in Lecture Notes in Mathematics, K.L. McAvaney (Ed.), Vol. 884, pp. 293-303, Springer-Verlag, New York, 1981.
21. R. Simion and D. Ullman, “On the structure of the lattice of noncrossing partitions,” Discrete Math. 98 (1991), 193-206.
22. R. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth & Brooks/Cole, Monterey, California, 1986.
23. W.T. Tutte, “A census of Hamiltonian polygons,” Canad. J. Math. 14 (1962), 402-417.
24. T.R.S. Walsh and A.B. Lehman, “Counting rooted maps by genus, I, II, III,” J. Combin. Theory 13 (1972), 122-141, 192-218, and 18 (1975), 259.
25. J.W.T. Youngs, “Minimal imbeddings and the genus of a graph,” J. Math. Mech. 12 (1963), 303-315.
26. G. Ziegler, “Lectures on polytopes,” Graduate Texts in Mathematics # 152, Springer-Verlag, New York, 1995.
2. G. Baxter, “On fixed points of the composite of commuting functions,” Proc. Amer. Math. Soc. 15 (1967), 851-855.
3. A. Bj\ddot orner, “Shellable and Cohen-Macaulay partially ordered sets,” Trans. Amer. Math. Soc. 260 (1980), 159-183.
4. A. Bj\ddot orner, A. Garsia, and R. Stanley, “An introduction to Cohen-Macaulay partially ordered sets,” in Ordered Sets (NATO Adv. Study Inst. Ser. C: Math. Phys. Sci.), Ivan Rival (Ed.), Reidel, Dordrecht/Boston, 1982.
5. J. Bonin, L. Shapiro, and R. Simion, “Some q-analogues of the Schr\ddot oder numbers arising from combinatorial statistics on lattice paths,” J. Stat. Planning and Inference 34 (1993), 35-55.
6. F. Chung, R. Graham, V. Hoggatt, and M. Kleiman, “The number of Baxter permutations,” J. Combin. Theory Series A 24 (1978), 382-394.
7. L. Comtet, Advanced Combinatorics, Reidel, Dordrecht, 1974.
8. R. Cori, “Un code pour les graphes planaires et ses applications,” Asterisque 27, Société Mathématique de France, 1975.
9. R. Cori, S. Dulucq, and X. Viennot, “Shuffle of parenthesis systems and Baxter permutations,” J. Combin. Theory Series A 43 (1986), 1-22.
10. R. Cori and A. Machi, “Maps, hypermaps and their automorphisms: A survey, I, II, III,” Exposition. Math. 10 (1992), 403-427, 429-447, 449-467. P1: JSN/PCY P2: JVS Journal of Algebraic Combinatorics KL600-04-Dulucq June 30, 1998 10:14 COMBINATORIAL STATISTICS ON PERMUTATIONS 191
11. M. Delest, “Algebraic languages: A bridge between combinatorics and computer science,” in Algebraic Combinatorics-Formal Power Series and Algebraic Combinatorics/Séries Formelles et Combinatoire Algébrique 1994, L. Billera, C. Greene, R. Simion, and R. Stanley (Eds.), AMS/DIMACS, 24 (1996), 71-87.
12. P. Edelman, “Multichains, noncrossing partitions and trees,” Discr. Math. 40 (1982), 171-179.
13. P. Edelman and R. Simion, “Chains in the lattice of non-crossing partitions,” Discrete Math. 126 (1994), 107-119.
14. D. Jackson, “The lattice of noncrossing partitions and the Birkhoff-Lewis equations,” Waterloo Research Report #89-34, 1989, and European J. Combin. 15 (1994), 245-250.
15. G. Kreweras, “Sur les partitions noncroisées d'un cycle,” Discrete Math. 1 (1972), 333-350.
16. C. Lee, “The associahedron and triangulations of the n-gon,” European J. Combin. 10 (1989), 551-560.
17. C.L. Mallows, “Baxter permutations rise again,” J. Combin. Theory Series A 27 (1979), 394-396.
18. R. Mullin, “The enumeration of Hamiltonian polygons,” Pacific J. Math. 16 (1966), 139-145.
19. I. Niven, “A combinatorial problem of finite sequences,” Nieuw Arch. Wisk. 16 (1968), 116-123.
20. D.G. Rogers and L. Shapiro, “Dequeues, trees, and lattice paths,” in Lecture Notes in Mathematics, K.L. McAvaney (Ed.), Vol. 884, pp. 293-303, Springer-Verlag, New York, 1981.
21. R. Simion and D. Ullman, “On the structure of the lattice of noncrossing partitions,” Discrete Math. 98 (1991), 193-206.
22. R. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth & Brooks/Cole, Monterey, California, 1986.
23. W.T. Tutte, “A census of Hamiltonian polygons,” Canad. J. Math. 14 (1962), 402-417.
24. T.R.S. Walsh and A.B. Lehman, “Counting rooted maps by genus, I, II, III,” J. Combin. Theory 13 (1972), 122-141, 192-218, and 18 (1975), 259.
25. J.W.T. Youngs, “Minimal imbeddings and the genus of a graph,” J. Math. Mech. 12 (1963), 303-315.
26. G. Ziegler, “Lectures on polytopes,” Graduate Texts in Mathematics # 152, Springer-Verlag, New York, 1995.