Decreasing subsequences in permutations and Wilf equivalence for involutions

Bousquet-Mélou, Mireille ; Steingrímsson, Einar

Journal of Algebraic Combinatorics, Tome 22 (2005) no. 4, pp. 383-409.

Résumé

Summary: In a recent paper, Backelin, West and Xin describe a map ${\phi }^{\ast }$ that recursively replaces all occurrences of the pattern $k\dots 21$ in a permutation $\sigma$by occurrences of the pattern $(k-1)\dots 21k$. The resulting permutation ${\phi }^{\ast }(\sigma )$ contains no decreasing subsequence of length $k$. We prove that, rather unexpectedly, the map ${\phi }^{\ast }$ commutes with taking the inverse of a permutation. In the BWX paper, the definition of ${\phi }^{\ast }$ is actually extended to full rook placements on a Ferrers board (the permutations correspond to square boards), and the construction of the map ${\phi }^{\ast }$ is the key step in proving the following result. Let $T$ be a set of patterns starting with the prefix $12\dots k$. Let $T^{\prime }$ be the set of patterns obtained by replacing this prefix by $k\dots 21$ in every pattern of $T$. Then for all $n$, the number of permutations of the symmetric group $S{\mathcal{S}}_n$ that avoid $T$ equals the number of permutations of $S{\mathcal{S}}_n$ that avoid $T^{\prime }$.

Détail

Mots-clés : keywords pattern avoiding permutations, Wilf equivalence, involutions, decreasing subsequences, prefix exchange