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.

Source : oai:HAL:hal-01283135v1

Volume: DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)

Section: Proceedings

Published on: January 1, 2012

Submitted on: January 31, 2017

Keywords: lattice path, combinatorial statistic, involution, Tutte polynomial, matroid,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

This page has been seen 65 times.

This article's PDF has been downloaded 306 times.