Equipopularity Classes of 132-Avoiding Permutations
The popularity of a pattern p in a set of permutations is the sum of the number of copies of p in each permutation of the set. We study pattern popularity in the set of 132-avoiding permutations. Two patterns are equipopular if, for all n, they have the same popularity in the set of length-n 132-avo...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Electronic Journal of Combinatorics
2014
|
| Online Access: | http://hdl.handle.net/1721.1/89795 |
| _version_ | 1811083632010330112 |
|---|---|
| author | Chua, Lynn Sankar, Krishanu Roy |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Chua, Lynn Sankar, Krishanu Roy |
| author_sort | Chua, Lynn |
| collection | MIT |
| description | The popularity of a pattern p in a set of permutations is the sum of the number of copies of p in each permutation of the set. We study pattern popularity in the set of 132-avoiding permutations. Two patterns are equipopular if, for all n, they have the same popularity in the set of length-n 132-avoiding permutations. There is a well-known bijection between 132-avoiding permutations and binary plane trees. The spines of a binary plane tree are defined as the connected components when all edges connecting left children to their parents are deleted, and the spine structure is the sorted sequence of lengths of the spines. Rudolph shows that patterns of the same length are equipopular if their associated binary plane trees have the same spine structure. We prove the converse of this result using the method of generating functions, which gives a complete classification of 132-avoiding permutations into equipopularity classes. |
| first_indexed | 2024-09-23T12:36:09Z |
| format | Article |
| id | mit-1721.1/89795 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:36:09Z |
| publishDate | 2014 |
| publisher | Electronic Journal of Combinatorics |
| record_format | dspace |
| spelling | mit-1721.1/897952022-09-28T08:55:48Z Equipopularity Classes of 132-Avoiding Permutations Chua, Lynn Sankar, Krishanu Roy Massachusetts Institute of Technology. Department of Mathematics Chua, Lynn The popularity of a pattern p in a set of permutations is the sum of the number of copies of p in each permutation of the set. We study pattern popularity in the set of 132-avoiding permutations. Two patterns are equipopular if, for all n, they have the same popularity in the set of length-n 132-avoiding permutations. There is a well-known bijection between 132-avoiding permutations and binary plane trees. The spines of a binary plane tree are defined as the connected components when all edges connecting left children to their parents are deleted, and the spine structure is the sorted sequence of lengths of the spines. Rudolph shows that patterns of the same length are equipopular if their associated binary plane trees have the same spine structure. We prove the converse of this result using the method of generating functions, which gives a complete classification of 132-avoiding permutations into equipopularity classes. Massachusetts Institute of Technology. Department of Mathematics 2014-09-18T14:47:15Z 2014-09-18T14:47:15Z 2014-03 2013-08 Article http://purl.org/eprint/type/JournalArticle 1077-8926 http://hdl.handle.net/1721.1/89795 Chua, Lynn, and Krishanu Roy Sankar. "Equipopularity Classes of 132-Avoiding Permutations." Electronic Journal of Combinatorics, Volume 21, Issue 1 (2014). en_US http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p59 Electronic Journal of Combinatorics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Electronic Journal of Combinatorics Electronic Journal of Combinatorics |
| spellingShingle | Chua, Lynn Sankar, Krishanu Roy Equipopularity Classes of 132-Avoiding Permutations |
| title | Equipopularity Classes of 132-Avoiding Permutations |
| title_full | Equipopularity Classes of 132-Avoiding Permutations |
| title_fullStr | Equipopularity Classes of 132-Avoiding Permutations |
| title_full_unstemmed | Equipopularity Classes of 132-Avoiding Permutations |
| title_short | Equipopularity Classes of 132-Avoiding Permutations |
| title_sort | equipopularity classes of 132 avoiding permutations |
| url | http://hdl.handle.net/1721.1/89795 |
| work_keys_str_mv | AT chualynn equipopularityclassesof132avoidingpermutations AT sankarkrishanuroy equipopularityclassesof132avoidingpermutations |