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...

Pattern-avoiding alternating words

Gao, Alice L L and Kitaev, Sergey and Zhang, Philip B. (2016) Pattern-avoiding alternating words. Discrete Applied Mathematics, 207. pp. 56-66. ISSN 0166-218X

[img]
Preview
Text (Gao-etal-DAP2016-pattern-avoiding-alternating-words)
Gao_etal_DAP2016_pattern_avoiding_alternating_words.pdf - Accepted Author Manuscript
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo

Download (253kB) | Preview

Abstract

A word w=w1w2⋯wn is alternating if either w1<w2>w3<w4>⋯ (when the word is up-down) or w1>w2<w3>w4<⋯ (when the word is down-up). In this paper, we initiate the study of (pattern-avoiding) alternating words. We enumerate up-down (equivalently, down-up) words via finding a bijection with order ideals of a certain poset. Further, we show that the number of 123-avoiding up-down words of even length is given by the Narayana numbers, which is also the case, shown by us bijectively, with 132-avoiding up-down words of even length. We also give formulas for enumerating all other cases of avoidance of a permutation pattern of length 3 on alternating words.