Pattern-avoiding alternating words

DOI10.1016/J.DAM.2016.03.007MaRDI QIDQ290100zbMATH OpenOpenAlexFDO

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

Publication date 1 June 2016

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

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

zbMATH Keywords

order idealspattern avoidancebijectionFibonacci numbersalternating wordsdown-up wordsNarayana numbersup-down words

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Fibonacci and Lucas numbers and polynomials and generalizations (11B39)

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

Recommendations

• Avoiding vincular patterns on alternating words
• Alternating, pattern-avoiding permutations
• On pattern avoiding alternating permutations
• Pattern avoidance for alternating permutations and Young tableaux
• Counting binary words avoiding alternating patterns

Cites work

• scientific article; zbMATH DE number 3552560 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• scientific article; zbMATH DE number 1844443 (Why is no real title available?)
• scientific article; zbMATH DE number 872231 (Why is no real title available?)
• A survey of alternating permutations
• Avoiding vincular patterns on alternating words
• Combinatorics of Compositions and Words
• Enumeration of up-down sequences
• Longest alternating subsequences in pattern-restricted \(k\)-ary words
• Longest alternating subsequences in pattern-restricted permutations
• Longest alternating subsequences of \(k\)-ary words
• Patterns in permutations and words.
• Quasi-symmetric functions and up-down compositions
• Restricted 132-alternating permutations and Chebyshev polynomials
• Restricted words by adjacencies
• The On-Line Encyclopedia of Integer Sequences
• Up-down sequences

Cited in

(5)

• Avoiding vincular patterns on alternating words
• Catalan words avoiding pairs of length three patterns
• scientific article; zbMATH DE number 1948509 (Why is no real title available?)
• Pattern avoidance by palindromes
• scientific article; zbMATH DE number 554160 (Why is no real title available?)

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Pattern-avoiding alternating words

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