De Bruijn sequence

In mathematics, a de Bruijn sequence in combinatorics is a cyclic sequence from a given alphabet A of size m, of length

N = mⁿ

for which every possible subsequence of length n in A is present exactly once.

For example, with

m = 2, n = 3, A = {0,1}

one can take

11100010.

For

m = 2, n = 5, A = {0,1}

one can take

01000111110111001101011000001010.

References

• de Bruijn, N. G. "A Combinatorial Problem." Koninklijke Nederlandse Akademie v. Wetenschappen 49, 758-764, 1946.

External links

• From MathWorld: [1]
• Applet generator: [2]