Decreasing subsequences in permutations and Wilf equivalence for involutions

Details Decreasing subsequences in permutations and Wilf equivalence for involutions Decreasing subsequences in permutations and Wilf equivalence for involutions

2004-05-17

arxiv.org/abs/math/0405334v1

Journal of Algebraic Combinatorics / Journal of Algebraic Combinatorics An International Journal 22, 4 (2005) 383 - 409

Mathematics

Combinatorics

Scientific paper

In a recent paper, Backelin, West and Xin describe a map $\phi ^*$ that recursively replaces all occurrences of the pattern $k... 21$ in a permutation $\sigma$ by occurrences of the pattern $(k-1)... 21 k$. The resulting permutation $\phi^*(\sigma)$ contains no decreasing subsequence of length $k$. We prove that, rather unexpectedly, the map $\phi ^*$ commutes with taking the inverse of a permutation. In the BWX paper, the definition of $\phi^*$ is actually extended to full rook placements on a Ferrers board (the permutations correspond to square boards), and the construction of the map $\phi^*$ 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.

Affiliated with

Also associated with

No associations

Rating

Decreasing subsequences in permutations and Wilf equivalence for involutions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Decreasing subsequences in permutations and Wilf equivalence for involutions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decreasing subsequences in permutations and Wilf equivalence for involutions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-284932