Equipopularity classes of 132-avoiding permutations

MaRDI QIDQ405164zbMATH OpenFDO

Authors Lynn Chua, Krishanu Roy Sankar

Publication date 4 September 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p59

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

pattern avoidancepermutations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Review text

Summary: 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. \textit{K. Rudolph} [ibid. 20, No. 1, Research Paper P8, 15 p. (2013; Zbl 1267.05013)] 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.

Recommendations

• Pattern popularity in 132-avoiding permutations
• Equipopularity classes in the separable permutations
• Classical pattern distributions in \(\mathcal{S}_n(132)\) and \(\mathcal{S}_n(123)\)
• The equidistribution of some length-three vincular patterns on \(S_n(132)\)
• Expected patterns in permutation classes

Cites work

• Pattern popularity in 132-avoiding permutations
• Surprising symmetries in objects counted by Catalan numbers
• The absence of a pattern and the occurrences of another

Cited in

(7)

• Pattern popularity in 132-avoiding permutations
• Popularity of patterns over \(d\)-equivalence classes of words and permutations
• Equipopularity classes in the separable permutations
• Classification of bijections between 321- and 132-avoiding permutations
• A relation on 132-avoiding permutation patterns
• New equidistributions on plane trees and decompositions of 132-avoiding permutations
• A general theory of Wilf-equivalence for Catalan structures

This page was built for publication: Equipopularity classes of 132-avoiding permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405164)