JOURNAL OF
ALGEBRAIC
COMBINATORICS

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$^{\prime}$ 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 S {\cal S} _n that avoid T equals the number of permutations of S {\cal S} _n that avoid T$^{\prime}$.

1. E. Babson and E. Steingrímsson, “Generalized permutation patterns and a classification of the Mahonian statistics,” Sém. Lothar. Combin., 44:Art. B44b, (2000), 18 pp. (electronic).
2. E. Babson and J. West, “The permutations 123 p4 . . . pm and 321 p4 . . . pm are Wilf-equivalent,” Graphs Combin. 16(4) (2000), 373-380.
3. J. Backelin, J. West, and G. Xin, “Wilf-equivalence for singleton classes,” in Proceeedings of the 13th Conference on Formal Power Series and Algebraic Combinatorics, H. Barcelo and V. Welker (Eds.), Arizona State University, 2001, pp. 29-38 (To appear in Adv. in Appl. Math.).
4. E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani, “Some permutations with forbidden subsequences and their inversion number,” Discrete Math. 234(1-3) (2001), 1-15.
5. M. Bóna, “Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps,” J. Combin. Theory Ser. A 80(2) (1997), 257-272.
6. M. Bousquet-Mélou, “Four classes of pattern-avoiding permutations under one roof: Generating trees with two labels,” Electron. J. Combin. 9(2), (2003).
7. A. Claesson and T. Mansour, “Enumerating permutations avoiding a pair of Babson-Steingrímsson patterns,” Ars Combinatoria, to appear.
8. I. Gessel, “Symmetric functions and P-recursiveness,” J. Combin. Theory Ser. A 53(2) (1990), 257-285.
9. I. Gessel, J. Weinstein, and H.S. Wilf, “Lattice walks in Zd and permutations with no long ascending subsequences,” Electron. J. Combin. 5(1) (1998), 11.
10. D. Gouyou-Beauchamps, “Standard Young tableaux of height 4 and 5,” European J. Combin. 10(1) (1989), 69-82.
11. O. Guibert, “Combinatoire des permutations `a motifs exclus, en liaison avec mots, cartes planaires et tableaux de Young,” Ph.D. thesis, LaBRI, Université Bordeaux 1, 1995.
12. O. Guibert, E. Pergola, and R. Pinzani, “Vexillary involutions are enumerated by Motzkin numbers,” Ann. Comb. 5(2) (2001), 153-174.
13. G. Huet, “Confluent reductions: Abstract properties and applications to term rewriting systems,” J. Assoc. Comput. Mach. 27(4) (1980) 797-821.
14. A.D. Jaggard, “Prefix exchanging and pattern avoidance for involutions,” Electron. J. Combin. 9(2)(2003), 16.
15. S. Kitaev and T. Mansour, “A survey of certain pattern problems,” Preprint, 2004.
16. C. Krattenthaler, “Permutations with restricted patterns and Dyck paths,” Adv. in Appl. Math. 27(2/3) (2001), 510-530.
17. A. Regev, “Asymptotic values for degrees associated with strips of Young diagrams,” Adv. in Math. 41(2) (1981) 115-136.
18. C. Schensted, “Longest increasing and decreasing subsequences,” Canad. J. Math. 13 (1961), 179-191.
19. R. Simion and F.W. Schmidt, “Restricted permutations,” European J. Combin. 6(4) (1985) 383-406.
20. Z.E. Stankova, “Forbidden subsequences,” Discrete Math. 132(1/3) (1994), 291-316.
21. Z.E. Stankova, “Classification of forbidden subsequences of length 4,” European J. Combin. 17(5) (1996), 501-517.
22. Z.E. Stankova and J. West, “A new class of Wilf-equivalent permutations,” J. Algebraic Combin. 15(3) (2002), 271-290.
23. G. Viennot, “Une forme géométrique de la correspondance de Robinson-Schensted,” in Combinatoire et représentation du groupe symétrique (Actes Table Ronde CNRS, Univ. Louis-Pasteur, Strasbourg, 1976). Lecture Notes in Math., vol.
579. Springer, Berlin, 1977, pp. 29-58.
24. J. West, “Permutations with Forbidden Subsequences, and Stack-Sortable Permutations,” Ph.D. thesis, MIT, 1990.