Matpic
mathematics, in pictures
Concept

Counting

Determining how many members a finite collection has without listing them. The two standard routes are a pairing with something already counted, and a decomposition into pieces whose counts add or multiply.

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

Counting the colourings, by deleting and contracting. A graph beside the two smaller graphs its edge deletion and contraction produce, with the number of proper colourings of each at every number of colours up to 5.

Counting the colourings

Asking whether a graph can be coloured with four colours gives a yes or a no. Asking how many ways there are gives a polynomial — and the polynomial answers the first question, and several others nobody asked.

discrete · Graph colouring 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 How many Latin squares there are, orders 1 to 8. The number of Latin squares of each small order, the ones up to six counted by exhaustive search and the larger ones quoted, on a logarithmic scale.

Nine thousand four hundred and eight

There are four Latin squares of order four once the first row and column are fixed, fifty-six of order five, and nine thousand four hundred and eight of order six. The exact answer is known for eleven orders and for no more — and yet a half-finished square can always be finished.

computation · Latin squares Ordinal sums and products, in normal form. A table of ordinal expressions with their Cantor normal forms and whether the two sides of each pair are equal, above two tick lines drawing one such pair.

One step in front of infinitely many

Put one step before an infinite run of them and nothing has changed; put it after and something has. Ordinal addition records that difference, which is why it is not commutative — and why it keeps information that counting throws away.

logic · Ordinals p(n) to 60, against the Hardy–Ramanujan estimate. The number of partitions of each number up to sixty on a logarithmic scale, with the asymptotic estimate drawn over it and the ratio of the two tabulated.

The size of a number with no formula

There is no closed expression for the number of partitions of n. There is an expression for how large it is — with a square root in the exponent and a π in front — and it is accurate enough that rounding a few terms of its refinement gives the exact count.

number · Partitions Counting walks that never revisit a square. Dots for the ratio of successive counts of self-avoiding walks and for the n-th root of the count, against the number of steps, both approaching a dashed horizontal line at the connective constant.

A walk that may not step where it has been

Forbid a walk on the square grid from ever revisiting a site and the number of possible n-step walks grows like 2.638ⁿ instead of 4ⁿ — a number nobody can write down exactly. On the honeycomb it is exactly √(2 + √2), proved in 2010. And the walks spread out like n to the three-quarters, faster than any ordinary walk, which physicists have used since 1949 and mathematicians still cannot prove.

probability · Random walk Latin squares of order 4, and the ones that are also Sudoku grids. Two 4×4 Latin squares with their 2×2 boxes outlined: one in which every box also holds 1 to 4, and the cyclic square, whose top-left box repeats a symbol. Of all 576 Latin squares of order 4, 288 pass the box test.

A Latin square with boxes

A finished Sudoku is a Latin square of order nine with one extra rule: each 3×3 box holds every digit once. At order four the extra rule keeps exactly half of the 576 Latin squares, the 288 survivors are two grids in disguise, and no puzzle can be pinned down by fewer than four clues. At order nine every one of those questions needed a computer, and the answers are 6.67 × 10²¹ grids, 5.47 billion essentially different ones, and seventeen clues.

computation · Latin squares

Named alongside it

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

Exhaustive searchAsymptoticsEstimateGrowth rateLatin squareAnalytic continuationApproximationAssociativityBijectionCardinalityChromatic numberChromatic polynomial

All concepts