<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Generating-Tree Isomorphisms for Pattern-Avoiding Involutions
Aaron D. Jaggard1 and Joseph J. Marincel2
1Department of Computer Science, Colgate University, 13 Oak Drive, Hamilton, NY 13346, USA
2Department of Mathematics, University of Michigan, 2074 East Hall, 530 Church Street, Ann Arbor, MI 48109-1043, USA
Annals of Combinatorics 15 (2) pp.437-448 July, 2011
AMS Subject Classification: 05A05, 05A15
We show that for k ≥ 5 and the permutations τk = (k − 1)k(k − 2) . . .312 andJk = k(k−1) . . .21, the generating tree for involutions avoiding the pattern τk is isomorphic to the generating tree for involutions avoiding the pattern Jk. This implies a family of Wilf equivalences for pattern avoidance by involutions.
Keywords: permutation pattern, involution, generating tree


1. Bousquet-M´elou, M.: Four classes of pattern-avoiding permutations under one roof: generating trees with two labels. Electron J. Combin. 9(2), #R19 (2002/03)

2. Bousquet-Mélou, M., Steingr´ımsson, E.: Decreasing subsequences in permutations and Wilf equivalence for involutions. J. Algebraic Combin. 22(4), 383–409 (2005)

3. Dukes, W.M.B., Jelınek, V., Mansour, T., Reifegerste, A.: New equivalences for pattern avoiding involutions. Proc. Amer. Math. Soc. 137(2), 457–465 (2009)

4. Gessel, I.M.: Symmetric functions and P-recursiveness. J. Combin. Theory Ser. A 53(2), 257–285 (1990)

5. Gouyou-Beauchamps, D.: Standard Young tableaux of height 4 and 5. European J. Combin. 10(1), 69–82 (1989)

6. Guibert, O.: Combinatoire des permutations `a motifs exclus en liaison avec mots, cartes planaires et tableaux de Young. University Bordeaux 1, Talence (1995)

7. Guibert, O., Pergola, E., Pinzani, R.: Vexillary involutions are enumerated by Motzkin numbers. Ann. Combin. 5(2), 153–174 (2001)

8. Jaggard, A.D.: Prefix exchanging and pattern avoidance by involutions. Electron J. Combin. 9(2), #R16 (2002/03)

9. Jaggard, A.D., Marincel, J.J.: Generating tree isomorphisms for pattern-avoiding involutions. Abstract of a talk given at the National Meeting of the AMS. Avaible at http://www.ams.org/amsmtgs/2098_abstracts/1023-05-1618.pdf (2007)

10. Krattenthaler, C.: Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes. Adv. Appl. Math. 37(3), 404–431 (2006)

11. Regev, A.: Asymptotic values for degrees associated with strips of Young diagrams. Adv. Math. 41(2), 115–136 (1981)

12. Simion, R., Schmidt, F.W.: Restricted permutations. European J. Combin. 6(4), 383–406 (1985)

13. West, J.: Permutations with forbidden subsequences, and, stack-sortable permutations. M.I.T., Cambridge (1990)