Wilf Classes of Pairs of Permutations of Length 4

Abstract

$S_n(\pi_1,\pi_2,\dots, \pi_r)$ denotes the set of permutations of length $n$ that have no subsequence with the same order relations as any of the $\pi_i$. In this paper we show that $|S_n(1342,2143)|=|S_n(3142,2341)|$ and $|S_n(1342,3124)|=|S_n(1243,2134)|$. These two facts complete the classification of Wilf-equivalence classes for pairs of permutations of length four. In both instances we exhibit bijections between the sets using the idea of a "block", and in the former we find a generating function for $|S_n(1342,2143)|$.