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 boundariesConference paper

Authors: Sergi Elizalde ORCID1; Martin Rubey 2

  • 1 Department of Mathematics [Dartmouth]
  • 2 Institut für Diskrete Mathematik und Geometrie [Wien]

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]
Funding:
    Source : OpenAIRE Graph
  • Pattern avoidance in dynamical systems; Funder: National Science Foundation; Code: 1001046

Consultation statistics

This page has been seen 351 times.
This article's PDF has been downloaded 567 times.