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 ORCID-iD; 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

    Share

    Consultation statistics

    This page has been seen 139 times.
    This article's PDF has been downloaded 362 times.