On the number of \(C^{\infty}\)-words of each length (Q1121320)

A word W on the alphabet \(\{\) 1,2\(\}\) in which neither 111 nor 222 occurs is said to be differentiable and its derivative D(W) is the word whose jth symbol equals the length of the jth run of W (discarding the first and/or the last run if these have length one). This notion was introduced by \textit{F. M. Dekking} [Sémin. Théor. Nombres Bordeaux 1980/1981, Exposé No.31, 6 p. (1981; Zbl 0472.10054)] to study the structure of the self-derivative \textit{W. Kowalowski} sequence 122112122122... [Am. Math. Mon. 73, 681-682 (1966)]. A word is said to be \(C^{\infty}\) if it is arbitrarily often differentiable. In this paper the number \(\gamma\) (n) of \(C^{\infty}\)-words of length n is investigated, using \(\gamma '(n):=\gamma (n+1)-\gamma (n)\) and \(\gamma ''\). Here \(\gamma ''(n)\) is just the number of fully extendable \(C^{\infty}\)-words S (i.e., 1S1, 1S2, 2S1 and 2S2 are all \(C^{\infty})\) of length n. The height of W is the least integer k such that \(D^ k(W)\) is the empty word. Now let A(k) denote the minimum and B(k) the maximum of possible lengths for fully extendable words of height k. Then (Corollary 6) for \(B(k-1)<n<A(k)\) one has \(\gamma ''(n)=0\) and for \(B(k-1)<n\leq A(k)\) one has \(\gamma '(n)=2^ k\). This leads to \(\gamma (n)=(n+3)2^ k-2\cdot 3^ k\) if \(B(k-1)+1\leq n\leq A(k)+1.\) Moreover for such n, \(\gamma (n)\asymp n^ p\) where p is the value log 3/ log(3/2) conjectured by \textit{F. M. Dekking} [loc.cit.] in the general case. Also the relation \(\gamma (3n)=3\gamma (2n-1)\) is obtained in particular cases. Proofs involve elementary enumerations.