Pattern-avoiding alternating words

DOI10.1016/J.DAM.2016.03.007zbMATH Open1337.05003arXiv1505.04078OpenAlexW1544034017MaRDI QIDQ290100FDOQ290100

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

Publication date: 1 June 2016

Published in: Discrete Applied 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). 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.

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

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

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)

Cites Work

• The On-Line Encyclopedia of Integer Sequences
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Enumeration of up-down sequences
• Up-down sequences
• Avoiding vincular patterns on alternating words
• A Survey of Alternating Permutations
• Combinatorics of Compositions and Words
• Patterns in permutations and words.
• Restricted 132-alternating permutations and Chebyshev polynomials
• Restricted words by adjacencies
• Quasi-symmetric functions and up-down compositions
• Longest alternating subsequences in pattern-restricted permutations
• Longest alternating subsequences of \(k\)-ary words
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (5)

• Pattern avoidance by palindromes
• Title not available (Why is that?)
• Avoiding vincular patterns on alternating words
• Catalan words avoiding pairs of length three patterns
• Title not available (Why is that?)

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)