On avoidance of patterns of the form σ-τ by words over a finite alphabet
Toufik Mansour, Mark Shattuck
Abstract
Vincular or dashed patterns resemble classical patterns except that
some of the letters within an occurrence are required to be
adjacent. We prove several infinite families of Wilf-equivalences for
k-ary words involving vincular patterns containing a
single dash, which explain the majority of the equivalences witnessed
for such patterns of length four. When combined with previous
results, numerical evidence, and some arguments in specific cases, we
obtain the complete Wilf-classification for all vincular patterns of
length four containing a single dash. In some cases, our proof shows
further that the equivalence holds for multiset permutations since it
is seen to respect the number of occurrences of each letter within a
word. Some related enumerative results are provided for patterns
τ of length four, among them generating function
formulas for the number of members of [k]n
avoiding any τ of the form 11a-b.
Full Text: PDF