Matpic
mathematics, in pictures
Concept

Bijection

A pairing that matches every member of one collection with exactly one member of another, leaving nothing over on either side. Exhibiting one is how two collections are shown to be the same size, without either of them being counted.

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

One point on the sphere for every point of the plane. Lines from the north pole of a sphere through each of its points land on a plane below, matching the sphere minus one point with the whole plane.

A sphere is a plane plus one point

Remove a single point from a sphere and what is left can be flattened out to cover an infinite plane exactly. The construction is one straight line, repeated.

topology · Stereographic projection 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 Stern–Brocot tree to depth 4. Every positive rational, each appearing exactly once, generated by taking mediants.

Every fraction, exactly once

Take two fractions, add the tops and add the bottoms. That is not how fractions are added, it is not an average, and repeating it produces every positive rational exactly once, already in lowest terms.

number · Stern brocot Rational points on the unit circle. Lines of rational slope through the left-hand point of a circle, each meeting it again at a rational point.

Every triple, on one circle

Draw a line of rational slope through a single point of a circle. Wherever it comes out is a rational point, and clearing the denominators turns it into a Pythagorean triple — so every triple there is comes from one line through one point.

number · Pythagoras One number, two dials: 3 and 5. A grid of remainder pairs, each cell holding the smallest number that leaves those two remainders.

Two dials at once

Watch one number on two clocks with different faces. If the faces share no factor, every pair of readings occurs exactly once — so two remainders name a number, and a hard calculation can be split into two easy ones.

number · Modular arithmetic 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 The diagonal, and the row built to be off the list. A table of rows of ones and zeros with the diagonal marked, and beneath it the row obtained by flipping every diagonal entry.

The row that is not on the list

Write down a list of infinite sequences, any list at all, and there is a rule that builds a sequence missing from it. The rule reads one entry from each row, and it is the single most reused argument in this field.

logic · Diagonalisation A closed interval and an open one, matched point for point. Two number lines, one closed and one open, with arrows showing the countable sequence of points that has to move.

Two injections make a bijection

If each of two collections fits inside the other without collisions, they are the same size. That sounds obvious and is not, because neither injection needs to be onto — and the proof is a rule for deciding which of the two to follow, one chain at a time.

logic · Cardinality One matching that is not stable, and all 24 counted by blocking pairs. An unstable matching with its blocking pair ringed and both members' rankings marked, above an exhaustive census of every matching of the instance by how many blocking pairs it has.

Nobody has a reason to run away

A matching is stable when no two people on opposite sides would both rather have each other than what they have — a condition that names nothing to build and everything to rule out. The surprise is that something always satisfies it, however perverse the rankings are made.

applied · Stable matching 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 Middle thirds removed 6 times over. The interval with its middle third removed, then the middle third of each survivor, and so on. The lengths removed are a geometric series adding to the whole interval.

Almost none of it left, and still uncountably many

Remove the middle third of an interval, then the middle third of each piece left, and keep going. The lengths removed add to exactly the whole interval, so nothing measurable survives — and what survives can be paired off one for one with every point of the interval that was started with.

analysis · Measure A path folded about the first time it touches. A walk from 2 to 4 that touches the axis, with the part before its first touch reflected. The reflection is a path from the mirrored start to the same endpoint, and the correspondence is exact.

The path folded at its first touch

Counting the walks that touch a line looks like a question about a walk's whole history. Fold each one where it first touches, and it becomes a question about where walks end up — which is a binomial coefficient, and is already known.

probability · Random walk The tree of Pythagorean triples. A tree rooted at 3-4-5. Each triple has three children, obtained by three fixed integer matrices, and every primitive triple appears exactly once somewhere in it.

A tree that holds every triple

Three fixed matrices, applied to 3-4-5 over and over, produce every primitive Pythagorean triple there is — each of them once, none of them twice, and with no test for common factors anywhere in the procedure.

number · Pythagoras The permutation (1 3 4 2) drawn as 4 strings, crossing 3 times. A permutation drawn as strings running from a row of numbered pegs to another, with every place two strings cross marked, and the crossing count checked against the number of pairs that are out of order.

The crossings that will not come out even

Draw a rearrangement as strings from one row of pegs to another and count where they cross. The count depends on how the strings are drawn; whether it is odd or even does not, and that single bit is what makes determinants exist and a sliding puzzle unsolvable.

algebra · Permutation parity The fractions, put in a line. A grid whose rows are numerators and columns denominators, walked by antidiagonals, with the place each fraction takes in the list written in its cell and the repeats left blank.

The arithmetic that loses subtraction

Adding one to an infinite collection changes nothing, and neither does doubling it, or squaring it. What that costs is the two operations that were doing the work — an equation between infinite sizes cannot be cancelled, and how many are left stops being a question.

logic · Cardinality A square's worth of points, on a line. A unit square with a point marked, the decimal places of its two coordinates woven into one number, and that number marked on a line beneath.

A line with as many points as a square

Interleave the decimal places of two numbers and one number comes out; take every other place back and the two return. The square has no more points than the segment, and dimension turns out to be invisible to counting.

