Beyond alternating permutations: pattern avoidance in Young diagrams and tableaux (Q396936)

Summary: 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 \textit{J. Backelin} et al. [Adv. Appl. Math. 38, No. 2, 133--148 (2007; Zbl 1127.05002)] and \textit{E. Ouchterlony} [``Pattern avoiding doubly alternating permutations'', in: Proceedings of the international conference on formal power series and algebraic combinatorics, FPSAC 2006. 12 p. (2006)] 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. The second in the series is [the second author, ``Ascent-descent Young diagrams and pattern avoidance in alternating permutations'' (submitted)].