Pattern-avoiding alternating words

Alice L L Gao, Sergey Kitaev, Philip B. Zhang

Research output: Contribution to journalArticle

31 Downloads (Pure)

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.

Original languageEnglish
Pages (from-to)56-66
JournalDiscrete Applied Mathematics
Volume207
Early online date31 Mar 2016
DOIs
Publication statusPublished - 10 Jul 2016

Keywords

  • alternating words
  • bijection
  • down-up words
  • fibonacci numbers
  • narayana numbers
  • order ideals
  • pattern-avoidance
  • up-down words

Cite this