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 An denote the set of alternating permutations of {1, 2,..., n}, and let An(σ) be the set of alternating permutations in An that avoid a pattern σ. Recently, Lewis used generating trees to enumerate A2n(1234), A2n(2143) and A2n+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 |A2n+1(1243)| = |A2n+1 (2143)| and |A2n(4312)| = |A2n(1234)|.

  AMS Classification:  05A05, 05A15

  Keywords:  alternating permutation, pattern avoidance, generating tree

  Download:   pdf