Picture of athlete cycling

Open Access research with a real impact on health...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of Open Access research papers by Strathclyde researchers, including by researchers from the Physical Activity for Health Group based within the School of Psychological Sciences & Health. Research here seeks to better understand how and why physical activity improves health, gain a better understanding of the amount, intensity, and type of physical activity needed for health benefits, and evaluate the effect of interventions to promote physical activity.

Explore open research content by Physical Activity for Health...

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.