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?)


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