Matpic
mathematics, in pictures
Concept

Recursion

A definition that refers to itself on smaller inputs, with a base case to stop it. It is what makes a short definition describe an unbounded object, and the base case is what stops the description from being empty.

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

Pascal's triangle mod 2, 32 rows. Only the odd entries are drawn; the pattern that appears is the Sierpiński triangle.

Pascal's triangle, in two colours

Shade the odd numbers in Pascal's triangle and a fractal appears. Nothing was designed to produce it, and the same shape arrives independently from a completely different construction.

discrete · Pascals triangle The whirling squares. Squares with Fibonacci sides 1, 1, 2, 3, 5, 8, 13, each attached to the long side of what came before. They fill a 13 by 21 rectangle exactly.

The rectangle that eats itself

Cut a square off a golden rectangle and what is left is a golden rectangle. That single property is the whole of the golden ratio, and it explains both what the number really does and most of what is wrongly claimed for it.

geometry · Golden ratio Every triangulation of a 6-gon. All 14 ways of cutting a convex 6-gon into triangles with non-crossing diagonals — the 4th Catalan number, counted by drawing them.

One sequence, counting everything

The number of ways to cut a polygon into triangles is 1, 2, 5, 14, 42. So is the number of ways to bracket a product, the number of binary trees, and the number of paths that never cross a diagonal. They are the same count, and the reason is one picture.

discrete · Catalan numbers The partition 5 + 4 + 2 + 1 and its conjugate. A row of dots for each part, and the same dots read down the columns instead.

A diagram turned on its side

Write a partition as rows of dots, then read the columns instead. Every theorem in this essay is that one move, and the move proves things that no formula suggests.

number · Partitions A closed walk on the 3-cube changing one place at a time. The corners of a 3-dimensional cube with a path through every one of them exactly once, each step moving along an edge, and the last corner one step from the first.

A walk that changes one thing at a time

Counting from nothing to fifteen in binary changes four digits at once somewhere in the middle. There is another order through the same sixteen words in which every step changes exactly one — and it is a closed walk on a four-dimensional cube.

discrete · Hamiltonian cycles The fast-growing hierarchy at its first few ordinals. A table of the fast-growing hierarchy: one row per ordinal index, one column per argument, with the cells too large to evaluate marked as such.

An ordinal as a growth rate

Index a family of functions by the ordinals, each one iterating the last, and the index becomes a measure of how fast a function grows. The point where the index leaves what arithmetic can prove is exactly where the Goodstein sequence became unprovable.

logic · Ordinals The partition product's coefficients to q¹². A row of series coefficients computed by expanding a product, beside the same numbers obtained another way.

Every partition, hidden in a product

Multiply out one factor for each part size and the coefficient of q to the n is the number of partitions of n. Nothing is being approximated: the product is a bookkeeping device that does the counting by multiplying.

number · Partitions The product of (1 − qᵏ), and what survives at 12. The coefficients of the pentagonal product drawn as signed bars, with the partitions into distinct parts that Franklin's move leaves unpaired.

The terms that cancel almost everything

Multiply out the product of 1 − q, 1 − q², 1 − q³ and so on, and nearly every coefficient is zero. What survives is a single plus or minus one at 1, 2, 5, 7, 12, 15 — and the reason is a way of pairing partitions off so that each pair cancels.

number · Partitions An Apollonian gasket, 125 circles in. The Apollonian gasket generated from four mutually tangent circles of curvature −1, 2, 2 and 3, drawn to 4 generations; every curvature in it is a whole number.

Curvatures that stay whole

Four circles touching one another satisfy an equation in their curvatures. Read it as a quadratic and the second solution is the first subtracted from something — so a packing that starts with whole numbers stays whole forever.

geometry · Inversion One word, four objects. The balanced word (()())() drawn as a lattice path, as nested brackets, as a triangulation of a 6-gon and as a binary tree. The four are the same object in four notations, and each is built here from the word itself.

