Pattern avoidance in partial permutations (Q625391)

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\).