Matpic
mathematics, in pictures
Theme

Counting the same thing twice — page 1

One collection, counted by two different methods, and an identity that falls out because both answers have to agree. The proof is the pair of counts.
The Stern–Brocot tree to depth 4. Every positive rational, each appearing exactly once, generated by taking mediants. Number

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.

 The divisors of 60. Every divisor as a lattice point, one axis per prime, joined when one divides the other by a single prime. Number

The shape of a number's divisors

Lay a number's divisors out as a lattice with one axis per prime, and two of the most useful facts in arithmetic stop being formulas and become the width and the corner of a rectangle.

 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. Number

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.

 Necklaces of 5 beads in 2 colours. Every string of beads, grouped by the rotations that carry one onto another. Number

Necklaces that prove a theorem

Thread five beads in two colours, thirty-two ways. Two of them are all one colour; the other thirty fall into rings of five. That count, and nothing else, is Fermat's little theorem.

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

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.

 Counting a 5 by 3 rectangle two ways. Lattice points in a rectangle cut by a diagonal of slope q over p, coloured by which side they fall. Number

Counting one rectangle, twice

Whether seven is a square modulo eleven, and whether eleven is a square modulo seven, are two unrelated-looking questions. Their answers are linked, and the link is a rectangle of dots counted along its rows and then along its columns.

 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. Number

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.

 Rotating by φ − 1 of a turn, 21 times. Points on a circle produced by repeatedly turning through the same angle. Dynamics

Three gaps and no more

Turn a circle by the same irrational angle over and over. The points never repeat and never settle, and yet at every single stage the gaps they leave take at most three different lengths — never four, at any number of steps, for any angle.

 The sixteen words of the [7,4] Hamming code. A table of sixteen seven-bit codewords with their data bits, parity bits and weights. Computation

Sixteen spheres that fill a cube

A hundred and twenty-eight seven-bit words, sixteen of them chosen, and a ball of eight around each. Sixteen times eight is a hundred and twenty-eight exactly — so the balls tile the space with nothing left over, and the code wastes nothing at all.

 The non-zero elements of GF(16) as the powers of one of them. A ring of the field's non-zero elements in the order the powers of a primitive element produce them, beside a table of exponents. Computation

Every element is a power of one of them

Pick the right element of a finite field and its powers run through every other non-zero element exactly once before returning to one. Multiplication becomes addition of exponents, and a table of q − 1 entries replaces the whole multiplication table.

 A schedule on 9 points where every pair meets exactly once. Points around a circle with the triples of a Steiner system drawn between them, beside the list of triples. Computation

A schedule where every pair meets once

Sort n people into groups of three so that every two of them share a group exactly once. Two divisions have to come out whole, that rules out most sizes — and at every size the divisions permit, a schedule exists.

 Five rules on one profile of 27 ballots, and 5 different winners. The ballot groups as columns beside a table of five voting rules with the winner each returns and the count that decided it. Applied

Five rules and five winners

Twenty-seven ranked ballots, five entirely reasonable ways of counting them, and five different candidates declared the winner. Every count is correct, every rule is defensible, and the answer turns out to be a property of the rule rather than of the ballots.

 One cake, one halving cut at 4/9, and two measures of it. A cake as a bar with two step valuations above and below it, the cutter's halving cut marked, and a table of both people's exact value of each piece. Applied

One cuts and the other chooses

The oldest rule in fair division promises each of two people at least half the cake by their own measure, and it keeps that promise exactly. It does not promise what the word "fair" is usually asked to carry, and the gap opens the moment the two measures disagree across the cut.

 The 4 stable matchings of the instance, ordered by side one's preference. A Hasse diagram of the stable matchings with the best for side one at the top, beside a table giving the join and the meet of every pair. Applied

The side that proposes wins

