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

[img]
Preview
 Text (Gao-Kitaev-Zhang-DM2016-avoiding-vincular-patterns-on-alternating-words)
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.

    Creators(s): 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
    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:23 Feb 2020 02:02
    URI:https://strathprints.strath.ac.uk/id/eprint/55630
    Export data:
    CORE (COnnecting REpositories)