Matpic
mathematics, in pictures
Theme

Counting the same thing twice — page 5

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

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.

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

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.

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

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.

 13 record approximations in 26 turns. The distance from π to each fraction the descent passes, against its denominator, on logarithmic axes. 13 of them beat every fraction with a smaller denominator. Number

The fractions that beat every smaller one

Walking down the tree towards a number produces a sequence of fractions closing in on it. Most of them are steps along the way; a few are the best approximations there are — closer than every fraction with a smaller denominator — and which few is decided by where the turns change direction.

 3 sheets, 8 of 26 words coming back. A table of reduced words in two generators with the sheet each sends the base sheet to. The words returning to it are the covering's subgroup, and the 3 sheets are its cosets. Topology

A covering is a permutation

Describing a covering means saying where each loop sends each sheet, which is a permutation for every generator. So a covering of a wedge of circles is nothing but a homomorphism to a symmetric group, and the subgroup it corresponds to is a stabiliser.

 The Farey tessellation, and a line down to √2 − 1. Semicircles over the unit interval joining every pair of Farey neighbours with denominators up to 13, and a vertical line at √2 − 1. The 6 arcs it crosses are the intervals of the Stern–Brocot descent to √2 − 1, and their turns spell LRRLL. Number

The arcs a line crosses on its way to a number

Draw a semicircle over every pair of neighbouring fractions and the half-plane above the number line is cut into curved triangles that never overlap. A straight line dropped towards any number crosses those arcs one after another, and the arcs it crosses, and the side it leaves each triangle by, are exactly the steps of the Stern–Brocot descent towards that number.

 3 sheets over a surface of genus 2: a surface of genus 4. A 3-sheeted covering of the closed surface of genus 2, drawn as 3 copies of its 8-sided face with each side coloured by its generator and numbered with the sheet it glues to. The Euler characteristic −6 is 3 times −2, and the cover has genus 4. Topology

Covering a surface multiplies its count

A covering of a closed surface is a permutation of the sheets for each edge of the surface's one face — with one condition that a covering of a graph never had to meet. When the condition holds, the cells of the cover can be counted directly, and the count is the base's count times the number of sheets. That multiplication decides which surfaces can cover which, before any cover is built.

 2 sheets branched over 4 points of a sphere: a surface of genus 1. A 2-sheeted branched covering of the sphere with 4 branch points, drawn as 2 rows of sheets over a centre and the branch points, with the sheets joined where each point's permutation cycles them. Counting cells gives Euler characteristic 0, matching the Riemann–Hurwitz formula, and genus 1. Topology

What a branch point subtracts

Let the sheets of a covering meet at a few points and the count stops multiplying — but it fails by an amount that can be read off each point's permutation. Cut the sphere into a star, lift the cells, and the Riemann–Hurwitz formula falls out of a subtraction. The same count then turns out to be necessary and not sufficient.

 The coefficients of (1 + x)¹² sorted by remainder mod 3. The binomial coefficients of the 12th power coloured by the remainder of their index on division by 3, beside the 3 points one plus a root of unity, whose powers averaged pick out each colour's total. Algebra

Every third coefficient

Add every third number in the twelfth row of Pascal's triangle and the answer is 1366 — a third of 4096, rounded up. Which way the rounding goes is decided by two arrows of length one in the complex plane, and the same average over the roots of unity counts dice totals, subsets and necklaces.

 The zeros of x² + y² + z² over GF(5), and of x² + y² over GF(7). Grids of every point over a small prime field with the solutions of a quadratic equation filled in: the three-variable equation drawn as one slice per value of z, beside a two-variable equation with far fewer solutions. Computation

Solutions that come in multiples of p

Count the solutions of x² + y² + z² = 0 in the field with five elements and there are 25; with seven, there are 49. Whenever a system of equations has more unknowns than its total degree, its number of solutions is a multiple of the characteristic — which forces a solution besides zero, and the reason is a sum over the field that vanishes because its non-zero elements form one cycle.

 Three pairs of places sharing one hub. A hub with three spokes of capacity one, the three pairs of outer places each routing half a unit through it, beside the total that can be sent fractionally, in whole units, and the cost of the cheapest set of roads separating every pair. Discrete

When several pairs share the roads

For one pair of places, the most that can travel between them equals the cheapest cut that separates them. Give three pairs a hub of three roads to share and the two numbers come apart: the pairs can send 3/2 between them, while separating every pair costs 2. Two pairs still meet their cut, but only by splitting units in half.

 A network of six places and the tree that holds all fifteen of its cheapest cuts. A network with capacities on its roads beside a tree on the same places, whose edge numbers give the cheapest cut between any two places as the smallest number on the path joining them. Discrete

One tree for every cut

A network of six places has fifteen pairs, and each pair has its own cheapest cut. All fifteen can be read off a tree with five numbers on it: the cheapest cut between any two places is the smallest number on the tree's path between them. Gomory and Hu proved in 1961 that such a tree always exists, and building it takes five cuts, not fifteen.

 A map drawn through the cycle 0 → 1/3 → 1, and the graph its pieces make. The graph of a map made of two straight pieces through a cycle of three points, with the cycle drawn as a staircase, beside a two-node graph showing which piece may follow which and the matrix of that graph. Dynamics

A matrix that counts the returns

