arXiv Analytics

Sign in

arXiv:math/0306002 [math.CO]AbstractReferencesReviewsResources

Prefix exchanging and pattern avoidance by involutions

Aaron D. Jaggard

Published 2003-05-30, updated 2004-09-02Version 2

Let I_n(\pi) denote the number of involutions in the symmetric group S_n which avoid the permutation \pi. We say that two permutations \alpha,\beta\in\S{j} may be exchanged if for every n, k, and ordering \tau of j+1,...,k, we have I_n(\alpha\tau)=I_n(\beta\tau). Here we prove that 12 and 21 may be exchanged and that 123 and 321 may be exchanged. The ability to exchange 123 and 321 implies a conjecture of Guibert, thus completing the classification of S_4 with respect to pattern avoidance by involutions; both of these results also have consequences for longer patterns. Pattern avoidance by involutions may be generalized to rook placements on Ferrers boards which satisfy certain symmetry conditions. Here we provide sufficient conditions for the corresponding generalization of the ability to exchange two prefixes and show that these conditions are satisfied by 12 and 21 and by 123 and 321. Our results and approach parallel work by Babson and West on analogous problems for pattern avoidance by general (not necessarily involutive) permutations, with some modifications required by the symmetry of the current problem.

Comments: Final version. Minor changes for clarity and to correct typos. Conjecture 6.4 follows from recent work of Bousquet-Melou and Steingrimsson (math.CO/0405334). 24 pages, 9 figures, 4 tables
Journal: Elec. J. Comb. 9 (2) 2003, #R16
Categories: math.CO
Subjects: 05A05, 05A15
Related articles: Most relevant | Search more
arXiv:2309.06518 [math.CO] (Published 2023-09-12)
Pattern Avoidance in Weak Ascent Sequences
arXiv:1509.07941 [math.CO] (Published 2015-09-26)
Pattern Avoidance for Random Permutations
arXiv:1211.3442 [math.CO] (Published 2012-11-14)
Pattern avoidance in matchings and partitions