CLR cover
Previous problem

Problem 18: From Lyndon Words to de Bruijn Words

Next problem

The combinatorial result of the problem provides the basis for an efficient online construction of de Bruijn words.

A binary word (on the alphabet $\{\sa{0},\sa{1}\}$) is a de Bruijn word of order (rank or span) $k$ if it contains cyclically each binary word of length $k$ exactly once as a factor. The word is of length $2^k$. There is a surprising relation between these words and the lexicographic ordering, which shows once more that ordering words is a powerful tool in text algorithms.

A Lyndon word is a primitive word that is the (lexicographically) smallest word in its conjugacy equivalence class.

Let $p$ be a prime number and $\mathcal{L}_p = (L_0,L_1,\dots,L_m)$ the sorted sequence of binary Lyndon words of length $p$ or $1$. Let also $$\mathbf{b}_p = L_0\cdot L_1\cdots L_m$$ be the concatenation of words in $\mathcal{L}_p$.

For a prime number $p$, show that the word $\mathbf{b}_p$ is a de Bruijn word of order $p$.

References

  • H. Fredricksen and J. Maiorana. Necklaces of beads in $k$ colors and $k$-ary de Bruijn sequences. Discrete Mathematics, 23(3):207-210, 1978.
  • E. Moreno and D. Perrin. Corrigendum to "on the theorem of Fredricksen and Maiorana about de Bruijn sequences". Advances in Applied Mathematics, 33(2):413-415, 2004.