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

Louis J. Billera, Lionel Levine, Karola Meszaros

We give a bijection between permutations of length 2n and certain pairs of Dyck paths with labels on the down steps. The bijection arises from a game in which two players alternate…