A New Class of Wilf-Equivalent Permutations
Zvezdelina Stankova
and Julian West
DOI: 10.1023/A:1015016625432
Abstract
For about 10 years, the classification up to Wilf equivalence of permutation patterns was thought completed up to length 6. In this paper, we establish a new class of Wilf-equivalent permutation patterns, namely, ( n - 1, n - 2, n, 
) 
( n - 2, n, n - 1, ) for any 
S n -3. In particular, at level n = 6, this result includes the only missing equivalence (546213) (465213), and for n = 7 it completes the classification of permutation patterns by settling all remaining cases in S 7.
) ( n - 2, n, n - 1, ) for any S n -3. In particular, at level n = 6, this result includes the only missing equivalence (546213) (465213), and for n = 7 it completes the classification of permutation patterns by settling all remaining cases in S 7.Pages: 271–290
Keywords: Wilf-equivalent; shape-Wilf-equivalent; restricted patterns; forbidden permutations
Full Text: PDF
References
1. E. Babson and J. West, “The permutations 123 p4 . . . pt and 321 p4 . . . pt are Wilf-equivalent,” Graphs Combin. 16(4) (2000), 373-380.
2. J. Backelin, J. West, and G. Xin, “Wilf-equivalence for singleton classes,” preprint.
3. S. Billey and G. Warrington, “Kashdan-Lusztig polynomials for 321-hexagon-avoiding permutations,” arXiv:math.CO/0005052, 5 May 2000.
4. M. Bóna, “Permutations avoiding certain patterns. The case of length 4 and some generalizations,” Discrete Math. 175 (1997), 55-67.
5. M. Bóna, “The solution of a conjecture of Wilf and Stanley for all layered patterns,” J. Combin. Theory Ser. A, 85 (1999), 96-104.
6. D. Knuth, “Permutations, matrices, and generalized Young tableaux,” Pacific J. of Math. 34 (1970), 709-727.
7. D. Knuth, The Art of Computer Programming, Vol. 3, Addison-Wesley, Reading, MA, 1973.
8. V. Lakshmibai and B. Sandhya, “Criterion for smoothness of Schubert varieties in SL(N)/B,” Proc. Indian Acad. Sci. Math. Sci., 100 (1990), 45-52.
9. L. Lovász, Combinatorial Problems and Exercises, North-Holland, New York, 1979.
10. I. Macdonald, Notes on Schubert Polynomials, Universite du Quebec, 1991.
11. N. Ray and J. West, “Posets of matrices and permutations with forbidden subsequences,” preprint.
12. A. Regev, “Asymptotic values for degrees associated with strips of Young diagrams,” Advances in Math. 41 (1981), 115-136.
13. D. Richards, “Ballot sequences and restricted permutations,” Arts Combinatoria 25 (1988), 83-86.
14. D. Rotem, “On correspondence between binary trees and a certain type of permutation,” Information Processing Letters 4 (1975), 58-61.
15. R. Simion and F. Schmidt, “Restricted permutations,” European J. Combin. 6 (1985), 383-406.
16. Z. Stankova, “Forbidden subsequences,” Discrete Math. 132 (1994), 291-316.
17. Z. Stankova, “Classification of forbidden subsequences of length 4,” European J. Combin. 17 (1996), 501-517.
18. J. West, “Permutations with forbidden subsequences and stack-sortable permutations,” Ph.D. thesis, MIT, 1990.
19. J. West, “Generating trees and the Catalan and Schr\ddot oder numbers,” Discrete Math. 146 (1995), 247-262.
20. J. West, “Generating trees and forbidden subsequences,” Discrete Math. 157 (1996), 363-374.
2. J. Backelin, J. West, and G. Xin, “Wilf-equivalence for singleton classes,” preprint.
3. S. Billey and G. Warrington, “Kashdan-Lusztig polynomials for 321-hexagon-avoiding permutations,” arXiv:math.CO/0005052, 5 May 2000.
4. M. Bóna, “Permutations avoiding certain patterns. The case of length 4 and some generalizations,” Discrete Math. 175 (1997), 55-67.
5. M. Bóna, “The solution of a conjecture of Wilf and Stanley for all layered patterns,” J. Combin. Theory Ser. A, 85 (1999), 96-104.
6. D. Knuth, “Permutations, matrices, and generalized Young tableaux,” Pacific J. of Math. 34 (1970), 709-727.
7. D. Knuth, The Art of Computer Programming, Vol. 3, Addison-Wesley, Reading, MA, 1973.
8. V. Lakshmibai and B. Sandhya, “Criterion for smoothness of Schubert varieties in SL(N)/B,” Proc. Indian Acad. Sci. Math. Sci., 100 (1990), 45-52.
9. L. Lovász, Combinatorial Problems and Exercises, North-Holland, New York, 1979.
10. I. Macdonald, Notes on Schubert Polynomials, Universite du Quebec, 1991.
11. N. Ray and J. West, “Posets of matrices and permutations with forbidden subsequences,” preprint.
12. A. Regev, “Asymptotic values for degrees associated with strips of Young diagrams,” Advances in Math. 41 (1981), 115-136.
13. D. Richards, “Ballot sequences and restricted permutations,” Arts Combinatoria 25 (1988), 83-86.
14. D. Rotem, “On correspondence between binary trees and a certain type of permutation,” Information Processing Letters 4 (1975), 58-61.
15. R. Simion and F. Schmidt, “Restricted permutations,” European J. Combin. 6 (1985), 383-406.
16. Z. Stankova, “Forbidden subsequences,” Discrete Math. 132 (1994), 291-316.
17. Z. Stankova, “Classification of forbidden subsequences of length 4,” European J. Combin. 17 (1996), 501-517.
18. J. West, “Permutations with forbidden subsequences and stack-sortable permutations,” Ph.D. thesis, MIT, 1990.
19. J. West, “Generating trees and the Catalan and Schr\ddot oder numbers,” Discrete Math. 146 (1995), 247-262.
20. J. West, “Generating trees and forbidden subsequences,” Discrete Math. 157 (1996), 363-374.