The basic principle of the De Bruijn sequence is that for an alphabet of $k$ letters all combinations of $n$-letter words can be found in a sequence of length $k^n$ letters. For example, given the possibility of any ATM pin containing 4 digits (0-9), there is a sequence of $10^4=10000$ digits which contains every possible pin. The length of the De Bruijn sequence is the same as the number of permutations of the letters.

The question is whether this principle extends to words in which the letters are not allowed to repeat. For example, mechanical door combinations do allow the code to repeat the same digit. Imagine a 5-digit mechanical door lock with buttons numbered 1,2,3,4,5. The code is 4-digits long and digits may not be repeated, so there are $5x4x3x2 = 120$ possible combinations.

Does that imply that there is a 120-digit De Bruijn sequence which contains all possible codes for the mechanical lock?



Assume that such a sequence existed. Without loss of generality (relabel the digits) we can assume that the sequence begins with 12345... What could the next digit be? It cannot be any of 2,3,4,5 for then there would be a run of 5 digits such that this digits appears twice, which was explicitly forbidden. Therefore the sixth digit needs to be a 1. Repeating the argument we see that the seventh number must be a 2, the eight a 3, the ninth a 4, and the tenth a 5, at which point we have repeated the sequence 12345 way too soon.

  • $\begingroup$ This sounds like a dup, walks like a dup and talks like dup... But I could not find one :-( $\endgroup$ – Jyrki Lahtonen Apr 28 '15 at 8:09
  • $\begingroup$ That make sense except the last sentence. In a De Bruijn sequence you cannot ever repeat any word-length sequence, otherwise it would impossible to express all possible words use only n^k letters. $\endgroup$ – Tyler Durden Apr 28 '15 at 13:34
  • $\begingroup$ @TylerDurden: Well, my goal was to arrive at the contradiction starting from the assumption that such a sequence would exist. The conclusion is that the sequence you are looking for does not exist. $\endgroup$ – Jyrki Lahtonen Apr 29 '15 at 6:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.