A natural bijection for contiguous pattern avoidance in words

DOI10.1016/J.DISC.2023.113793MaRDI QIDQ6136679zbMATHFDO

Authors Julia Carrigan, Isaiah Hollars, Eric Rowland

Publication date 17 January 2024

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

combinatorics on wordsbijectionscontiguous pattern avoidance

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Two words $p$ and $q$ are avoided by the same number of length-$n$ words, for all $n$, precisely when $p$ and $q$ have the same set of border lengths. However, known proofs of this result use generating functions and do not provide explicit bijections. We establish a natural bijection from the set of words avoiding $p$ to the set of words avoiding $q$ in the case that $p$ and $q$ have the same set of proper borders.

Recommendations

• Pattern avoidance in biwords
• Words restricted by patterns with at most 2 distinct letters
• Finite automata and pattern avoidance in words
• Exponential lower bounds for the number of words of uniform length avoiding a pattern
• Pattern avoidance in multiset permutations: bijective proof

Cites work

• scientific article; zbMATH DE number 3842140 (Why is no real title available?)
• A Combinatorial Identity and Its Application to the Problem Concerning the First Occurrence of a Rare Event
• An Inversion Theorem for Cluster Decompositions of Sequences with Distinguished Subsequences
• Classification of bijections between 321- and 132-avoiding permutations
• Enumeration of words by their number of mistakes
• Periods and borders of random words
• Some Combinatorial Properties of Free Semigroups
• String overlaps, pattern matching, and nontransitive games
• The Goulden—Jackson cluster method: extensions, applications and implementations

This page was built for publication: A natural bijection for contiguous pattern avoidance in words

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