Extending from bijections between marked occurrences of patterns to all occurrences of patterns
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2012-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3098/pdf |
| _version_ | 1797270270627545088 |
|---|---|
| author | Jeffrey Remmel Mark Tiefenbruck |
| author_facet | Jeffrey Remmel Mark Tiefenbruck |
| author_sort | Jeffrey Remmel |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:01:36Z |
| format | Article |
| id | doaj.art-3da9854d6bc84387b08696c96fb7beb3 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:01:36Z |
| publishDate | 2012-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-3da9854d6bc84387b08696c96fb7beb32024-03-07T14:51:45ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502012-01-01DMTCS Proceedings vol. AR,...Proceedings10.46298/dmtcs.30983098Extending from bijections between marked occurrences of patterns to all occurrences of patternsJeffrey Remmel0Mark Tiefenbruck1Department of Mathematics [Univ California San Diego]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.https://dmtcs.episciences.org/3098/pdfbijectionpermutation statisticsgenerating functionpartially marked pattern family[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Jeffrey Remmel Mark Tiefenbruck Extending from bijections between marked occurrences of patterns to all occurrences of patterns Discrete Mathematics & Theoretical Computer Science bijection permutation statistics generating function partially marked pattern family [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | Extending from bijections between marked occurrences of patterns to all occurrences of patterns |
| title_full | Extending from bijections between marked occurrences of patterns to all occurrences of patterns |
| title_fullStr | Extending from bijections between marked occurrences of patterns to all occurrences of patterns |
| title_full_unstemmed | Extending from bijections between marked occurrences of patterns to all occurrences of patterns |
| title_short | Extending from bijections between marked occurrences of patterns to all occurrences of patterns |
| title_sort | extending from bijections between marked occurrences of patterns to all occurrences of patterns |
| topic | bijection permutation statistics generating function partially marked pattern family [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/3098/pdf |
| work_keys_str_mv | AT jeffreyremmel extendingfrombijectionsbetweenmarkedoccurrencesofpatternstoalloccurrencesofpatterns AT marktiefenbruck extendingfrombijectionsbetweenmarkedoccurrencesofpatternstoalloccurrencesofpatterns |