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 $\varphi ^{*}$ that recursively replaces all occurrences of the pattern $k\dots 21$ in a permutation $\sigma $by occurrences of the pattern $( k - 1)\dots 21 k$. The resulting permutation $\varphi ^{*}(\sigma )$ contains no decreasing subsequence of length $k$. We prove that, rather unexpectedly, the map $\varphi ^{*}$ commutes with taking the inverse of a permutation. In the BWX paper, the definition of $\varphi ^{*}$ is actually extended to full rook placements on a Ferrers board (the permutations correspond to square boards), and the construction of the map $\varphi ^{*}$ 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 {\cal S} _{ n}$ that avoid $T$ equals the number of permutations of $S {\cal S} _{ n}$ that avoid $T^{\prime}$.

Détail

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