The Number of Threshold Words on $n$ Letters Grows Exponentially for Every $n\ge 27$

Abstract

For every $n\ge 27$, we show that the number of $n/(n-1{)}^{+}$-free words (i.e., threshold words) of length $k$ on $n$ letters grows exponentially in $k$. This settles all but finitely many cases of a conjecture of Ochem.

13 pages