Increasing Consecutive Patterns in Words

Mingjia Yang, Doron Zeilberger

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})$ algorit…