On Pattern Avoiding Alternating Permutations

Abstract

An alternating permutation of length $n$ is a permutation $\pi ={\pi }_1{\pi }_2...{\pi }_n$ such that ${\pi }_1<{\pi }_2>{\pi }_3<{\pi }_4>...$. Let $A_n$ denote set of alternating permutations of $1,2,...,n$, and let $A_n(\sigma )$ be set of alternating permutations in $A_n$ that avoid a pattern $\sigma$. Recently, Lewis used generating trees to enumerate $A_{2n}(1234)$, $A_{2n}(2143)$ and $A_{2n+1}(2143)$, and he posed several conjectures on the Wilf-equivalence of alternating permutations avoiding certain patterns. Some of these conjectures have been proved by Bóna, Xu and Yan. In this paper, we prove the two relations $|A_{2n+1}(1243)|=|A_{2n+1}(2143)|$ and $|A_{2n}(4312)|=|A_{2n}(1234)|$ as conjectured by Lewis.

21 pages, 2 figures

References in corpus (1)

• On a Family of Conjectures of Joel Lewis on Alternating Permutations