Matpic
mathematics, in pictures
Concept

De bruijn sequence

A cyclic sequence of letters in which every word of a fixed length appears exactly once, and in a cycle just long enough to hold them all. One exists for every alphabet and every word length, because the overlaps between consecutive windows form a graph in which every vertex has as many edges leaving as arriving.

Named by 7 essays across one field — each of them below, with the objects they name alongside it.

The de Bruijn graph on 2 letters and words of 3, and the cycle through it. A graph whose vertices are short words and whose arrows are words one letter longer, with a closed walk using every arrow exactly once marked, and the cyclic sequence it spells.

Every word once, around a cycle

A cyclic string of eight bits holds all eight three-bit words, each exactly once — and the reason such a thing exists is that the constraint linking overlapping windows is itself the construction.

computation · De bruijn 6 necklaces, concatenated into a de Bruijn sequence. The Lyndon words of length dividing 4 over 2 letters, listed in lexicographic order and written end to end; the result is the lexicographically least de Bruijn sequence of order 4.

Every necklace, in order

The graph construction needs the whole graph in memory and finds one sequence among hundreds of millions. Listing the necklaces in alphabetical order and writing them end to end needs no graph at all, and produces the smallest of them.

computation · De bruijn A 4-bit register that visits all 15 nonzero states. The first 15 states of a 4-bit linear feedback shift register with taps at 4 and 1, with the bit that leaves the register at each step; the output shows every nonzero window of 4 bits exactly once.

A memory of four bits

A register holding four bits, shifting them along and adding two of them back, runs through all fifteen nonzero states before it repeats. Which two are added back is a question about a polynomial, and getting it wrong costs fourteen of the fifteen.

computation · De bruijn A four-by-four array holding every two-by-two block. A binary array, cyclic in both directions, drawn with its wrapped row and column, in which each of the sixteen two-by-two blocks appears exactly once.

A page that knows where it is

A four-by-four array of bits, cyclic in both directions, in which every two-by-two block appears exactly once. Print it repeatedly across a sheet and any four marks on that sheet are an address.

computation · De bruijn A cycle showing every pair from 5 things exactly once. The complete graph on 5 points with an Eulerian circuit drawn, and the cyclic sequence of symbols it spells; every window of two consecutive symbols is a different pair.

A cycle for every pair

A cyclic sequence in which every window of two consecutive symbols is a different pair of things. For five things it exists and for four it does not, and in both cases there are exactly as many pairs as there are places to put them.

computation · De bruijn Six permutations as six arrows between three symbols. A directed graph with 3 vertices and 6 arrows, one per permutation of 3 symbols in shorthand, every vertex with two arrows in and two out, numbered in the order of an Euler circuit spelling 213231.

Every ordering once, around a cycle

No cycle can show every ordering of three symbols as a window of three: a window holding each symbol once forces the next symbol to repeat the one just dropped, so the sequence has period three and shows three orderings of six. Two repairs work. Write each ordering by its first two entries and the transitions form a balanced graph, so Euler's theorem hands over the cycle at once. Or add a fourth symbol and ask only that each window keep a different relative order — which works too, but no graph explains why.

computation · De bruijn Every ordering of four in thirty-three symbols. 123412314231243121342132413214321: windows 1234 2341 3412 4123 (1231) 2314 3142 1423 4231 (2312) 3124 1243 2431 4312 (3121) (1213) 2134 1342 3421 4213 (2132) 1324 3241 2413 4132 (1321) 3214 2143 1432 4321.

The shortest string holding every ordering

Thirty-three symbols hold all twenty-four orderings of 1, 2, 3, 4 as blocks of four in a row, and no shorter string does. The formula 1! + 2! + … + n! gives the shortest length for up to five symbols and was believed for all of them — until a string of 872 for six beat its 873, and a lower bound posted anonymously on a forum left everything between 867 and 872 open.

computation · De bruijn

Named alongside it

The objects these essays reach for when they reach for this one.

Counting argumentEulerian pathGraphPermutationExhaustive searchGreedy algorithmUniversal cycleConstructionCountingCyclic wordDe bruijn torusDiscrete logarithm

All concepts