Avoiding vincular patterns on alternating words

DOI10.1016/J.DISC.2016.02.013MaRDI QIDQ284737zbMATH OpenOpenAlexFDO

Authors Alice L. L. Gao, Sergey Kitaev, Philip B. Zhang

Publication date 18 May 2016

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.06154

zbMATH Keywords

Catalan numberStirling number of the second kindDyck pathalternating wordNarayana numberpattern-avoidanceup-down word

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Bell and Stirling numbers (11B73)

Abstract: A word $w=w_1{w}_{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 $underline132$ and up-down words of odd length avoiding the consecutive pattern $underline312$ to answer all of our enumerative questions. The former of the two key cases is enumerated by the Stirling numbers of the second kind.

Recommendations

• Pattern-avoiding alternating words
• On pattern avoiding alternating permutations
• Alternating, pattern-avoiding permutations
• Pattern avoiding alternating involutions
• Pattern avoidance for alternating permutations and Young tableaux

Cites work

• scientific article; zbMATH DE number 3675904 (Why is no real title available?)
• scientific article; zbMATH DE number 872231 (Why is no real title available?)
• A survey of alternating permutations
• Enumeration of up-down sequences
• Generalized permutation patterns and a classification of the Mahonian statistics
• Pattern-avoiding alternating words
• Patterns in permutations and words.
• Up-down sequences

Cited in

(2)

• scientific article; zbMATH DE number 1948509 (Why is no real title available?)
• Pattern-avoiding alternating words

This page was built for publication: Avoiding vincular patterns on alternating words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q284737)