DMTCS Proceedings, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)

Font Size:  Small  Medium  Large

Bijections for lattice paths between two boundaries

Sergi Elizalde, Martin Rubey

Abstract


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.
Résumé. On montre que, sur l'ensemble des chemins avec des pas N=(0,1) et E=(1,0) qui se trouvent entre deux chemins donnés B et T, les deux statistiques ``nombre des pas E en commun avec B" et ``nombre des pas E en commun avec T" ont une distribution conjointe symétrique. On donne une involution qui échange ces deux statistiques, préserve quelques autres paramètres additionelles, et admet une généralisation à des chemins avec des pas S=(0, -1) dans des positions données. On montre aussi un autre résultat d'équidistribution similaire, lié au polynôme de Tutte d'un matroïde. Finalement, on étend les deux théorèmes à k-tuples de chemins entre deux frontières, et on donne quelques applications aux chemins de Dyck, en généralisant un résultat de Deutsch, et aux permutations avec des motifs exclus.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional