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. 20792093. ISSN 0012365X
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 updown) or $w_1>w_2<w_3>w_4<\cdots$ (when the word is downup). The study of alternating words avoiding classical permutation patterns was initiated by the authors in~\cite{GKZ}, where, in particular, it was shown that 123avoiding updown words of even length are counted by the Narayana numbers.However, not much was understood on the structure of 123avoiding updown words. In this paper, we fill in this gap by introducing the notion of a cutpair 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 updown words of even length avoiding the consecutive pattern $\underline{132}$ and updown 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: https://orcid.org/0000000333241647 and Zhang, Philip B.;

Item type: Article ID code: 55630 Dates: DateEvent2016Published22 February 2016AcceptedNotes: Accepted for publication on 14.03.2016 Keywords: Dyck path, alternating word, updown word, patternavoidance, 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: 25 Sep 2023 01:42 URI: https://strathprints.strath.ac.uk/id/eprint/55630