On Minimal Words With Given Subword Complexity

Ming-wei Wang, Jeffrey Shallit


We prove that the minimal length of a word $S_n$ having the property that it contains exactly $F_{m+2}$ distinct subwords of length $m$ for $1 \leq m \leq n$ is $F_n + F_{n+2}$. Here $F_n$ is the $n$th Fibonacci number defined by $F_1 = F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n > 2$. We also give an algorithm that generates a minimal word $S_n$ for each $n \geq 1$.

Full Text: PDF