Matpic
mathematics, in pictures
Theme

Counting the same thing twice — page 4

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.
At most 3 of the 7 arcs can pairwise meet. The 7 elements arranged round a circle with the 7 arcs of 3 consecutive drawn, and the largest collection of arcs that pairwise intersect picked out. Discrete

The largest family that always meets

Change the question from "no two comparable" to "every two share an element" and the answer changes shape. The best antichain is a whole layer; the best intersecting family is a star, and the proof is a circle.

 16 ways to sort it. A small order with its 16 linear extensions counted, and for each incomparable pair the fraction of extensions putting one before the other. Discrete

How many ways to sort it

An order says some things come before others and leaves the rest open. Counting the orderings consistent with it measures how much is still unknown — and the counting is as hard as any counting problem gets.

 The two supplements, and the residue classes that decide them. A table of odd primes with the Legendre symbols of minus one and two beside the residue of p modulo four and modulo eight. Number

The two supplements, and where the eight comes from

The main law relates two odd primes to each other and says nothing about −1 or about 2. Those two are settled separately, by their own counts, and the answers arrive modulo four and modulo eight — which is a clue about where the whole subject is really taking place.

 Multiplication by 3 modulo 11, and the sign of the shuffle. Residues in two rows joined by strings showing where multiplication sends each one, with a strip beneath comparing the sign of the shuffle to the Legendre symbol for every multiplier. Number

The symbol is the sign of a shuffle

Multiplying every residue modulo p by a fixed number rearranges them. That rearrangement is a permutation, permutations have a sign, and the sign is exactly the Legendre symbol — so a question about squares becomes a question about crossings.

 The rationals covered by intervals of total length 0.1800. Intervals of rapidly shrinking length placed around the rationals of the unit interval in the order they are listed, with the union of them drawn as a single band beneath. Analysis

Covering a set from outside

To say how long a set is, cover it with intervals and add their lengths, then take the smallest total any covering achieves. That definition is short, obviously right for an interval, and gives the rationals a length of nothing.

 A game that stops, over totals 0 to 5. States in a row with arrows up and down between them and the two ends absorbing, above a table of the expected number of steps and the chance of ending at the top from each start. Probability

The chain that stops

Give a chain a state it cannot leave and there is no long run to find — every walk ends. What is worth computing instead is how long it lasts and where it finishes, and both are exact answers to a linear system rather than limits of anything.

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

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.

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

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.

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

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.

 The share that provably comes down. The proportion of starting values that fall below their own start within k steps, plotted against k up to 12. The proportion rises towards one; at the largest k drawn it is 0.94. Dynamics

Almost every number comes down

The Collatz conjecture is open and a great deal about it is not. Whether a number falls below its own start in the first few steps is decided entirely by its remainder on division by a power of two, and the share of numbers for which it happens can be counted exactly.

 Seats to districts and to parties at once. A 4 by 3 table of seats, with every row total and every column total prescribed. The entries come from scaling the votes by one factor per row and one per column and rounding, and all the totals come out exactly right. Applied

Seats to parties and places at once

Seats can be given to regions in proportion to one list of populations, and no rule does it perfectly. Ask for seats to regions and to parties simultaneously and the object stops being a list — and the impossibility that closed the subject does not apply.

 A cheapest assignment, and the proof that it is cheapest. A 4 by 4 cost table with the cheapest assignment marked, and a row price and column price beside each. Every used cell's two prices add to its cost, and the prices total the assignment's cost. Applied

A price for every person and task

The cheapest assignment can be found without comparing it to any other. Attach a number to each person and each task so that no pair's two numbers exceed its cost, and if the numbers add to an assignment's total, that assignment is cheapest — proved, by an argument that never mentions the alternatives.

 Where the two procedures part company. A table of 3 judges' verdicts on two premises and the conclusion each is committed to, with the two majorities at the foot disagreeing about the conclusion. Applied

Deciding the premises or the conclusion

A body that cannot be both decisive and coherent has to choose which. The two live options are to vote on the reasons and let the verdict follow, or to vote on the verdict and let the reasons look after themselves — and they reach opposite answers on exactly the profiles the impossibility identifies.

 One piece, and connected, are different thresholds. Two curves against the average degree for graphs of 400 points: the largest component's share, rising from an average degree of one, and the probability of connectivity, rising only near the logarithm of the point count. Probability

