Wilf classes of pairs of permutations of length 4

Abstract

Sn(π1 π2, . . . , πr) denotes the set of permutations of length n that have no subsequence with the same order relations as any of the πi. In this paper we show that Sn(1342, 2143)| = |Sn(3142, 2341)| and Sn(1342, 3124)| = |Sn(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 |Sn(1342, 2143)|. Show more