De Bruijn Sequences

A cyclic sequence B(k,n) that contains every k-ary string of length n exactly once as a contiguous substring — visualized as an Eulerian path on the De Bruijn graph.

De Bruijn graph — nodes are (n−1)-mers, edges are n-mers
Sequence visualization (each symbol = colored cell)
—
2
3
5
De Bruijn graph G(k,n): nodes are all k-ary strings of length n−1; directed edge from u to v if u's suffix of length n−2 equals v's prefix. Each edge corresponds to a unique n-gram. An Eulerian circuit (visiting every edge exactly once) spells out a De Bruijn sequence of length kⁿ. For k=2, n=3: 8 edges, sequence 00010111. Applications: Gray codes, card tricks, DNA sequencing, pseudo-random number generation.