Pattern occurrences in k-ary words revisited: a few new and old observations

2021/01/31 by Mansour, Toufik, Rastegar, Reza
#05A05 #05A16 #05C81 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2102.00443

Abstract

In this paper, we study the pattern occurrence in k-ary words. We prove an explicit upper bound on the number of k-ary words avoiding any given pattern using a random walk argument. Additionally, we reproduce several already known results and establish a simple connection among pattern occurrences in permutations and k-ary words. A simple consequence of this connection is that Wilf-equivalence of two patterns in words implies their Wilf-equivalence in permutations.

Related

• On avoidance of patterns of the form σ-τ by words over a finite alphabet
• Finite automata, probabilistic method, and occurrence enumeration of a\n pattern in words and permutations
• Pattern statistics in faro words and permutations
• The absence of a pattern and the number of occurrences of another
• Enumerating pattern-avoiding permutations by leading terms