Increasing Consecutive Patterns in Words

Abstract

We show how to enumerate words in $1^{m_1}\dots n^{m_n}$ that avoid the increasing consecutive pattern $12\dots r$ for any $r\ge 2$. Our approach yields an $O(n^{s+1})$ algorithm to enumerate words in $1^s\dots n^s$, avoiding the consecutive pattern $1\dots r$, for any $s$, and any $r$. This enables us to supply many more terms to quite a few OEIS sequences, and create new ones. We also treat the more general case of counting words with a specified number of the pattern of interest (the avoiding case corresponding to zero appearances). This article is accompanied by three Maple packages implementing our algorithms.

After the first version of the current paper was posted, Justin Troyka pointed out that our Theorem 1 is not new and it goes back to Ira Gessel. Thus we have this second version