De Bruijn sequence

Remarks

Example: for $k = 2$ and $n = 3$, the word $00010111$ is a de Bruijn sequence. Its eight cyclic factors of length $3$, starting at positions $0$ to $7$, are $000, 001, 010, 101, 011, 111, 110, 100$. These are all the $2^3 = 8$ binary words of length $3$, each once.

Existence follows from graph theory. The de Bruijn graph is the directed graph whose vertices are the words of length $n - 1$, and in which each word $a_1 \cdots a_n$ is an edge from $a_1 \cdots a_{n-1}$ to $a_2 \cdots a_n$. Each vertex has in-degree and out-degree $k$, and the graph is strongly connected. By the directed form of Euler's theorem, it has an Eulerian circuit. Reading the last letters of the edges along this circuit gives a de Bruijn sequence.

The number of distinct de Bruijn sequences of order $n$ over $k$ letters, counted as cyclic words, is $(k!)^{k^{n-1}} / k^n$. For $k = 2$ and $n = 3$ this is $2^4 / 8 = 2$: the words $00010111$ and $00011101$.