Avoiding vincular patterns on alternating words

Gao, Alice L.L. and Kitaev, Sergey and Zhang, Philip B. (2016) Avoiding vincular patterns on alternating words. Discrete Mathematics, 339. pp. 2079-2093. ISSN 0012-365X

[thumbnail of Gao-Kitaev-Zhang-DM2016-avoiding-vincular-patterns-on-alternating-words]
Preview
 Text. Filename: Gao_Kitaev_Zhang_DM2016_avoiding_vincular_patterns_on_alternating_words.pdf
Accepted Author Manuscript
Download (141kB)| Preview

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.

ORCID iDs

Gao, Alice L.L., Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647 and Zhang, Philip B.;
  • Item type:Article
    ID code:55630
    Dates:
    Date
    Event
    2016
    Published
    22 February 2016
    Accepted
    Notes:Accepted for publication on 14.03.2016
    Keywords:Dyck path, alternating word, up-down word, pattern-avoidance, Narayana number, Catalan number, Stirling number of the second kind, Discrete Mathematics and Combinatorics, Theoretical Computer Science
    Subjects:UNSPECIFIED
    Department:Faculty of Science > Computer and Information Sciences
    Depositing user: Pure Administrator
    Date deposited:22 Feb 2016 13:57
    Last modified:29 Jan 2022 01:23
    URI:https://strathprints.strath.ac.uk/id/eprint/55630
CORE (COnnecting REpositories)