How to decompose a permutation into a pair of labeled Dyck paths by playing a game
HTML articles powered by AMS MathViewer
- by Louis J. Billera, Lionel Levine and Karola Mészáros PDF
- Proc. Amer. Math. Soc. 143 (2015), 1865-1873
Abstract:
We give a bijection between permutations of $1,\ldots ,2n$ and certain pairs of Dyck paths with labels on the down steps. The bijection arises from a game in which two players alternate selecting from a set of $2n$ items: the permutation encodes the players’ preference ordering of the items, and the Dyck paths encode the order in which items are selected under optimal play. We enumerate permutations by certain new statistics, AA inversions and BB inversions, which have natural interpretations in terms of the game. We derive identities such as \[ \sum _{p} \prod _{i=1}^n q^{h_i -1} [h_i]_q = [1]_q [3]_q \cdots [2n-1]_q \] where the sum is over all Dyck paths $p$ of length $2n$, and $h_1,\ldots ,h_n$ are the heights of the down steps of $p$.References
- Steven J. Brams and Philip D. Straffin Jr., Prisoner’s dilemma and professional sports drafts, Amer. Math. Monthly 86 (1979), no. 2, 80–88. MR 520570, DOI 10.2307/2321942
- Denis Chebikin, Variations on descents and inversions in permutations, Electron. J. Combin. 15 (2008), no. 1, Research Paper 132, 34. MR 2448882
- Findstat: The combinatorial statistic finder, http://www.findstat.org (2013)
- Jean Françon and Gérard Viennot, Permutations selon leurs pics, creux, doubles montées et double descentes, nombres d’Euler et nombres de Genocchi, Discrete Math. 28 (1979), no. 1, 21–35 (French, with English summary). MR 542933, DOI 10.1016/0012-365X(79)90182-1
- I. P. Goulden and D. M. Jackson, Combinatorial enumeration, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Inc., New York, 1983. With a foreword by Gian-Carlo Rota. MR 702512
- Brian Hopkins and Michael A. Jones, Bruhat orders and the sequential selection of indivisible items, The mathematics of preference, choice and order, Stud. Choice Welf., Springer, Berlin, 2009, pp. 273–285. MR 2648307, DOI 10.1007/978-3-540-79128-7_{1}5
- David A. Kohler and R. Chandrasekaran, A class of sequential games, Operations Res. 19 (1971), 270–277. MR 275897, DOI 10.1287/opre.19.2.270
- Lionel Levine, Scott Sheffield, and Katherine E. Stange, A duality principle for selection games, Proc. Amer. Math. Soc. 141 (2013), no. 12, 4349–4356. MR 3105877, DOI 10.1090/S0002-9939-2013-11707-7
- Lionel Levine and Katherine E. Stange, How to make the most of a shared meal: plan the last bite first, Amer. Math. Monthly 119 (2012), no. 7, 550–565. MR 2956425, DOI 10.4169/amer.math.monthly.119.07.550
- Gérard Viennot, A combinatorial theory for general orthogonal polynomials with extensions and applications, Orthogonal polynomials and applications (Bar-le-Duc, 1984) Lecture Notes in Math., vol. 1171, Springer, Berlin, 1985, pp. 139–157. MR 838979, DOI 10.1007/BFb0076539
Additional Information
- Louis J. Billera
- Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853
- MR Author ID: 36960
- Lionel Levine
- Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853
- MR Author ID: 654666
- Karola Mészáros
- Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853
- MR Author ID: 823389
- Received by editor(s): July 29, 2013
- Published electronically: January 8, 2015
- Additional Notes: The first author was partially supported by the Simons Foundation
The second author was partially supported by NSF DMS-1243606
The third author was partially supported by an NSF Postdoctoral Research Fellowship (DMS 1103933). - Communicated by: Jim Haglund
- © Copyright 2014 by the authors
- Journal: Proc. Amer. Math. Soc. 143 (2015), 1865-1873
- MSC (2010): Primary 05A05, 05A15, 91A10
- DOI: https://doi.org/10.1090/S0002-9939-2015-12427-6
- MathSciNet review: 3314097