An instance usually has several stable matchings, and the set of them is not a heap — it is a lattice, closed under taking the better partner and under taking the worse. The two ends of that lattice are exactly what deferred acceptance returns from the two sides, so whoever proposes decides which end the instance lands on.

 What one more unit of constraint 1 is worth. The optimum of a linear program plotted against one of its right-hand sides, as an exact piecewise linear graph, with the breakpoints marked and each piece's slope named as a dual variable. Applied

What a constraint is worth

The rung below settled that a linear program and its dual reach the same number. This one asks what the dual's variables are, and the answer converts a solution into a rate for every constraint — piecewise constant, zero on the constraints that are not doing any work.

 16 colourings in 6 classes. Every way of colouring the corners, with the ones a motion carries to each other placed on the same row; the number of rows is the number of genuinely different colourings. Algebra

Colourings nobody can tell apart

Sixteen ways to colour four corners in two colours, and only six of them are genuinely different. The count can be got by pooling the sixteen — or by never forming a single class and instead averaging how many colourings each motion leaves untouched.

 All 24 arrangements of 4 objects, and the 9 that move every one. Every permutation of 4 objects drawn as a grid of cells, with the diagonal — where an object stays where it began — shaded, and the arrangements that avoid it entirely marked. Probability

Nobody gets their own hat

Hand back a pile of hats at random and ask for the chance that not one person gets their own. The answer barely moves as the crowd grows — it is a third and a bit at four people, and a third and a bit at four thousand.

 Waiting for all 6 kinds. One bar per new kind: the expected number of draws needed to see a kind not yet seen, rising as fewer of them are left, and adding to 14.70 draws in total. Probability

How long until every one turns up

Draw at random from six equally likely kinds until all six have appeared. The wait is not six draws, and it is not sixty; it is fourteen point seven, and the number is a harmonic sum wearing a hat.

 A lattice polygon of area 22.5. A polygon with all its corners on the integer grid, with the 20 grid points strictly inside and the 7 on its boundary marked; its area is the first count plus half the second, less one. Discrete

Area by counting dots

Draw a polygon with every corner on a grid of dots. Count the dots strictly inside, add half the dots on the edge, subtract one — and the answer is the area, exactly, with no measuring anywhere.

 How many colourings each knot allows. Three knots, and the number of ways their arcs can be coloured with three, five and seven colours under the crossing rule, beside the determinant computed separately from the same crossings. Topology

Colours that count more than three

Three colours prove the trefoil is knotted and say nothing at all about the figure-eight, which refuses them exactly as an unknotted loop does. The repair is to stop colouring and start counting — with five colours, or seven, and with the arithmetic done modulo the number of them.

 A subgroup of 2, and the 4 blocks it cuts the group into. The 8 symmetries of a 4-gon, split into 4 blocks by composing every element onto the subgroup {e, r²}. The blocks all have 2 elements and no element is in two of them. Algebra

The blocks a subgroup cuts out

Take any part of a group that is closed under composition, and it slices the whole group into blocks of its own size that do not overlap. Everything Lagrange's theorem says is arithmetic about that picture — and whether the blocks can be multiplied is a separate question with a surprising answer.

 3 roots, and the two numbers the coefficients already knew. The roots of a degree-3 polynomial, found numerically, with the point they average to. That average, and their product, are readable straight off the coefficients without finding the roots at all. Algebra

What the coefficients already know

Finding the roots of a polynomial is hard and often impossible in closed form. Reading off their sum, their product and how many of them are real is none of those things — those numbers are sitting in the coefficients, and no root-finding is required to get at them.

 5,040 orders, 7 thresholds, one best rule. For each number of candidates passed over, the share of the 5,040 possible arrival orders in which the rule ends up with the best of the 7. The count is exhaustive. Probability

When to stop looking

Candidates arrive one at a time in a random order. Each must be accepted or rejected on the spot, with no going back and no way to know what is still to come. The best possible rule is to look at about a third of them and then take the first one that beats everything seen — and it works about a third of the time, however many there are.

 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. Discrete

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.

All themes