Draw a map straight through the cycle 0 → 1/3 → 1 and its two pieces carry each other in a fixed pattern: the left piece only across the right, the right across both. The orbits' words are then walks on a two-node graph, and the number of points that come back after n steps is the trace of that graph's matrix to the nth power — 1, 3, 4, 7, 11, 18 — each one checked by solving for the points exactly.

 Four shapes of perimeter 300 between their inner and outer circles. A square, an ellipse, a Reuleaux triangle and a stadium, each drawn with the largest circle inside it and the smallest circle around it, the ring between the two shaded, with the ring's width and the widest ring allowed. Geometry

Nearly the most means nearly round

A shape that holds almost as much as a circle of the same perimeter must almost be a circle. Bonnesen made that exact: the ring between a convex shape's largest inscribed circle and smallest enclosing circle is never wider than √(L² − 4πA)/π. Three quite different shapes holding 99% of the circle's area all have rings under 9.55 wide, and not one of 200 random convex shapes breaks the bound.

 The states the continued fraction of √61 can be in. A grid of whole-number pairs with the band of reduced states shaded, the pairs that qualify marked, and the cycle of states visited by the expansion of the square root numbered in order. Number

Why the expansion has to repeat

The continued fraction of √61 runs 7; 1, 4, 3, 1, 2, 2, 1, 3, 4, 1, 14 and then starts again. It must: each step's state is a pair of whole numbers trapped in a small band, and only 14 pairs fit. The expansion of √61 visits 11 of them in a cycle, the other 3 form a cycle of their own, and the period reads the same backwards before its last term, which is twice the first.

 A 6-sided die rolled 6 to 40 times: some face missing, and the sum stopped early. Curves of the chance that some face of a die has not yet appeared against the number of rolls, with the inclusion–exclusion sum stopped after one, two and three terms drawn around the exact curve. Probability

A sum stopped early still says something

Inclusion–exclusion corrects an overcount, then the correction's overcount, and so on to the end. Stop after any number of terms and the result is not merely an approximation: after an odd number it is too high and after an even number too low, always. So two or three terms bracket an answer whose full sum is out of reach — as long as the events being counted are rare.

 How many of 8 people get their own hat, against the Poisson with mean 1. Paired bars for each number of people getting their own hat: the exact share of arrangements and the Poisson probability with mean one, nearly equal at every count. Probability

How many get their own hat

The chance that nobody gets their own hat settles on 1/e. The chance that exactly one person does settles on 1/e too, exactly two on 1/(2e), exactly three on 1/(6e) — the Poisson distribution with mean 1. The reason is a set of averages that come out exactly 1 at every size, and the counts reach the limit so fast that eight hats are within six ten-thousandths of it.

 A necklace of 4 orange, 4 blue, 2 green beads, shared fairly with 3 cuts. A row of coloured beads cut at marked places into pieces, each piece labelled with the thief who receives it, so that both thieves get half of every colour. Topology

As many cuts as colours

Two thieves steal a necklace and want half of every colour of bead each. However the beads are strung, they never need more cuts than there are colours — three cuts for three colours, four for four — and sometimes they need every one. The guarantee is the Borsuk–Ulam theorem again, with a point on a sphere read as a way of cutting the necklace, and every necklace of several small kinds has been checked against it.

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

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.

 Permutations of n things, by how many pairs they put in the wrong order. A table whose row n and column k hold the number of permutations of size n whose inversions is k, with each row's total beside it — the plain count the one-variable series gives. Discrete

The coefficient that is a polynomial

Add a second variable to track a statistic and each coefficient stops being a number. Set the new variable to one and the old count comes back untouched; leave it in and the mean of the statistic is a derivative rather than an average.

 The powers of 2 modulo 13, as a ring of 12. The non-zero residues modulo 13 placed on a circle, with the successive powers of 2 joined by straight lines into a closed walk of 12 steps. Number

One residue whose powers are all of them

Fermat's theorem says every order divides p − 1. It does not say that anything has order exactly p − 1, which is a separate and stronger claim — and what forces it is a count of how many numbers share each divisor with p − 1.

 A matching of 4 and a cover of 4. A bipartite graph with its largest matching drawn thick and a smallest set of vertices meeting every edge ringed, the two having the same size. Discrete

What the search has when it fails

A largest matching is easy to find and hard to certify: the claim that nothing larger exists is a claim about every arrangement not tried. The certificate turns out to be free — it is the wreckage of the search that failed.

 A graph whose matching misses 2 of its 10 vertices. A graph with its largest matching drawn thick, a set of vertices ringed, and the pieces left when that set is deleted marked by whether they hold an odd number of vertices. Discrete

The piece that cannot pair off

Take the sides away and the obstruction to a matching changes character completely. It is no longer a shortage of partners; it is a parity, and the quantity that measures it counts pieces of odd size rather than vertices of any size.

 Runs of doubling length in 1/n^2, and the geometric series that bounds them. A bar for the total of each run of terms of 1/n to the 2, with an outlined bar above it for the bound obtained by replacing every term in the run with its largest, the bounds forming a geometric series. Analysis

The repair at the boundary

Where the geometric yardstick says nothing, compare a series with itself at doubled spacing. That one move turns every 1/n^p back into a geometric series, reads the threshold off at p = 1, and then produces an infinite hierarchy of boundaries with no slowest divergent series anywhere in it.

All themes