Nicolaas Govert de Bruijn, a noted mathematician, passed away on February 17, 2012, at the age of 93.

He made contributions to many branches of mathematics, but those interested in recreational mathematics will be especially interested in discovery of what is known today as the de Bruijn sequences. What exactly are they and more importantly, how are they used?

If I asked you to list all the possible pairs in which you could combine a 1 and 0, that's simple to do. The possible pairs are 00, 01, 10, 11. If we combine them into one long sequence of numbers, it would look like this: 00011011.

Now, what if I asked you to give me the shortest possible sequence of 0s and 1s that contains all their possible pairs? This is a little trickier, but it turns out that the answer is simply 0011. A quick look and you can find 00, 01, 11 and...wait, what about 10? If you repeat the sequence (00110011...and so on), you'll note that the 10 is found by combining the final 1 of the sequence with the initial 0.

You can't make a shorter cyclic sequence of numbers than 0011 that contains every possible pair of 0s and 1s, so this is a de Bruijn sequence.

In a more general sense, a de Bruijn sequence is the shortest possible cyclic sequence in which given k symbols, you can find all possible permutations of length n. The less technical definition of a de Bruijn sequence is simply “every possible arrangement squeezed into the smallest possible space.”

In our simple example above, we dealt with an “alphabet” of 2 symbols, so k=2, and we were looking for all possible pairs, so n=2. In mathematical notation, this is often simple written as B(k,n), so our example would be B(2,2).

Such sequences are known to have been used as long ago as 200 BCE, but de Bruijn's breakthrough, with help from Tatyana Pavlovna Ehrenfest, was in finding a general approach for determining the sequence for any B(k,n).

If you want to see how challenging this can get as k and n get larger, consider James Grime's combination lock puzzle:



Here, you're using an alphabet of 10 symbols, and looking for every possible sequence of 4 numbers, or B(10,4). Try working out the simpler challenges in the above video, and then watch James Grime's solution video, along with the method used to solve them:



Applying the formula mentioned in the video above, you can quickly determine that B(10,4) is going to be 10⁴, or 10,000 digits long. Fortunately, you only need to find 1 of the many possible de Bruijn sequences.

Besides picking locks, mathematicians have taken advantage of de Bruijn sequences for use in card tricks. Colm Mulcahy explains a basic use in his December 2008 Card Colm column.

Since the study of these sequences is applicable to so many fields, it's amazing where you can find a use for them. Playing around with card tricks based on the de Bruijn sequence led one researcher to discover an improved way to make files smaller.

In the recently-released book Magical Mathematics, authors Persi Diaconis and Ron Graham delve even deeper into de Bruijn sequences and card tricks. You can get a preview of part of that chapter by clicking on the Google Preview button below:



In that book, there are some ingenious uses for de Bruijn sequences with cards, but there's one magician whose work has taken them to an entirely new level. If you're a member of the Magic Café, explore Leo Boudreau's online work, as well as his written work, with de Bruijn sequences. Leo Boudreau work largely involves binary numbers, so if you like his work, learning a good binary number memory system can turn his amazing routines into miracles.

Even with this lengthy post, we've barely delved into only one part of N. G. de Bruijn's body of work. The world was better for having him in it, and he will be truly missed.