<%@ 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
adj@dimacs.rutgers.edu
2Department of Mathematics, University of Michigan, 2074 East Hall, 530 Church Street, Ann Arbor, MI 48109-1043, USA
jomarin@umich.edu
Annals of Combinatorics 15 (2) pp.437-448 July, 2011
AMS Subject Classification: 05A05, 05A15
Abstract:
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

References:

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)