Jeffrey Remmel ; Mark Tiefenbruck - Extending from bijections between marked occurrences of patterns to all occurrences of patterns

dmtcs:3098 - 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.3098
Extending from bijections between marked occurrences of patterns to all occurrences of patternsArticle

Authors: Jeffrey Remmel 1; Mark Tiefenbruck 1

  • 1 Department of Mathematics [Univ California San Diego]

We consider two recent open problems stating that certain statistics on various sets of combinatorial objects are equidistributed. The first, posed by Anders Claesson and Svante Linusson, relates nestings in matchings on $\{1,2,\ldots,2n\}$ to occurrences of a certain pattern in permutations in $S_n$. The second, posed by Miles Jones and Jeffrey Remmel, relates occurrences of a large class of consecutive permutation patterns to occurrences of the same pattern in the cycles of permutations. We develop a general method that solves both of these problems and many more. We further employ the Garsia-Milne involution principle to obtain purely bijective proofs of these results.


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: bijection, permutation statistics, generating function, partially marked pattern family,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 285 times.
This article's PDF has been downloaded 264 times.