Matpic
mathematics, in pictures
Concept

Encoding

A rule attaching to each object of one kind a distinct object of another, usually a string of symbols. It turns comparison and computation on the originals into operations on the strings, and its cost is the length those strings need.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

All 16 trees on 4 labelled points. Every tree on 4 labelled points, drawn one by one. There are 16 of them, which is 4 to the power 2.

Sixteen trees on four points

How many ways are there to connect n labelled points into a single tree? The answer is n to the power n minus two, which is a strange enough formula to demand an explanation — and the explanation is a code that turns every tree into a short list of numbers, and every short list of numbers back into a tree.

discrete · labelled trees 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

Named alongside it

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

GraphBijectionCatalan numbersCayleys formulaCountingCounting argumentCyclic wordDe bruijn sequenceEulerian circuitExhaustive searchHierholzer's algorithmLabelled tree

All concepts