We investigate pattern avoidance in alternating permutations and generalizations thereof. First, we study pattern avoidance in an alternating analogue of Young diagrams. In particular, we extend Babson-West's notion of shape-Wilf equivalence to apply to alternating permutations and so generalize results of Backelin-West-Xin and Ouchterlony to alternating permutations. Second, we study pattern avoidance in the more general context of permutations with restricted ascents and descents.?We consider a question of Lewis regarding permutations that are the reading words of thickened staircase Young tableaux, that is, permutations that have $k-1$ ascents followed by a descent, followed by $k-1$ ascents, et cetera. We determine the relative sizes of the sets of pattern-avoiding $(k-1)$-ascent permutations in terms of the forbidden pattern. Furthermore, inequalities in the sizes of sets of pattern-avoiding permutations in this context arise from further extensions of shape-equivalence type enumerations. This paper is the first of a two-paper series presenting the work of Beyond alternating permutations: Pattern avoidance in Young diagrams and tableaux (arXiv:1301.6796v1). The second in the series is Ascent-descent Young diagrams and pattern avoidance in alternating permutations (by the second author, submitted).
展开▼