Two thresholds, not one

A random graph acquires a piece holding most of its points at average degree one, and is still not connected. Connectivity waits until the average degree reaches the logarithm of the size, and what holds it up is the very last isolated point.

 A triangle appears when the count says it should. The measured probability of containing a triangle against the edge chance, on graphs of 200 points, beside the expected number of triangles capped at one. Probability

Finding a threshold with two moments

Every monotone property of a random graph has a threshold, and locating one is nearly always the same two calculations — count what the property needs, and check the count does not concentrate on rare cases. The triangle is where the method is cleanest.

 The primes below 100,000, by remainder mod 4. A bar for each remainder on division by 4, showing how many primes below 100000 leave it. The 2 classes sharing no factor with 4 hold near-equal counts; the rest are empty or hold one prime. Number

Infinitely many of one kind

Euclid's argument produces a prime nobody had listed, and says nothing about what it looks like. Ask for infinitely many primes ending in 3, or leaving a remainder of 1 on division by 4, and the same construction has to be aimed — and for most targets nobody knows how to aim it.

 Five families of primes, counted below 100,000. Five counting curves on logarithmic axes: every prime, the primes one more than a multiple of four, the twin pairs, the primes one more than a square, and the Mersenne primes. Two of the five families are known to be infinite and three are open questions. Number

Which infinitudes are proved

The primes never stop, and neither — apparently — do the twin pairs, the primes one more than a square, or the Mersenne primes. Three of those four statements are theorems and one is not, and counting the members of each family tells nobody which.

 Two hundred and forty roots, built and counted. An eight by eight grid whose upper cells stand for the pairs of coordinates a root can use, beside bars counting how many roots stand at each angle from a given root: 1, 56, 126, 56 and 1. Algebra

Two hundred and forty directions

The quaternions have twenty-four units and they are the vertices of the most symmetric object in four dimensions. Eight dimensions has two hundred and forty of them, and the quaternions turn out to be how they are built — twice over, with a hundred and ninety-two left to explain.

 Every point of a hull, as a mixture of three of 11 points. A scatter of points with its convex hull outlined, and several interior points each shown inside a triangle of three of the scattered points, found by trying every triple. Analysis

Three points, however many there are

A point inside the hull of a thousand points is inside the hull of three of them. Any four points split into two groups whose hulls meet. And a family of convex sets, every three of which have a common point, has one common to all — three, in each case, being one more than the dimension.

 The largest code at each length, distance 3, against four bounds. A table with one row per word length, giving the exact size of the largest code of that length at the stated minimum distance and the values of the Singleton, Hamming, Plotkin and Gilbert-Varshamov bounds. Computation

The best a code can be

A code is a set of words chosen far apart, and every construction answers "here is one" rather than "here is the best". The best can be computed at small lengths, and putting four classical bounds beside the exact answer shows which of them is doing the work and where none of them is.

 How many codewords lie within each radius, for a [7,3] code over 11 symbols. A bar for each decoding radius, its height the largest number of codewords found inside a ball of that radius around a randomly drawn received word, with the unique-decoding radius and the Johnson radius marked. Computation

Past half the distance

A code of minimum distance five corrects two errors, and every account stops there. Two is the largest number for which the answer is unique — and a decoder that returns a short list instead of one answer reaches considerably further, which can be measured by counting the codewords in a ball.

 The lattice-point count inside a circle, less its area, out to radius 160. A plot of the difference between the number of lattice points in a disc and the disc's area, against radius, with envelopes proportional to the square root and the two-thirds power drawn. Discrete

The dots a circle catches

Pick's theorem gives a lattice polygon's area exactly, with no error term anywhere. Ask a circle the same question and the exactness is gone: the count is the area plus something, the something has been measured for two centuries, and nobody knows how big it is.

 The primes 3 mod 4 against the primes 1 mod 4, out to 30,000. A plot of the difference between the counts of primes in two residue classes, against the bound, showing a persistent lead for one class and where it is lost. Number

Every class, and in equal shares

Euclid's argument aimed at a residue class reaches some classes and stalls at others. The theorem covering all of them is Dirichlet's, its proof abandons arithmetic entirely for analysis, and what it proves is stronger than infinitude — the classes are equal, though not at any point anybody has counted.

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

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.

All themes