Abstract | ||
---|---|---|
We give a bijection between permutations of 1,..., 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 Sigma(p) Pi(n)(i=1) q(hi-1) [h(i)](q) = [1]q[3](q) ... [2n - 1](q) where the sum is over all Dyck paths p of length 2n, and h(1),..., h(n) are the heights of the down steps of p. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1090/S0002-9939-2015-12427-6 | PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY |
Keywords | DocType | Volume |
AA inversion,BB inversion,Dyck path,fair division,Hermite history,q-analogue | Journal | 143 |
Issue | ISSN | Citations |
5 | 0002-9939 | 0 |
PageRank | References | Authors |
0.34 | 4 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Louis J. Billera | 1 | 279 | 57.41 |
Lionel Levine | 2 | 31 | 5.43 |
Karola Mészáros | 3 | 0 | 2.03 |