Decreasing Subsequences in Permutations and Wilf Equivalence for Involutions

In a recent paper, Backelin, West and Xin describe a map φ^* that recursively replaces all occurrences of the pattern k... 21 in a permutation σ by occurrences of the pattern (k−1)... 21 k. The resulting permutation φ^*(σ) contains no decreasing subsequence of length k. We prove that, rather unexpectedly, the map φ^* commutes with taking the inverse of a permutation. In the BWX paper, the definition of φ^* is actually extended to full rook placements on a Ferrers board (the permutations correspond to square boards), and the construction of the map φ^* is the key step in proving the following result. Let T be a set of patterns starting with the prefix 12... k. Let T′ be the set of patterns obtained by replacing this prefix by k... 21 in every pattern of T. Then for all n, the number of permutations of the symmetric group _n that avoid T equals the number of permutations of _n that avoid T′. Our commutation result, generalized to Ferrers boards, implies that the number of involutions of _n that avoid T is equal to the number of involutions of _n avoiding T′, as recently conjectured by Jaggard. Both authors were partially supported by the European Commission's IHRP Programme, grant HPRN-CT-2001-00272, “Algebraic Combinatorics in Europe”