Beyond Alternating Permutations: Pattern Avoidance in Young Diagrams and Tableaux

作者：Gowravaram Nihal^*; Jagadeesan Ravi

来源：Electronic Journal of Combinatorics, 2013, 20(4): P17.

• pattern avoidance
• alternating permutations
• descent type permutations
• Wilf equivalence
• shape-Wilf equivalence

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).

• 出版日期2013-11-15