<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 11 Issue 3-4" %>
Restricted Symmetric Permutations
Eric S. Egge
Department of Mathematics, Carleton College, Northfield, MN 55057, USA
Annals of Combinatorics 11 (3-4) p.405-434 September, 2007
AMS Subject Classification:05A05, 05A15
Pattern-avoiding involutions, which have received much enumerative attention, are pattern-avoiding permutations which are invariant under the natural action of a certain subgroup of D8, the symmetry group of a square. Three other nontrivial subgroups of D8 also have invariant permutations under this action. For each of these subgroups, we enumerate the set of permutations which are invariant under the action of the subgroup and which also avoid a given set of forbidden patterns. The sets of forbidden patterns we consider include all subsets of S3. For each subgroup we also give a bijection between the invariant permutations and certain symmetric signed permutations.
Keywords: pattern-avoiding permutation, pattern-avoiding involution, restricted permutation, signed permutation, signed involution


1. C. Banderier, M. Bousquet-M´elou, A. Denise, P. Flajolet, D. Gardy, and D. Gouyou- Beauchamps, Generating functions for generating trees, Discrete Math. 246 (1) (2002) 29- 55.

2. E.S. Egge, Restricted 3412-avoiding involutions, continued fractions, and Chebyshev polynomials, Adv. Appl. Math. 33 (3) (2004) 451-475.

3. E.S. Egge, Restricted signed permutations counted by the Schröder numbers, Discrete Math. 306 (6) (2006) 552-563.

4. O. Guibert and E. Pergola, Enumeration of vexillary involutions which are equal to their mirror/complement, Discrete Math. 224 (1-3) (2000) 281-287.

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

6. A. Jaggard, Prefix exchanging and pattern avoidance by involutions, Electron. J. Combin. 9 (2) (2002) #R16.

7. T. Mansour and J. West, Avoiding 2-letter signed patterns, Sém. Lothar. Combin. 49 (2002) B49a.

8. T. Mansour, S.H.F. Yan, and L.L.M. Yang, Counting occurences of 231 in an involution, Discrete Math. 306 (6) (2006) 564-572.

9. H. Prodinger, The kernel method: a collection of examples, Sém. Lothar. Combin. 50 (2003) B50f.

10. R. Simion, Combinatorial statistics on type-B analogues of noncrossing partitions and restricted permutations, Electron. J. Combin. 7 (1) (2000) #R9.

11. R. Simion and F. Schmidt, Restricted permutations, Europ. J. Combin. 6 (4) (1985) 383-406.

12. J.West, Generating trees and forbidden subsequences, Discrete Math. 157 (1-3) (1996) 363- 374.