TOPICS
Search

de Bruijn Sequence


The shortest circular sequence of length sigma^n such that every string of length n on the alphabet a of size sigma occurs as a contiguous subrange of the sequence described by a. For example, a de Bruijn sequence of order n=2 on the alphabet {a,b,c} is given by {a,a,c,b,b,c,c,a,b}.

A de Bruijn sequence can be generated in the Wolfram Language using DeBruijnSequence[list, n].

Every de Bruijn sequence corresponds to an Eulerian cycle on a de Bruijn graph. Surprisingly, it turns out that the lexicographic sequence of Lyndon words of lengths divisible by n gives the lexicographically smallest de Bruijn sequence (Ruskey).

de Bruijn sequences can be generated by feedback shift registers (Golomb 1967; Ronse 1984; Skiena 1990, p. 196).


See also

de Bruijn Graph, Lyndon Word

Explore with Wolfram|Alpha

References

de Bruijn, N. G. "A Combinatorial Problem." Koninklijke Nederlandse Akademie v. Wetenschappen 49, 758-764, 1946.Golomb, S. W. Shift Register Sequences. San Francisco, CA: Holden-Day, 1967.Good, I. J. "Normal Recurring Decimals." J. London Math. Soc. 21, 167-172, 1946.Knuth, D. E. "Oriented Subtrees of an Arc Digraph." J. Combin. Th. 3, 309-314, 1967.Ronse, C. Feedback Shift Registers. Berlin: Springer-Verlag, 1984.Ruskey, F. "Information on Necklaces, Lyndon Words, de Bruijn Sequences." http://www.theory.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 195-196, 1990.

Referenced on Wolfram|Alpha

de Bruijn Sequence

Cite this as:

Weisstein, Eric W. "de Bruijn Sequence." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/deBruijnSequence.html

Subject classifications