Pattern-avoiding alternating words

Gao, Alice L L and Kitaev, Sergey and Zhang, Philip B. (2016) Pattern-avoiding alternating words. Discrete Applied Mathematics, 207. pp. 56-66. ISSN 0166-218X (https://doi.org/10.1016/j.dam.2016.03.007)

[thumbnail of Gao-etal-DAP2016-pattern-avoiding-alternating-words]
Preview
 Text. Filename: Gao_etal_DAP2016_pattern_avoiding_alternating_words.pdf
Accepted Author Manuscript
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo
Download (253kB)| Preview

Abstract

A word w=w1w2⋯wn is alternating if either w1<w2>w3<w4>⋯ (when the word is up-down) or w1>w2<w3>w4<⋯ (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.

CORE (COnnecting REpositories)