Let $W$ be a cyclic word of length $n$ in a 2letter alphabet $\{0,1\}$. It is clear that it has at most $n^2$ different subwords (because the number of subwords of length $i$ is at most $n$ for each $i$) and that the actual number of subwords is less than $n^2$ (because the number of subwords of length $1$ is not $n$, but $2$). What is the maximal possible number of subwords as a function of $n$ and what are words where this upper bound is achieved.
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
If you take a de Bruijn sequence of length $2^k$, then you have every length $k$ sequence precisely once. This implies that the number of subwords is maximal, since each subword of length $\geq k$ is determined uniquely by its prefix, and each subword of length $ < k$ occurs (with equal frequency). So this achieves the upper bound when $n=2^k$. 

