# de Bruijn sequence

## Cycle through all length-k sequences / From Wikipedia, the free encyclopedia

#### Dear Wikiwand AI, let's keep it short by simply answering these key questions:

Can you list the top facts and stats about De Bruijn sequence?

Summarize this article for a 10 year old

In combinatorial mathematics, a **de Bruijn sequence** of order *n* on a size-*k* alphabet *A* is a cyclic sequence in which every possible length-*n* string on *A* occurs exactly once as a substring (i.e., as a *contiguous* subsequence). Such a sequence is denoted by *B*(*k*, *n*) and has length *k*^{n}, which is also the number of distinct strings of length *n* on *A*. Each of these distinct strings, when taken as a substring of *B*(*k*, *n*), must start at a different position, because substrings starting at the same position are not distinct. Therefore, *B*(*k*, *n*) must have *at least* *k*^{n} symbols. And since *B*(*k*, *n*) has *exactly* *k*^{n} symbols, de Bruijn sequences are optimally short with respect to the property of containing every string of length *n* at least once.

The number of distinct de Bruijn sequences *B*(*k*, *n*) is

- ${\dfrac {\left(k!\right)^{k^{n-1}}}{k^{n}}}.$

The sequences are named after the Dutch mathematician Nicolaas Govert de Bruijn, who wrote about them in 1946.^{[1]} As he later wrote,^{[2]} the existence of de Bruijn sequences for each order together with the above properties were first proved, for the case of alphabets with two elements, by Camille Flye Sainte-Marie (1894). The generalization to larger alphabets is due to Tatyana van Aardenne-Ehrenfest and de Bruijn (1951). Automata for recognizing these sequences are denoted as de Bruijn automata.

In most applications, *A* = {0,1}.