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 5 essays across 4 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

Named alongside it

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

AsymptoticsExhaustive searchAnalytic continuationApproximationAssociativityBijectionCardinalityChromatic numberChromatic polynomialCommutativityConvergenceCyclic word

All concepts