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.
@article{10_37236_3675,
author = {Lynn Chua and Krishanu Roy Sankar},
title = {Equipopularity classes of 132-avoiding permutations},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {1},
doi = {10.37236/3675},
zbl = {1300.05004},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3675/}
}
TY - JOUR
AU - Lynn Chua
AU - Krishanu Roy Sankar
TI - Equipopularity classes of 132-avoiding permutations
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/3675/
DO - 10.37236/3675
ID - 10_37236_3675
ER -
%0 Journal Article
%A Lynn Chua
%A Krishanu Roy Sankar
%T Equipopularity classes of 132-avoiding permutations
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/3675/
%R 10.37236/3675
%F 10_37236_3675
Lynn Chua; Krishanu Roy Sankar. Equipopularity classes of 132-avoiding permutations. The electronic journal of combinatorics, Tome 21 (2014) no. 1. doi: 10.37236/3675
