Decreasing subsequences in permutations and Wilf equivalence for involutions
| dc.creator | Bousquet-Melou, Mireille | |
| dc.creator | Steingrimsson, Einar | |
| dc.date | 2004-05-17 | |
| dc.date.accessioned | 2026-07-07T09:36:45Z | |
| dc.date.available | 2026-07-07T09:36:45Z | |
| dc.description | 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 $\Sn_n$ that avoid $T$ equals the number of permutations of $\Sn_n$ that avoid $T'$. Our commutation result, generalized to Ferrers boards, implies that the number of {\em involutions} of $\Sn_n$ that avoid $T$ is equal to the number of involutions of $\Sn_n$ avoiding $T'$, as recently conjectured by Jaggard. | |
| dc.identifier | https://arxiv.org/abs/math/0405334 | |
| dc.identifier | http://arxiv.org/abs/math/0405334 | |
| dc.identifier | Journal of Algebraic Combinatorics / Journal of Algebraic Combinatorics An International Journal 22, 4 (2005) 383 - 409 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/160229 | |
| dc.subject | Combinatorics | |
| dc.subject | 05A15, 05E15 | |
| dc.title | Decreasing subsequences in permutations and Wilf equivalence for involutions | |
| dc.type | text |