Wilf-Equivalence For Singleton Classes

. Write p1p2 : : : pm for the permutation matrix ffi p i ;j . Let Sn (M) be the set of n \Theta n permutation matrices which do not contain the m \Theta m permutation matrix M as a submatrix. In [2] Simion and Schmidt show bijectively that jSn(123)j = jSn(213)j. In the present work this is generalised to a bijection between Sn(12 : : : tp t+1 : : : pm) and Sn (t : : : 21p t+1 : : : pm ). This result was established for t = 2 in [5] and for t = 3 in [8]. 1. Introduction and main theorem A permutation matrix of order n is a traversal of the n by n square diagram, in other words a placement of n non-attacking rooks on an n by n board. We can easily generalise this definition of a traversal to boards of general shape, and will do so below. Given a permutation matrix M of order m, a permutation matrix N of order n ? m will be said to contain the smaller matrix if there exist two subsets of the index set [n], R = fr 1 ! r 2 ! \Delta \Delta \Delta ! r m g and C = fc 1 ! c 2 ! \Delta ..