One word, and four objects

A balanced string of brackets, a lattice path, a triangulated polygon and a binary tree are four different-looking things counted by the same numbers. They are not four things that happen to agree — each is a way of writing the others down, and the translation is mechanical.

discrete · Catalan numbers The equation the objects satisfy. A diagram of the decomposition C = 1 + xC², with a table of the first several coefficients computed two ways: by the convolution the equation prescribes, and from the closed form.

The equation a sequence satisfies

Write the whole sequence as the coefficients of one series, and the recursion becomes an equation with a square in it. Solving the equation by the ordinary quadratic formula produces the closed form, the growth rate and the correction term, none of which the recursion offers.

discrete · Catalan numbers A run down a diagonal, and the entry it adds to. 9 rows of Pascal's triangle with 5 entries shaded and the entry they add to marked. The claim is checked by adding the shaded entries: 1 + 3 + 6 + 10 + 15 = 35.

The run that lands one place along

Add up a run of entries down one of Pascal's diagonals and the total is another entry of the triangle — one row further down and one place along. The same triangle holds four more sums of that kind, and each is a different question answered by the same additive rule.

discrete · Pascals triangle 35 routes across a 4 by 3 grid. A grid with each cell holding the number of monotone routes reaching it. The far corner holds 35, which is the binomial coefficient of 7 choose 3.

Every entry counts the routes to it

Turn Pascal's triangle forty-five degrees and it becomes a grid of street corners, with each entry counting the ways of walking there. Identities between the entries then become statements about routes, and the statements are proved by cutting the routes in one place.

discrete · Pascals triangle Every positive rational, in one sequence. The first 32 terms of Stern's diatomic sequence as bars, with the ratios of consecutive terms beneath. Every ratio is in lowest terms, no two agree, and each term counts the hyperbinary representations of its index.

Every rational in one sequence

The tree lists every positive fraction once and needs a tree to do it. One recursion on the whole numbers lists them in a single row — and each term of it counts something nobody was asking about, which is why the enumeration works.

number · Stern brocot Even and Paz's halving, for 4 people. The recursive halving procedure run on a cake valued differently by 4 people: each round's marks and cuts, and the final pieces, each worth at least a 1/4 share to its owner. 8 marks are made.

How many cuts a fair share costs

Every person can be guaranteed a share of a cake worth at least one n-th by their own measure, and the oldest rule that does it asks about n²/2 questions. Splitting the people into halves and the cake at a median mark asks about n log n — and a theorem says nothing can ask fewer. Fairness has a price, and it can be counted.

applied · Fair division Breadth-first levels in a planar triangulation. A Delaunay triangulation of 160 random points with each point coloured by whether it is inside, on or outside the level 4 steps from the centre; that level of 23 points separates 31 from 106.

The few points that cut a flat graph

Any graph that can be drawn without crossings, however large, falls into pieces of at most two thirds once a few points are removed — about the square root of its size, never more than 2.83 times it. A grid shows the square root cannot be beaten, a ring of breadth-first neighbours comes close, and a cycle through a shallow tree finishes the job.

discrete · Planarity Fair bits from a biased coin. 44 flips of a coin biased 0.7 towards 1, read in 22 pairs. Mixed pairs are kept and give their first bit; matched pairs are discarded. Over a long run the output is 50.2% ones, at 0.210 output bits per flip.

Fair bits from an unfair coin

Read a biased coin's flips in pairs, keep 01 as 0 and 10 as 1, and throw away the rest: the output is exactly fair, whatever the bias, and nobody needs to know the bias. The trick wastes most of the coin, the waste can be recycled almost up to the ceiling Shannon's entropy sets — and it fails quietly the moment the flips remember each other.

computation · Pseudorandomness

Named alongside it

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

BijectionCounting two waysAlgebraic identityBinomial coefficientGenerating functionBinaryCatalan numbersLattice pathsParityPartitionBinary treesCombinatorial proof

All concepts