---
tag: GY8F3M39R8
kind: object
name: De Bruijn sequence
msc: [68R15, 05A05, 05C45]
sources:
  - url: https://en.wikipedia.org/wiki/De_Bruijn_sequence
same_as:
  wikidata: Q1953457
  wikipedia: De Bruijn sequence
---

## Description

Let $k \ge 1$ and $n \ge 1$ be integers, and let $A$ be an alphabet with $k$ letters.
A *de Bruijn sequence* of order $n$ over $A$ is a cyclic word $w = a_0 a_1 \cdots a_{k^n - 1}$ of length $k^n$ with the following property.
Every word of length $n$ over $A$ occurs exactly once as a cyclic factor $a_i a_{i+1} \cdots a_{i+n-1}$, with indices taken modulo $k^n$.
Such sequences exist for all $k$ and $n$.

## 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|0KFYGSHHF5]] 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|020422MDQF]], it has an [[Eulerian circuit|05NWGBHKSZ]].
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$.

## Explanations

### L1 human

A de Bruijn sequence is a shortest circular string that contains every possible block of a given length.
Think of a lock with a keypad that opens as soon as the last $n$ digits pressed are the code.
Typing a de Bruijn sequence tries every code while pressing far fewer keys than typing each code separately.
For binary codes of length $3$, the circular string $00010111$ contains all eight codes.