Decreasing subsequences in permutations and Wilf equivalence
by
Astrid Reifegerste
Universität Hannover

In a recent paper, Backelin, West and Xin describe a map f that recursively replaces all occurrences of the pattern k(k-1)¼1 in a permutation by occurrences of the pattern (k-1)¼1k. The resulting permutation contains no decreasing subsequence of length k. Extending the definition to full rook placements on a Ferrers board, the map can be used to prove the Wilf equivalence of 12¼kt and k¼21t for any pattern t. We give a direct description of the bijection f on which some phenomena (as commutability with taking the inverse permutation) become clear.

Date received: March 29, 2005