Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

   
 
 

 

How to decompose a permutation into a pair of labeled Dyck paths by playing a game


Authors: Louis J. Billera, Lionel Levine and Karola Mészáros
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
Published electronically: January 8, 2015
MathSciNet review: 3314097
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

$\displaystyle \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 [Enhancements On Off] (What's this?)

  • [1] 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 (80f:90176), https://doi.org/10.2307/2321942
  • [2] Denis Chebikin, Variations on descents and inversions in permutations, Electron. J. Combin. 15 (2008), no. 1, Research Paper 132, 34. MR 2448882 (2009g:05003)
  • [3] Findstat: The combinatorial statistic finder, http://www.findstat.org (2013)
  • [4] 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 (French, with English summary), Discrete Math. 28 (1979), no. 1, 21-35. MR 542933 (81a:05002), https://doi.org/10.1016/0012-365X(79)90182-1
  • [5] I. P. Goulden and D. M. Jackson, Combinatorial enumeration, With a foreword by Gian-Carlo Rota; Wiley-Interscience Series in Discrete Mathematics, A Wiley-Interscience Publication, John Wiley & Sons Inc., New York, 1983. MR 702512 (84m:05002)
  • [6] 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 (2012e:91183), https://doi.org/10.1007/978-3-540-79128-7_15
  • [7] David A. Kohler and R. Chandrasekaran, A class of sequential games, Operations Res. 19 (1971), 270-277. MR 0275897 (43 #1650)
  • [8] 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, https://doi.org/10.1090/S0002-9939-2013-11707-7
  • [9] 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, https://doi.org/10.4169/amer.math.monthly.119.07.550
  • [10] 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 (87g:42046), https://doi.org/10.1007/BFb0076539

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05A05, 05A15, 91A10

Retrieve articles in all journals with MSC (2010): 05A05, 05A15, 91A10


Additional Information

Louis J. Billera
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853

Lionel Levine
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853

Karola Mészáros
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853

DOI: https://doi.org/10.1090/S0002-9939-2015-12427-6
Keywords: AA inversion, BB inversion, Dyck path, fair division, Hermite history, $q$-analogue
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
Article copyright: © Copyright 2014 by the authors

American Mathematical Society