# De Bruijn sequence

A **de Bruijn sequence** of order \( n \) on an alphabet of \( k \) symbols is a cyclic sequence of \( k^{n} \) symbols in which every possible length-\( n \) string over the alphabet occurs exactly once as a block of consecutive symbols, including across the wraparound from the end to the beginning.<sup>[1](https://classes.golem.ph.utexas.edu/category/2015/01/mathematics_and_magic_the_de_b.html)</sup> For example, the circular binary string 0001110100 contains each of the eight binary strings of length 3 (000, 001, 010, 011, 100, 101, 110, 111) exactly once, and it is as short as possible because a sequence containing each 3-mer once needs at least \( 2^{3} = 8 \) symbols.<sup>[2](https://pmc.ncbi.nlm.nih.gov/articles/PMC5531759/)</sup> The sequences are named after the Dutch mathematician [Nicolaas Govert de Bruijn](https://www.edgepedia.org/nicolaas-govert-de-bruijn), who rediscovered them in the 1940s together with an independent proof of the theorem that counts them.<sup>[3](https://www.mdpi.com/2227-7390/14/9/1424)</sup>

| Key fact | Detail |
|---|---|
| Definition | A cyclic string of \( k^{n} \) symbols in which each length-\( n \) string over a \( k \)-symbol alphabet appears exactly once as consecutive characters<sup>[1](https://classes.golem.ph.utexas.edu/category/2015/01/mathematics_and_magic_the_de_b.html)</sup> |
| Count | The number of \( k \)-ary de Bruijn sequences of order \( n \) is \( (k!)^{k^{n-1}} / k^{n} \)<sup>[4](https://debruijnsequence.org/db/graph)</sup> |
| Graph model | De Bruijn sequences correspond one-to-one with Euler cycles in the de Bruijn graph \( G(n{-}1,k) \), obtained by reading edge labels along the cycle<sup>[5](https://debruijnsequence.org/db/random)</sup> |
| Graph structure | \( G(n,k) \) has all \( k \)-ary strings of length \( n \) as vertices; every vertex has in-degree and out-degree \( k \), so the graph is Eulerian<sup>[4](https://debruijnsequence.org/db/graph)</sup> |
| Greedy construction | The Prefer-1 algorithm (Martin 1934, Ford 1957) seeds with \( 0^{n-1} \) and repeatedly appends the largest bit that does not create a duplicate length-\( n \) substring<sup>[6](https://profs.scienze.univr.it/~liptak/FundBA/files/SawadaDB.pdf)</sup> |
| Earliest record | Examples appear in early Sanskrit prosody of the 6th century BCE<sup>[6](https://profs.scienze.univr.it/~liptak/FundBA/files/SawadaDB.pdf)</sup> |
| Applications | Genome assembly, cipher locks, card tricks, and finding bit positions in computer words<sup>[2](https://pmc.ncbi.nlm.nih.gov/articles/PMC5531759/)</sup><sup> • </sup><sup>[7](https://debruijnsequence.org/db/app)</sup> |

## Definition and basic properties

Writing the sequence as \( B(k,n) \), the defining property is that the \( k^{n} \) windows of \( n \) consecutive symbols, taken cyclically, exhaust all \( k^{n} \) possible strings with no repetition. Because the sequence is cyclic, appending the first \( n-1 \) symbols to a linear copy of it produces a non-cyclic string of length \( k^{n} + n - 1 \) that still contains every length-\( n \) string exactly once.<sup>[1](https://classes.golem.ph.utexas.edu/category/2015/01/mathematics_and_magic_the_de_b.html)</sup>

The count of distinct sequences follows from Euler-cycle counting in the de Bruijn graph. Applying the BEST theorem, the total number of \( k \)-ary de Bruijn sequences of order \( n \) is

\[ \frac{(k!)^{k^{n-1}}}{k^{n}}. \]

For the binary alphabet this becomes \( 2^{2^{n-1} - n} \), so the number of sequences grows very quickly with the order.<sup>[4](https://debruijnsequence.org/db/graph)</sup>

## The de Bruijn graph

The standard construction treats the sequence as a tour in a directed graph. Given an alphabet of size \( k \), the de Bruijn graph of order \( n \), written \( G(n,k) \), has as vertices all \( k \)-ary strings of length \( n \), with a directed edge from \( u = u_{1}u_{2}\cdots u_{n} \) to \( v = v_{1}v_{2}\cdots v_{n} \) whenever the last \( n-1 \) symbols of \( u \) equal the first \( n-1 \) symbols of \( v \); each edge is labeled by \( v_{n} \).<sup>[4](https://debruijnsequence.org/db/graph)</sup> Each length-\( (n+1) \) string corresponds to exactly one edge, recovered from a vertex together with an outgoing edge label.<sup>[6](https://profs.scienze.univr.it/~liptak/FundBA/files/SawadaDB.pdf)</sup>

Two cycle types produce sequences. Reading the edge labels along a **Hamilton cycle** in \( G(n,k) \) yields a de Bruijn sequence of order \( n \).<sup>[4](https://debruijnsequence.org/db/graph)</sup> Reading the edge labels along an **Euler cycle**, which visits every edge exactly once, yields a de Bruijn sequence of order \( n+1 \), because \( G(n,k) \) is the line graph of \( G(n-1,k) \) and an Euler cycle in \( G(n-1,k) \) corresponds to a Hamilton cycle in \( G(n,k) \).<sup>[4](https://debruijnsequence.org/db/graph)</sup><sup> • </sup><sup>[8](https://staff.dc.uba.ar/becher/papers/edb.pdf)</sup> A de Bruijn sequence of order \( n \) is therefore in one-to-one correspondence with an Euler cycle in \( G(n-1,k) \).<sup>[5](https://debruijnsequence.org/db/random)</sup>

The Euler-cycle route is the practical one because the graph is always Eulerian: \( G(n,k) \) is connected, and every vertex has in-degree and out-degree \( k \), satisfying Euler's condition that a directed graph has an Euler cycle when it is strongly connected and every vertex is balanced.<sup>[4](https://debruijnsequence.org/db/graph)</sup><sup> • </sup><sup>[6](https://profs.scienze.univr.it/~liptak/FundBA/files/SawadaDB.pdf)</sup> Finding an Euler cycle is solvable in time linear in the size of the graph, but storing the graph requires exponential \( O(k^{n}) \) space, so this direct approach carries an exponential memory cost and an exponential delay before the first symbol can be output.<sup>[4](https://debruijnsequence.org/db/graph)</sup>

## Constructions

**Greedy algorithms.** The Prefer-1 construction, due to Martin (1934) and Ford (1957), starts from the seed \( 0^{n-1} \) and repeatedly appends the largest bit that does not create a duplicate length-\( n \) substring, removing the seed at the end. For \( n = 4 \) it builds 000, 0001, 00011, 000111, and so on, eventually producing a full de Bruijn sequence.<sup>[6](https://profs.scienze.univr.it/~liptak/FundBA/files/SawadaDB.pdf)</sup>

**Euler-cycle algorithms.** Fleury's algorithm implements the principle "do not burn bridges": never traverse an edge if using it would leave the remaining graph disconnected. It computes a spanning in-tree (arborescence) rooted at a chosen vertex, places each tree edge last on its vertex's adjacency list, and then traverses edges depth-first, always taking the first unused edge. This cycle-joining idea underlies all the successor-rule constructions, and the lexicographically smallest Euler cycle can be generated by cycle joining.<sup>[4](https://debruijnsequence.org/db/graph)</sup> The Hierholzer algorithm uses the same joining idea: build a cycle from an arbitrary vertex, then repeatedly splice in new disjoint cycles from vertices already on the cycle until no edges remain.<sup>[6](https://profs.scienze.univr.it/~liptak/FundBA/files/SawadaDB.pdf)</sup>

**Preference tables.** A preference table, also called a look-up table, specifies the exact order in which edges are visited at each vertex in Fleury's algorithm. Given a table and a root vertex, the construction succeeds when the last edge from each non-root vertex forms a spanning in-tree to the root. For the Prefer-largest construction on \( G(3,2) \), the only valid root is 000; for Prefer-same, either 010 or 101 works.<sup>[4](https://debruijnsequence.org/db/graph)</sup>

**Random generation.** Because each Euler cycle corresponds to a unique rooted spanning in-tree, a de Bruijn sequence can be generated uniformly at random by choosing a random arborescence and randomly ordering the remaining outgoing edges at each vertex. For Eulerian graphs, a uniformly random arborescence can be produced by a random backwards walk that records, on each vertex's first visit, the edge used to reach it.<sup>[5](https://debruijnsequence.org/db/random)</sup>

## History

Examples of de Bruijn sequences appear in early Sanskrit prosody from the 6th century BCE. In 1894, Rivière questioned whether such a sequence exists for arbitrary \( n \); Flye Sainte-Marie solved the question the same year. The sequences were later independently rediscovered by de Bruijn in the 1940s, along with an independent proof of the counting theorem.<sup>[6](https://profs.scienze.univr.it/~liptak/FundBA/files/SawadaDB.pdf)</sup><sup> • </sup><sup>[3](https://www.mdpi.com/2227-7390/14/9/1424)</sup>

## Applications

**Genome assembly.** In DNA sequencing, the de Bruijn graph construction assigns every possible \( k \)-mer to an edge between overlapping \( (k-1) \)-mers, so an Eulerian cycle in the graph spells a shortest cyclic superstring containing each \( k \)-mer exactly once. Because the graph is balanced, Euler's algorithm constructs the cycle and thereby solves the superstring problem. Sequence assemblers apply the same construction to the \( k \)-mers actually observed in sequencing reads rather than all possible ones, converting a question about Hamiltonian cycles into one about Eulerian cycles.<sup>[2](https://pmc.ncbi.nlm.nih.gov/articles/PMC5531759/)</sup> The assembly variant is computationally harder than the complete graph: the Eulerian Extension problem, which asks for the smallest set of added nodes and edges that makes a read-derived de Bruijn graph Eulerian, is NP-hard, and remains NP-hard even when no new nodes may be added.<sup>[9](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.12)</sup>

**Cipher locks.** A classic application from Fredricksen's 1982 survey is the cipher lock: a de Bruijn sequence, including the wraparound, gives the shortest string of button presses that is guaranteed to contain every possible access code, since each length-\( n \) window is a distinct code.<sup>[7](https://debruijnsequence.org/db/app)</sup>

**Card tricks.** The counting property supports magic tricks in which a sequence of \( k^{n} \) arranged cards lets a magician identify which length-\( n \) window an audience member has seen, because every possible window occurs exactly once.<sup>[1](https://classes.golem.ph.utexas.edu/category/2015/01/mathematics_and_magic_the_de_b.html)</sup>

When the alphabet contains three or more symbols, any [Hamiltonian cycle](https://www.edgepedia.org/hamiltonian-cycle) of a de Bruijn graph can be turned into an Eulerian cycle of that same graph.<sup>[8](https://staff.dc.uba.ar/becher/papers/edb.pdf)</sup> Beyond the full set of strings, universal-cycle constructions produce sequences for restricted sets, such as weight-range sequences covering all length-\( n \) strings whose weights fall in a specified range, and maximum-length sequences avoiding a forbidden substring \( 0^{z} \).<sup>[5](https://debruijnsequence.org/db/random)</sup>

## References

1. [Mathematics and Magic: the de Bruijn Card Trick, The n-Category Café](https://classes.golem.ph.utexas.edu/category/2015/01/mathematics_and_magic_the_de_b.html)
2. [Why are de Bruijn graphs useful for genome assembly?, PMC](https://pmc.ncbi.nlm.nih.gov/articles/PMC5531759/)
3. [The Cross-Joint Method and Generation of De Bruijn Sequences, Mathematics (MDPI)](https://www.mdpi.com/2227-7390/14/9/1424)
4. [De Bruijn Sequences and Universal Cycles: graph model and Euler cycles, debruijnsequence.org](https://debruijnsequence.org/db/graph)
5. [De Bruijn Sequences and Universal Cycles: random generation, debruijnsequence.org](https://debruijnsequence.org/db/random)
6. [De Bruijn Sequence Constructions, lecture notes by Joe Sawada, University of Guelph](https://profs.scienze.univr.it/~liptak/FundBA/files/SawadaDB.pdf)
7. [De Bruijn Sequences and Universal Cycles: applications, debruijnsequence.org](https://debruijnsequence.org/db/app)
8. [Becher, V., Heiber, P. (2011). On extending de Bruijn sequences. Information Processing Letters 111, 930–932](https://staff.dc.uba.ar/becher/papers/edb.pdf)
9. [Making de Bruijn Graphs Eulerian, CPM 2022, Dagstuhl](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.12)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Combinatorics › Enumerative combinatorics › Combinatorics on words › De Bruijn sequences and universal cycles*

*Initially written Sep 17, 2026 · Reviewed: Sep 17, 2026; Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license