## Sergi Elizalde ; Martin Rubey - Bijections for lattice paths between two boundaries

dmtcs:3086 - Discrete Mathematics & Theoretical Computer Science, January 1, 2012, DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012) - https://doi.org/10.46298/dmtcs.3086
Bijections for lattice paths between two boundaries

Authors: Sergi Elizalde ; Martin Rubey

We prove that on the set of lattice paths with steps $N=(0,1)$ and $E=(1,0)$ that lie between two boundaries $B$ and $T$, the two statistics number of $E$ steps shared with $B$' and number of $E$ steps shared with $T$' have a symmetric joint distribution. We give an involution that switches these statistics, preserves additional parameters, and generalizes to paths that contain steps $S=(0,-1)$ at prescribed $x$-coordinates. We also show that a similar equidistribution result for other path statistics follows from the fact that the Tutte polynomial of a matroid is independent of the order of its ground set. Finally, we extend the two theorems to $k$-tuples of paths between two boundaries, and we give some applications to Dyck paths, generalizing a result of Deutsch, and to pattern-avoiding permutations.

Volume: DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)
Section: Proceedings
Published on: January 1, 2012
Imported on: January 31, 2017
Keywords: lattice path, combinatorial statistic, involution, Tutte polynomial, matroid,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Fundings :
Source : OpenAIRE Research Graph
• Pattern avoidance in dynamical systems; Funder: National Science Foundation; Code: 1001046