Matpic
mathematics, in pictures
Theme

Counting the same thing twice — page 2

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.
Two trees, sharing every edge between them. The cube flattened into a planar graph, with a spanning tree of its corners drawn solid and the leftover edges drawn dashed; the leftover edges join the faces into a second tree, and the two counts add to the number of edges. Topology

Two trees, and every edge in exactly one of them

Euler's formula is usually proved by deleting things until nothing is left. There is a better argument that deletes nothing — a tree through the corners and a tree through the faces, which between them use every edge once and can therefore be counted.

 The gap at a corner of the cube. The 3 faces meeting at one corner of the cube, unfolded onto the page. They leave a gap of 90.0 degrees, and the 8 gaps come to 720 degrees in total. Topology

Seven hundred and twenty degrees of gap

Unfold the faces around any corner of a solid and they do not close up. The gap left over is different at every corner and on every solid, and the gaps always add to two full turns.

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

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.

 The target, multiplied by one harmonic at a time. Four panels, each showing the square wave multiplied by a single sine. The areas cancel exactly except against the harmonics the wave actually contains. Analysis

Where the coefficients come from

The recipe for a square wave has a four over pi in front and a one over three on the second term, and the first rung of this ladder used them without saying where they came from. They come from multiplying by one harmonic and taking the area.

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

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.

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

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.

 A three-coloured triangulation, and the walk that finds a rainbow triangle. A triangle cut into 36 smaller ones, its corners coloured under Sperner's rule. The 9 small triangles carrying all three colours are shaded, and a path enters through a door on one edge and ends inside one of them. Discrete

Three colours force a triangle

Cut a triangle into small ones and colour the corners under one restriction. However the cutting and the colouring are done, some small triangle ends up with all three colours — and the number of them is always odd.

 π(x) against its two estimates, up to 20,000. The ratio of the prime counting function to x over the logarithm of x, and to the logarithmic integral, plotted against x. The first is above one and coming down slowly; the second is close to one throughout. Number

Counting what has no formula

There is no expression that gives the nth prime, and yet the number of primes below a bound is predictable to within a fraction of a per cent — by a function that is not a formula for the primes but an integral of the wrong-looking quantity.

 Between every number and its double. The interval from n to twice n, drawn for n up to 26, with the primes inside each marked. Every interval contains at least one. Number

Always one before the double

A density says what happens on average and permits long empty stretches. This says something a density cannot — that the stretch from any number to twice it contains a prime, at every scale, without exception.

 A matching that covers all 5 of one side. A bipartite graph with every possible pairing drawn thin and one complete matching drawn thick, so that each vertex on the left is joined to a distinct vertex on the right. Discrete

One bottleneck and nothing else

A set of jobs can be filled by distinct people unless some group of jobs has too few candidates between them — and that single obstruction is the only one there is, which is what makes the theorem worth having.

 A product of 3 polynomials, and what its coefficients count. The coefficients of a product of small polynomials, with the combinations of choices that reach one marked total written out beneath it. Discrete

A polynomial that counts

Hang a counting sequence on the powers of a variable and the two ways of combining choices — this and that, this or that — become multiplication and addition, so a recursion turns into an equation and the equation can be solved.

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

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.

 A table of shares written as a lottery over 3 whole assignments. A doubly stochastic table of shares, and beneath it the permutation matrices and weights that add up to it exactly, each drawn as a grid with one marked cell per row. Applied

A lottery over whole assignments

A table of shares in which every person's shares add to one task and every task is exactly covered is never anything more than a mixture of whole assignments — and finding the mixture is a matter of taking one complete assignment out at a time.

 A wedge of 2 circles. Several circles all passing through one common point, each labelled with a generator, so that a loop is a word in those letters. Topology

The subgroup that is freer than the group

A free group on two letters contains a subgroup of index three that is free on four. Nothing about a group makes that plausible; everything about a graph makes it obvious, and the argument is to stop looking at the group and start looking at the space whose loops it is.

 The 91 histograms 12 draws can produce. A triangle whose points are the possible histograms of a fixed number of draws over three faces, each drawn as a dot shaded by how far it is from the true distribution. Probability

