Avoiding vincular patterns on alternating words

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

Research output: Contribution to journalArticle

20 Downloads (Pure)

Abstract

A word $w=w_1w_2\cdots w_n$ is alternating if either $w_1<w_2>w_3<w_4>\cdots$ (when the word is up-down) or $w_1>w_2<w_3>w_4<\cdots$ (when the word is down-up). The study of alternating words avoiding classical permutation patterns was initiated by the authors in~\cite{GKZ}, where, in particular, it was shown that 123-avoiding up-down words of even length are counted by the Narayana numbers.However, not much was understood on the structure of 123-avoiding up-down words. In this paper, we fill in this gap by introducing the notion of a cut-pair that allows us to subdivide the set of words in question into equivalence classes. We provide a combinatorial argument to show that the number of equivalence classes is given by the Catalan numbers, which induces an alternative (combinatorial) proof of the corresponding result in~\cite{GKZ}.Further, we extend the enumerative results in~\cite{GKZ} to the case of alternating words avoiding a vincular pattern of length 3. We show that it is sufficient to enumerate up-down words of even length avoiding the consecutive pattern $\underline{132}$ and up-down words of odd length avoiding the consecutive pattern $\underline{312}$ to answer all of our enumerative questions. The former of the two key cases is enumerated by the Stirling numbers of the second kind.
Original languageEnglish
Pages (from-to)2079-2093
Number of pages25
JournalDiscrete Mathematics
Volume339
Publication statusPublished - 2016

Fingerprint

Equivalence classes
Equivalence class
Consecutive
Narayana numbers
Stirling numbers of the second kind
Combinatorial argument
Subdivide
Catalan number
Permutation
Odd
Sufficient
Alternatives

Keywords

  • Dyck path
  • alternating word
  • up-down word
  • pattern-avoidance
  • Narayana number
  • Catalan number
  • Stirling number of the second kind

Cite this

Gao, A. L. L., Kitaev, S., & Zhang, P. B. (2016). Avoiding vincular patterns on alternating words. Discrete Mathematics, 339, 2079-2093.
Gao, Alice L.L. ; Kitaev, Sergey ; Zhang, Philip B. / Avoiding vincular patterns on alternating words. In: Discrete Mathematics. 2016 ; Vol. 339. pp. 2079-2093.
@article{8ce15c9707534b918d724c7caf7d2716,
title = "Avoiding vincular patterns on alternating words",
abstract = "A word $w=w_1w_2\cdots w_n$ is alternating if either $w_1w_3\cdots$ (when the word is up-down) or $w_1>w_2w_4<\cdots$ (when the word is down-up). The study of alternating words avoiding classical permutation patterns was initiated by the authors in~\cite{GKZ}, where, in particular, it was shown that 123-avoiding up-down words of even length are counted by the Narayana numbers.However, not much was understood on the structure of 123-avoiding up-down words. In this paper, we fill in this gap by introducing the notion of a cut-pair that allows us to subdivide the set of words in question into equivalence classes. We provide a combinatorial argument to show that the number of equivalence classes is given by the Catalan numbers, which induces an alternative (combinatorial) proof of the corresponding result in~\cite{GKZ}.Further, we extend the enumerative results in~\cite{GKZ} to the case of alternating words avoiding a vincular pattern of length 3. We show that it is sufficient to enumerate up-down words of even length avoiding the consecutive pattern $\underline{132}$ and up-down words of odd length avoiding the consecutive pattern $\underline{312}$ to answer all of our enumerative questions. The former of the two key cases is enumerated by the Stirling numbers of the second kind.",
keywords = "Dyck path, alternating word, up-down word, pattern-avoidance, Narayana number, Catalan number, Stirling number of the second kind",
author = "Gao, {Alice L.L.} and Sergey Kitaev and Zhang, {Philip B.}",
note = "Accepted for publication on 14.03.2016",
year = "2016",
language = "English",
volume = "339",
pages = "2079--2093",
journal = "Discrete Mathematics",
issn = "0012-365X",

}

Gao, ALL, Kitaev, S & Zhang, PB 2016, 'Avoiding vincular patterns on alternating words', Discrete Mathematics, vol. 339, pp. 2079-2093.

Avoiding vincular patterns on alternating words. / Gao, Alice L.L.; Kitaev, Sergey; Zhang, Philip B.

In: Discrete Mathematics, Vol. 339, 2016, p. 2079-2093.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Avoiding vincular patterns on alternating words

AU - Gao, Alice L.L.

AU - Kitaev, Sergey

AU - Zhang, Philip B.

N1 - Accepted for publication on 14.03.2016

PY - 2016

Y1 - 2016

N2 - A word $w=w_1w_2\cdots w_n$ is alternating if either $w_1w_3\cdots$ (when the word is up-down) or $w_1>w_2w_4<\cdots$ (when the word is down-up). The study of alternating words avoiding classical permutation patterns was initiated by the authors in~\cite{GKZ}, where, in particular, it was shown that 123-avoiding up-down words of even length are counted by the Narayana numbers.However, not much was understood on the structure of 123-avoiding up-down words. In this paper, we fill in this gap by introducing the notion of a cut-pair that allows us to subdivide the set of words in question into equivalence classes. We provide a combinatorial argument to show that the number of equivalence classes is given by the Catalan numbers, which induces an alternative (combinatorial) proof of the corresponding result in~\cite{GKZ}.Further, we extend the enumerative results in~\cite{GKZ} to the case of alternating words avoiding a vincular pattern of length 3. We show that it is sufficient to enumerate up-down words of even length avoiding the consecutive pattern $\underline{132}$ and up-down words of odd length avoiding the consecutive pattern $\underline{312}$ to answer all of our enumerative questions. The former of the two key cases is enumerated by the Stirling numbers of the second kind.

AB - A word $w=w_1w_2\cdots w_n$ is alternating if either $w_1w_3\cdots$ (when the word is up-down) or $w_1>w_2w_4<\cdots$ (when the word is down-up). The study of alternating words avoiding classical permutation patterns was initiated by the authors in~\cite{GKZ}, where, in particular, it was shown that 123-avoiding up-down words of even length are counted by the Narayana numbers.However, not much was understood on the structure of 123-avoiding up-down words. In this paper, we fill in this gap by introducing the notion of a cut-pair that allows us to subdivide the set of words in question into equivalence classes. We provide a combinatorial argument to show that the number of equivalence classes is given by the Catalan numbers, which induces an alternative (combinatorial) proof of the corresponding result in~\cite{GKZ}.Further, we extend the enumerative results in~\cite{GKZ} to the case of alternating words avoiding a vincular pattern of length 3. We show that it is sufficient to enumerate up-down words of even length avoiding the consecutive pattern $\underline{132}$ and up-down words of odd length avoiding the consecutive pattern $\underline{312}$ to answer all of our enumerative questions. The former of the two key cases is enumerated by the Stirling numbers of the second kind.

KW - Dyck path

KW - alternating word

KW - up-down word

KW - pattern-avoidance

KW - Narayana number

KW - Catalan number

KW - Stirling number of the second kind

M3 - Article

VL - 339

SP - 2079

EP - 2093

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

ER -