Matpic
mathematics, in pictures
Series

De bruijn — the series

6 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    part 1 · computation
  2. 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.

    part 2 · computation
  3. 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.

    part 3 · computation
  4. 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.

    part 4 · computation
  5. 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.

    part 5 · computation
  6. 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.

    part 6 · computation

All series