On Pattern Avoiding Alternating Permutations
Joanna N. Chen, William Y.C. Chen and Robin D.P. Zhou
Abstract: An alternating permutation of length n is a permutation π = π_{1}π_{2}...π_{n} such that π_{1} < π_{2} > π_{3} < π_{4} >.... Let A_{n} denote the set of alternating permutations of {1, 2,..., n}, and let A_{n}(σ) be the set of alternating permutations in A_{n} that avoid a pattern σ. Recently, Lewis used generating trees to enumerate A_{2n}(1234), A_{2n}(2143) and A_{2n+1}(2143), and he posed some conjectures on the Wilf-equivalence of alternating permutations avoiding certain patterns of length four. Some of these conjectures have been proved by Bóna, Xu and Yan. In this paper, we prove two conjectured relations |A_{2n+1}(1243)| = |A_{2n+1} (2143)| and |A_{2n}(4312)| = |A_{2n}(1234)|. AMS Classification: 05A05, 05A15 Keywords: alternating permutation, pattern avoidance, generating tree Download: pdf |