logic · Cardinality The 3 mutually orthogonal squares of order 4. Every Latin square built from the field of order 4 as a·i + j, one for each non-zero multiplier, with every pair checked orthogonal.

A field's worth of squares

Two orthogonal squares of order five are easy to stumble on. Four of them, every pair orthogonal, is not a stumble — it is one line of arithmetic over a field, and the field supplies as many as the order allows.

computation · Latin squares 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 A determinant counting the 16 spanning trees. A small graph, the minor of its Laplacian, and every one of its spanning trees drawn as thumbnails.

A determinant that counts trees

Write down a graph's Laplacian, strike out one row and its column, take the determinant. The answer is the number of spanning trees — and the minus signs in the determinant are what cancel every subset of edges that is not one.

algebra · Determinant 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 The cube cut into 6 symmetric chains. The subsets of a set of 4 partitioned into 6 chains by the bracket rule, each chain running from size k to size 4 − k and passing once through the middle layer.

The cube cut into chains

Write a subset as a string of brackets, match them the ordinary way, and the unmatched ones say which chain it is on. Six chains cover all sixteen subsets of a four-element set, and the bound and the example arrive together.

discrete · Posets A bad path, and the path it reflects to. Two grids, 6 by 5. On the left a monotone path that dips below the diagonal, with its first offending step marked; on the right the same path with everything after that step reflected, which ends one square right and one square below the corner.

Counting the paths that go wrong

The number of good paths across a grid has no obvious formula. The number of bad ones does, because every bad path can be reflected into a path to a different corner, and that reflection is a perfect matching between two sets nobody chose to relate.

discrete · Catalan numbers 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 Every parity pattern of length up to 12, and each occurring exactly once. A bar for each pattern length, showing the number of distinct parity patterns produced by all remainders of that power of two, which equals the number of remainders at every length.

Every pattern happens exactly once

Choose any sequence of odds and evens and there is exactly one residue class whose orbit follows it, and exactly one fraction that cycles through it forever. The Collatz conjecture is then the statement that only one of those infinitely many cycles is made of whole numbers.

dynamics · Collatz 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 The tree as words in two matrices. 6 nodes of the Stern–Brocot tree, each as the word of turns reaching it, the matrix that word multiplies out to, its two columns as fractions, and the mediant of those columns.

Two matrices that generate the tree

A node of the Stern–Brocot tree is not really a fraction — it is the pair of fractions it lies between. Written as the columns of a matrix, the two turns of the tree become two multiplications, and the determinant that kept everything in lowest terms becomes a property of a product.

number · Stern brocot 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 Minkowski's question-mark function. The graph of Minkowski's function ?(x) on the unit interval: continuous and increasing, sending each Stern–Brocot fraction to the binary fraction in the same position. It sends √2 − 1 to 2/5 and φ − 1 to 2/3.

The function that sends fractions to binary

The Stern–Brocot tree and the tree of binary fractions have exactly the same shape, so there is a function that sends each fraction to the binary fraction in the same position. It is continuous and increasing, it turns every quadratic irrational into an ordinary fraction, and it does all of its rising on a set of numbers so thin that at almost every point its slope is nought.

number · Stern brocot The 6 ways to deal 4 labels between pieces of size 2 and 2. Every way of splitting 4 labels between a piece of size 2 and a piece of size 2, listed as two rows of boxes each. The count is the binomial coefficient that distinguishes a labelled product from an ordinary one.

The product that deals the labels

Multiplying two counting series pairs one choice with another. When the things being counted carry labels, the labels have to be dealt out as well, and the only series that survive the extra bookkeeping are the ones divided by n factorial.

discrete · Generating functions Pollak's circle: one rotation in every n + 1 parks on the line. Several circles of numbered spots, each showing where cars park when every preference in a list is rotated by a fixed amount, with the one rotation that leaves the last spot empty highlighted.

Cars that park, and trees that grow

Three cars arrive at a one-way street with three spaces; each has a favourite space, drives to it, and takes the first free one from there on. Of the 27 lists of favourites, exactly 16 let every car park — the same 16 as the labelled trees on four points. The reason is a circular street with one extra space, on which every list parks and exactly one rotation of it leaves the extra space empty.

discrete · Labelled trees Two ways of counting that agree at every number. For n up to 40, the counts of partitions with gaps of at least two against partitions into parts congruent to 1 or 4 mod 5, on a logarithmic scale, equal at every n, with the second identity's counts beside them.

Two counts that agree for no visible reason

Write 10 as a sum of whole numbers that differ from each other by at least two, and there are six ways. Write 10 as a sum of numbers that each leave 1 or 4 on division by 5, and there are six ways. The same happens for 20 (thirty-one each), for 40 (three hundred and seventy-four each), for every number anyone has checked and every number there is. The two lists look nothing alike, and no one has found a simple way to turn one into the other.

number · Partitions

Named alongside it

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

Counting two waysRecursionBinomial coefficientCounting argumentGenerating functionLattice pathsPartitionStern brocot treeCardinalityCatalan numbersCountabilityModular arithmetic

All concepts