Beyond Alternating Permutations: Pattern Avoidance in Young Diagrams and Tableaux

  • Nihal Gowravaram
  • Ravi Jagadeesan
Keywords: pattern avoidance, alternating permutations, descent type permutations, Wilf equivalence, shape-Wilf equivalence

Abstract

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

Published
2013-11-15
Article Number
P17