Avoiding vincular patterns on alternating words

DOI10.1016/J.DISC.2016.02.013zbMATH Open1336.05002arXiv1507.06154OpenAlexW2219113549MaRDI QIDQ284737FDOQ284737

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

Publication date: 18 May 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Generalized permutation patterns and a classification of the Mahonian statistics
• Enumeration of up-down sequences
• Up-down sequences
• Pattern-avoiding alternating words
• A survey of alternating permutations
• Title not available (Why is that?)
• Patterns in permutations and words.

Cited In (2)

• Title not available (Why is that?)
• 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)