# More Fun with Binary Words: De Bruijn Sequences

January 1st, 2013 by munizao

In the previous post, we explored symmetry variations on binary words in the context of crossed stick puzzles. Now I want to look at some ways to play with sequences of these binary words. For reference, I’ll recap the table of numbers of different binary words of various types and lengths from that post. As before, swapping 1’s and 0’s with each other gives equivalent invertible words, and turning words backwards gives equivalent reversible words.

You’ll notice some new columns in this version of the table. Cyclic words remain equivalent over any number of cyclic shifts or moves that take every digit but the last down by one place and put the last into the first place. You can think of the digits as black and white beads on a necklace, where the necklace stays the same however you rotate it. The cyclic property can be combined with invertibility and reversibility; reversing a cyclic word is equivalent to “flipping over” the necklace.

 Length Fixed Invertible Reversible Inv. & Rev. Cyclic Cyclic Inv. Cyclic Rev. Cyclic Inv. & Rev. 1 2 1 2 1 2 1 2 1 2 4 2 3 2 3 2 3 2 3 8 4 6 3 4 2 4 2 4 16 8 10 6 6 4 6 4 5 32 16 20 10 8 4 8 4 6 64 32 36 20 14 8 13 8 7 128 64 72 36 20 10 18 9

One classic puzzle involving binary words is to find a necklace where every possible word of a given length is present exactly once exactly once as a substring of the necklace. These necklaces are known as De Bruijn sequences. For example, here’s a De Bruijn sequence of length 4 binary words:

Since we have a bunch of variations on binary words, we can look for De Bruijn sequences of each of them. Neither the cyclic nor the reversible words will make proper De Bruijn sequences. Consider the length 3 word `000`. There can’t be another 0 on either end of that, because that would make a second instance of `000` in the sequence. So there must be a substring of `10001` in the sequence. But that gives instances of both `001` and `100` which are equivalent to each other both as cyclic and reversible words. The same reasoning applies to longer words.

However, you can make improper, non-cyclic De Bruijn sequences. For example, `00010111` is an improper De Bruijn sequence of the reversible length 3 words. For the reversible length 4 words, even an improper De Bruijn sequence is impossible. (Try to make one, if you are wondering why.) Problem #29 is to find an improper De Bruijn sequence for the reversible words of length 5.

The invertible and reversible length 4 words do have an improper De Bruijn sequence: `000011010`. And with plain invertible words, proper cyclic De Bruijn sequences are again possible. Here’s a De Bruijn sequence of the invertible words of length 4:

Problem #30: Find a De Bruijn sequence of the invertible words of length 5.

Unlike polyform puzzles, De Bruijn sequences are considered a topic for respectable mathematics, which means that they are well studied, and therefore it can be assumed that anything written here is well known by those who know such things. Still, they are fun to think about, and have real world applications. For example, in the study of Sanskrit poetry, a mnemonic based on the nonsense word yamātārājabhānasalagā has been employed. In this word, the syllables correspond to the names of three syllable feet, (like anapests and dactyls in western poetry) and the three syllable segment starting with a given syllable has the same stress pattern as the foot denoted by that name. (The syllables with macrons are stressed and the others are unstressed.) If you truncate the last two syllables, the stress patterns “wrap around” to create a proper De Bruijn sequence.

And I still haven’t gotten to Gray Codes. Well, I’ll get to that in a later post. Unless I get distracted and never get back to it, which is a real possibility.

(Sources: Wikipedia on Sankrit Prosody and De Bruijn Sequences, and Professor Stewart’s Cabinet of Mathematical Curiosities by Ian Stewart.)

1. Bryce Herdt says:

XOXOOOOOXXXOXXOO
Let’s see…
ooooo oooox xxxox oooxx
xxoxx ooxox xxoox ooxxx
oxooo xoxxo oxoxo xoxoo
oxxoo xooxo oxxxo xoooo
Yep, that’s all of ’em!

2. munizao says:

Nice!