When the whole histogram deviates

The rung below priced a rare average. Ask instead for the chance that the whole tally of outcomes comes out wrong, and the exponent is no longer a function of one number — it is a distance between two distributions, and every rare-average rate is a shadow of it.

 Every order of arrival for three partners, and what each player adds. A table with one row per order in which the players could arrive, giving what each adds to the group already present, and the average of each column as that player's share. Applied

The order everybody arrives in

Three people jointly earn nine, and the question is what each is owed. Ask instead what each adds on walking into a room the others are already in, average that over every order they could have arrived in, and four modest conditions leave no other answer.

 The most triangle-free edges on 6 points. A graph on 6 points carrying 9 edges and no triangle, found by examining every graph on those points, with the two sides its edges cross between drawn apart. Discrete

The edge that forces a triangle

A graph on six points can carry nine edges with no three of them closing a triangle. It cannot carry ten. The bound is n²/4, the graphs that achieve it are all the same shape, and both facts fall out of examining every graph there is.

 A largest flow of 5 through two wide ends and a narrow middle. A network with a capacity on every road, the amount a largest flow sends along each, and the cut whose capacity equals that flow's value drawn as a line separating the places. Discrete

The bottleneck is the whole story

However much a network can carry from one place to another, there is a way of cutting it in two whose total capacity is exactly that number. One quantity is a maximum over ways of routing and the other a minimum over ways of severing, and they are never off by even one.

 The widest layer of the subsets of a set of 4. A Hasse diagram of a small order with the widest layer marked, and the largest set of mutually incomparable elements found by examining every subset. Discrete

The widest layer and the longest chain

Order sixteen subsets by inclusion and ask for the largest collection with no two comparable. The answer is the six subsets of size two — the widest layer — and no cleverer collection beats it. Ask instead for the fewest chains covering everything, and the answer is the same number again.

 The orbit of 13/32 under doubling, and its word. A cobweb of the doubling map with one orbit drawn, the interval split in half beneath it, and the letter each step contributes written out in order. Dynamics

The orbit written as a word

Cut the interval in two and record which half each step of an orbit lands in. The orbit becomes an infinite string of two letters, the map becomes the act of deleting the first letter, and questions about trajectories turn into questions about words.

 Whole-number points on x² − 2y² = 1. The branch of the hyperbola x² − 2y² = 1 in the first quadrant, with the whole-number points on it marked and labelled, and the lattice drawn faintly behind. Number

One solution that makes all the others

The equation x² − 2y² = 1 has infinitely many whole-number solutions, and every one of them is a power of the smallest. The multiplication that produces them is what multiplying two numbers of the form a + b√2 comes to when the √2 terms are collected — so an equation about a hyperbola turns out to carry a group.

 The share of arrangements that fix nothing, up to 8 objects. A bar per number of objects, giving the proportion of its arrangements that leave nothing in place, against the horizontal line at 1/e. Analysis

The constant that counts what does not happen

Nothing grows in a shuffled pack of cards, and nothing grows in a factorial. Yet e sits in the middle of both — as the chance that a shuffle leaves nothing in place, and as the base that makes n! nearly a power.

 Points too even to be random. 256 independent random points beside 256 points of a Halton sequence, with the largest mismatch between a box's share of points and its area plotted against the number of points for both. Probability

Points too even to be random

Independent random points clump, and the clumping is what makes the error fall only as the square root. Points chosen to be evenly spread rather than independently beat that rate, and the price is that nothing about them is random at all.

 The expected number of monochromatic sets, and where it drops below one. The logarithm of the expected number of single-coloured 4, 5, 6-point sets in a random two-colouring, plotted against the number of points, with the crossing of one marked for each. Discrete

The colouring nobody has ever seen

Count the monochromatic sets a random colouring is expected to contain. If the average is below one, some colouring has none — and the argument is finished, having produced nothing anyone can look at.

All themes