Pattern avoidance in partial permutations
The paper deals with pattern-avoidance in partial permutations. A \textit{partial permutation} of size \(n\) with \(k\) holes is a word such that each symbol from the set \(\{1, 2,\dots,n - k\}\) appears exactly once and the remaining \(k\) symbols are ``holes. The paper extends many well-known results on Wilf equivalence of permutation patterns to partial permutations with an arbitrary number of holes. In particular, the authors give refinements of earlier results due to \textit{J. Backelin, J. West} and \textit{G. Xin} [``Wilf-equivalence for singleton classes, Adv. Appl. Math. 38, No.\,2, 133--148 (2007; Zbl 1127.05002)] and \textit{Z. E. Stankova-Frenkel} and \textit{J. West} [``Explicit enumeration of 321, hexagon-avoiding permutations, Discrete Math. 280, No.\,1--3, 165--189 (2004; Zbl 1041.05003)], respectively. More precisely, they show that the patterns \(123 \cdots m\tau\) and \(m(m-1)\cdots21\tau\) are strongly Wilf-equivalent in the set of partial permutations, where \(\tau\) is any permutation of \(\{m+1, \dots, t \}\) and the patterns \(312\tau\) and \(231\tau\) are strongly Wilf-equivalent in the set of partial permutations, where \(\tau\) is a permutation of \(\{4,5,\dots,r\}\). Moreover, the authors find a connection between Baxter permutations of size \(k\) and partial permutations with \(k-2\) holes. Also, they enumerate the partial permutations of size \(n\) with \(k\) holes avoiding a given pattern of length at most four, for each \(n \geq k \geq1\).
- Pattern avoidance in partial permutations (extended abstract)
- Partial permutations avoiding pairs of patterns
- On Wilf equivalence for alternating permutations
- A new class of Wilf-equivalent permutations
- Completion of the Wilf-classification of 3-5 pairs using generating trees
- Generating-tree isomorphisms for pattern-avoiding involutions
- Pattern avoidance of \([4,k]\)-pairs in circular permutations
- Wilf classification of three and four letter signed patterns
- Wilf classes of pairs of permutations of length 4
- Beyond alternating permutations: pattern avoidance in Young diagrams and tableaux
- On universal partial words
- Statistics of partial permutations via Catalan matrices
- Classical length-5 pattern-avoiding permutations
- On pattern-avoiding Fishburn permutations
- Permutation statistics and multiple pattern avoidance
- Pattern avoidance of generalized permutations
- Pattern avoidance in multiset permutations: bijective proof
- Pattern avoidance in flattened permutations
- scientific article; zbMATH DE number 5831716 (Why is no real title available?)
- Partial permutations avoiding pairs of patterns
- Shape-Wilf-equivalences for vincular patterns
- Pattern avoidance in partial permutations (extended abstract)
- On the sub-permutations of pattern avoiding permutations
- Partial matchings and pattern avoidance
- Pattern avoidance and dominating compositions
- Vincular pattern avoidance on cyclic permutations
- Pattern avoidance by even permutations
- Partial permutations comparison, maintenance and applications
This page was built for publication: Pattern avoidance in partial permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q625391)
