The complexity of smooth words on 2-letter alphabets (Q653325)

The sequence \(K = 1,2,2,1,1,2,1,2,2,1,2,2,\ldots\), often attributed to Kolakoski, has the unusual property that its sequence of run lengths (that is, the lengths of maximal blocks of consecutive identical letters) is equal to \(K\) itself. (However, recent research of Berstel and Brlek has shown that \(K\) actually appeared much earlier in a paper of \textit{R. Oldenburger} [Trans. Am. Math. Soc. 46, 453-466 (1939; Zbl 0022.34002)]). Let \(a, b\) be integers with \(0 < a < b\), and let \(D(w)\) denote the sequence of run lengths in the word \(w\), discarding the first and/or the last run if its length is less than \(b\). If \(D(w)\) consists of nothing but \(a\)'s and \(b\)'s, then we say that \(w\) is \textit{differentiable}. A word is called \textit{smooth} if (very roughly speaking) it can be repeatedly differentiated without bound. (There is a technical point involving extending the left and right edges appropriately if they are too short.) In this rather technical paper, the author obtains polynomial upper and lower bounds on the number of smooth words of length \(n\).