Pattern-avoiding alternating words

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

Research output: Contribution to journalArticle

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.

LanguageEnglish
Pages56-66
JournalDiscrete Applied Mathematics
Volume207
Early online date31 Mar 2016
DOIs
Publication statusPublished - 10 Jul 2016

Fingerprint

Narayana numbers
Order Ideal
Bijection
Poset
Permutation

Keywords

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

Cite this

Gao, Alice L L ; Kitaev, Sergey ; Zhang, Philip B. / Pattern-avoiding alternating words. In: Discrete Applied Mathematics. 2016 ; Vol. 207. pp. 56-66.
@article{04a6931c901249f19073ec1646c3aa45,
title = "Pattern-avoiding alternating words",
abstract = "A word w=w1w2⋯wn is alternating if either w1w3⋯ (when the word is up-down) or w1>w2w4<⋯ (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.",
keywords = "alternating words, bijection, down-up words, fibonacci numbers, narayana numbers, order ideals, pattern-avoidance, up-down words",
author = "Gao, {Alice L L} and Sergey Kitaev and Zhang, {Philip B.}",
year = "2016",
month = "7",
day = "10",
doi = "10.1016/j.dam.2016.03.007",
language = "English",
volume = "207",
pages = "56--66",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",

}

Pattern-avoiding alternating words. / Gao, Alice L L; Kitaev, Sergey; Zhang, Philip B.

In: Discrete Applied Mathematics, Vol. 207, 10.07.2016, p. 56-66.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Pattern-avoiding alternating words

AU - Gao, Alice L L

AU - Kitaev, Sergey

AU - Zhang, Philip B.

PY - 2016/7/10

Y1 - 2016/7/10

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

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

KW - alternating words

KW - bijection

KW - down-up words

KW - fibonacci numbers

KW - narayana numbers

KW - order ideals

KW - pattern-avoidance

KW - up-down words

UR - http://www.scopus.com/inward/record.url?scp=84962069957&partnerID=8YFLogxK

UR - http://www.sciencedirect.com/science/article/pii/S0166218X16301275

U2 - 10.1016/j.dam.2016.03.007

DO - 10.1016/j.dam.2016.03.007

M3 - Article

VL - 207

SP - 56

EP - 66

JO - Discrete Applied Mathematics

T2 - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -