Counting Words Avoiding a Short Increasing Pattern and the Pattern 1k...2

Abstract

We find finite-state recurrences to enumerate the words on the alphabet $[n{]}^r$ which avoid the patterns 123 and $1k(k-1)\dots 2$, and, separately, the words which avoid the patterns 1234 and $1k(k-1)\dots 2$.