Pattern-avoiding alternating words

Emma L. L. Gao; Sergey Kitaev; Philip B. Zhang

paper

Pattern-avoiding alternating words

arXiv:1505.04078

Abstract

A word $w = w_{1} w_{2} \dots w_{n}$ is alternating if either $w_{1} < w_{2} > w_{3} < w_{4} > \dots$ (when the word is up-down) or $w_{1} > w_{2} < w_{3} > w_{4} < \dots$ (when the word is down-up). In this paper, we initiate the study of (pattern-avoiding) alternating words. We enumerate up-down (equivalently, down-up) words via finding a bijection with order ideals of a certain poset. Further, we show that the number of 123-avoiding up-down words of even length is given by the Narayana numbers, which is also the case, shown by us bijectively, with 132-avoiding up-down words of even length. We also give formulas for enumerating all other cases of avoidance of a permutation pattern of length 3 on alternating words.