A New Class of Wilf-Equivalent Permutations

Abstract

For about 10 years, the classification of permutation patterns was thought completed up to length 6. In this paper, we establish a new class of Wilf-equivalent permutation patterns, namely, (n-1,n-2,n,tau)~(n-2,n,n-1,tau) for any tau in S_{n-3}. In particular, at level n=6, this result includes the only missing equivalence (546213)~(465213), and for n=7 it completes the classification of permutation patterns by settling all remaining cases in S_7.

20 pages, 14 figures, corrected typo

Cited by in corpus (5)

• On the Wilf-Stanley limit of 4231-avoiding permutations and a conjecture of Arratia
• Shape-Wilf-equivalences for vincular patterns
• Classical and consecutive pattern avoidance in rooted forests
• Fillings of skew shapes avoiding diagonal patterns
• The 26 Wilf-equivalence classes of length five quasi-consecutive patterns