Alternating, pattern-avoiding permutations

Joel Brewster Lewis

The electronic journal of combinatorics, Tome 16 (2009) no. 1

Résumé

We study the problem of counting alternating permutations avoiding collections of permutation patterns including $132$. We construct a bijection between the set $S_n(132)$ of $132$-avoiding permutations and the set $A_{2n + 1}(132)$ of alternating, $132$-avoiding permutations. For every set $p_1, \ldots, p_k$ of patterns and certain related patterns $q_1, \ldots, q_k$, our bijection restricts to a bijection between $S_n(132, p_1, \ldots, p_k)$, the set of permutations avoiding $132$ and the $p_i$, and $A_{2n + 1}(132, q_1, \ldots, q_k)$, the set of alternating permutations avoiding $132$ and the $q_i$. This reduces the enumeration of the latter set to that of the former.

Détail

DOI : 10.37236/245

Classification : 05A15, 05A05
Mots-clés : counting alternating permutations, avoiding permutations patterns, 132-avoiding permutations