Expected patterns in permutation classes

MaRDI QIDQ456387zbMATH OpenFDO

Authors Cheyne Homberger

Publication date 24 October 2012

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

Full work available at URL https://arxiv.org/abs/1206.0320, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i3p43

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

Dyck pathspatternspermutations

Mathematics Subject Classification ID

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

Abstract: In the set of all patterns in $S_n$, it is clear that each k-pattern occurs equally often. If we instead restrict to the class of permutations avoiding a specific pattern, the situation quickly becomes more interesting. Mikl'os B'ona recently proved that, surprisingly, if we consider the class of permutations avoiding the pattern 132, all other non-monotone patterns of length 3 are equally common. In this paper we examine the class $Av(123)$, and give exact formula for the occurrences of each length 3 pattern. While this class does not break down as nicely as $Av(132)$, we find some interesting similarities between the two and prove that the number of 231 patterns is the same in each.

Review text

Summary: Each length \(k\) pattern occurs equally often in the set \(S_n\) of all permutations of length \(n\), but the same is not true in general for a proper subset of \(S_n\). \textit{M. Bóna} [Electron. J. Comb. 19, No. 1, Research Paper P62, 11 p., electronic only (2012; Zbl 1243.05006)] recently proved that if we consider the set of \(n\)-permutations avoiding the pattern 132, all other non-monotone patterns of length 3 are equally common. In this paper we focus on the set \(\operatorname{Av}_n (123)\) of \(n\)-permutations avoiding \(123\), and give exact formulae for the occurrences of each length 3 pattern. While this set does not have the same symmetries as \(\operatorname{Av}_n (132)\), we find several similarities between the two and prove that the number of 231 patterns is the same in each.

Recommendations

• Patterns in random permutations
• Permutation patterns and statistics
• Permutation classes
• The patterns of permutations
• Permutation tableaux and permutation patterns
• Generalized permutation patterns and a classification of the Mahonian statistics
• Patterns in random permutations avoiding some sets of multiple patterns
• Permutation statistics and multiple pattern avoidance
• Patterns in random permutations avoiding some other patterns
• Permutations with fixed pattern densities

Cited in

(19)

• The Brownian limit of separable permutations
• The equidistribution of some length-three vincular patterns on \(S_n(132)\)
• Pattern popularity in 132-avoiding permutations
• Pattern statistics in faro words and permutations
• Universal limits of substitution-closed permutation classes
• Popularity of patterns over \(d\)-equivalence classes of words and permutations
• Equipopularity classes in the separable permutations
• Counting pattern avoiding permutations by number of movable letters
• The absence of a pattern and the occurrences of another
• scientific article; zbMATH DE number 1375582 (Why is no real title available?)
• The shape of random pattern-avoiding permutations
• Equipopularity classes of 132-avoiding permutations
• Refining enumeration schemes to count according to permutation statistics
• Classical pattern distributions in \(\mathcal{S}_n(132)\) and \(\mathcal{S}_n(123)\)
• Patterns in random permutations avoiding the pattern 132
• scientific article; zbMATH DE number 7662504 (Why is no real title available?)
• The infinite limit of separable permutations
• Clustering of consecutive numbers in permutations avoiding a pattern of length three or avoiding a finite number of simple patterns
• Descent distribution on Catalan words avoiding a pattern of length at most three

This page was built for publication: Expected patterns in permutation classes

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