Burnside lemma
Named by 3 essays across 3 fields — each of them below, with the objects they name alongside it.
Truth tables up to renaming
There are 256 truth functions of three letters, but many differ only in which letter is called what, or whether a letter or the answer is negated. Counted up to such renamings there are fourteen. For four letters there are 222, for five 616,126 — and almost every function of many letters is changed by every renaming, so the count settles into a simple division.
How many ways a curve can cross itself
A closed curve that crosses itself three times can be drawn in exactly six essentially different ways on a sphere, and twenty in the plane. Four crossings give nineteen and eighty-two; six give 376 and 2,645. Every one of them is a word — the order in which the crossings are met — and a choice of direction at each crossing, and the whole census comes from asking which of those choices close up on a sphere.
How many shapes a tree can take
There are 262,144 labelled trees on eight points and only twenty-three shapes. Labels make counting easy — Cayley's nⁿ⁻² — and shapes make it hard, because a symmetric shape absorbs labellings. The count of shapes comes instead from a recurrence for trees with a root and a theorem of Richard Otter's for taking the root away: in every tree there is exactly one more class of points than of edges. Run to two hundred points, the counts grow like 0.535 × 2.9558ⁿ ÷ n^(5/2), and the same arithmetic counts the alkanes.
Named alongside it
The objects these essays reach for when they reach for this one.
AsymptoticsExhaustive searchAutomorphismCayleys formulaEuler characteristicGenerating functionHomeomorphismHypercubeImmersionOrbitPermutationPlanar graph