Matpic
mathematics, in pictures
Theme

Counting the same thing twice — page 3

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 colours avoid a progression up to 8, and no further. The numbers 1 to 8 in the two colours that avoid three equally spaced numbers in one colour, with the number 9 beside them in both colours and the pattern each choice forces. Discrete

Three in a row on the number line

Colour the numbers one to eight in two colours and it can be arranged that no three equally spaced numbers agree. Add the ninth and it cannot. The structure being forced is arithmetic rather than graphical, and the proof is a different proof.

 A sequence of 3² with no climb and no fall longer than 3. 10 terms plotted in order, each labelled with the longest climb and the longest fall ending at it; the first 9 keep both counters at 3 or below and the last one cannot. Discrete

The sequence that cannot avoid a staircase

Any ten numbers in a row contain four that climb or four that fall. The proof gives every term a pair of counters, notices that no two terms can share a pair, and is finished — with a bound that is exactly right.

 The gluing abab makes a projective plane. A polygon whose edges carry the word abab, with arrows for the direction each edge is glued and the corners coloured by which vertex they become. Topology

A disc sewn to a Möbius band

The band has one boundary curve, and a disc has one boundary curve. Sew them together and the result is the smallest closed surface with one side — the one every other one-sided surface is built out of.

 A sphere over a projective plane, cell by cell. An icosahedron with opposite faces drawn in matching colours, beside the count of cells it has and the count the quotient by the antipodal map has — every number halved, including the Euler characteristic. Topology

Two sheets over a one-sided surface

Above every one-sided surface sits a two-sided one, exactly twice as large, and the map between them forgets which of the two senses of turning a point was carrying. Building it turns a question about sides into a question about covers.

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

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.

 The algebraic numbers, arriving in finite batches. A stretch of the number line with the roots of integer polynomials marked, each at the height of the smallest polynomial that catches it, and the count of polynomials at each height. Logic

Countable, and everywhere

The numbers a polynomial can catch arrive in finite batches, so they can be listed. They are also in every interval, however short. Being listable turns out to say nothing whatever about being sparse.

 How fast an iteration arrives. The distance from the fixed point plotted against the step number on a logarithmic vertical axis, for two ordinary iterations and for Newton's method, whose curve bends downward. Dynamics

How fast the staircase arrives

The slope at a crossing decides whether an orbit reaches it. The same number decides how fast — and when the slope is zero the arithmetic changes kind, from a fixed factor per step to a doubling of the correct digits.

 Where a long orbit of the logistic map spends its time. A histogram of 60000 iterates in 32 bins, with the density the map preserves drawn over it as the exact share each bin should hold. Dynamics

The histogram an orbit leaves

When no single step of an orbit is worth reporting, what is left is where it spends its time. That distribution is not uniform, it does not depend on where the orbit started, and it can be computed in closed form.

 A share of the votes, and a share of the power. Three weighted assemblies, each with the members' share of the votes beside their share of the power counted two independent ways. Applied

A share of the votes is not a share of the power

Give three members four, four and one vote, with five needed to pass. Every winning coalition needs exactly two of them, so all three have equal power — and one of them holds a ninth of the votes.

 Sampling the orders, and how fast the answer arrives. The largest error in the estimated shares against the number of orderings sampled, both on logarithmic axes, with the square-root rate drawn through the first point. Applied

Too many orders to list

The rule is an average over every order the players could have arrived in. At seven players that is five thousand orders and at twenty it is more than there are seconds in the age of the universe — so the average is sampled, and the error falls at a rate that can be measured.

 Every order of arrival for three users of one shared capacity, 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

Sharing a cost that is not the sum of its parts

Three users need capacities three, six and twelve of one shared thing, and serving any group costs the largest of them. Averaging what each adds over every order of arrival divides the bill — and for this family the average collapses to a rule anybody could apply by hand.

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

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.

 A parallelepiped of volume 2.94. The image of the unit cube under a three-by-three matrix, beside the six signed products whose sum is its volume. Algebra

The only function that behaves like a volume

Ask for a function of the columns of a matrix that scales when a column scales, vanishes when two columns agree, and gives one on the identity. Three conditions, and there is exactly one such function in every dimension.

 A lattice of determinant 3, and the ellipse that must hold a point. A lattice with the parallelogram its basis spans, an ellipse centred at the origin, and the nearest non-zero lattice point it contains. Algebra

One point in every big enough shape

A determinant measures a lattice, not the basis that happened to describe it — and that measurement is an exchange rate. Any symmetric convex region with more than four times that area has to swallow a lattice point.

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

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.

 A determinant of −5 and a permanent of 23 from the same six products. The six products of a three-by-three matrix listed once, added with signs to give the determinant and without signs to give the permanent, with a row operation applied to both. Algebra

The same sum without its minus signs

Delete the signs from the determinant's sum over permutations and what is left counts things directly rather than by cancellation. It is a better count and a far worse object — because the cancellation was what made the determinant computable.

 The partition product's coefficients to q¹². A row of series coefficients computed by expanding a product, beside the same numbers obtained another way. Number

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.

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

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.

 Every fifth partition count divides, and the rank that says why. A row of partition counts with the ones in a congruence class marked, and a histogram of partitions sorted by rank. Number

Every fifth one divides

p(4) is 5, p(9) is 30, p(14) is 135, and every partition count at a number leaving four on division by five is divisible by five. Ramanujan read it off a table; the explanation is a way of splitting those partitions into five equal heaps.

 A ray through a knotted tube, crossing it 5 times. A closed surface in space — a tube round a trefoil knot — with a point, a ray from it and every crossing of the surface marked; the parity of the count says which side of the surface the point is on. Topology

Two pieces, in every dimension

A closed curve cuts the plane in two. A closed curve in space cuts nothing at all, and it takes a closed surface to do the job — which is the shape of the general theorem, and the reason the word "dimension" means anything.

 6 necklaces, concatenated into a de Bruijn sequence. The Lyndon words of length dividing 4 over 2 letters, listed in lexicographic order and written end to end; the result is the lexicographically least de Bruijn sequence of order 4. Computation

Every necklace, in order

The graph construction needs the whole graph in memory and finds one sequence among hundreds of millions. Listing the necklaces in alphabetical order and writing them end to end needs no graph at all, and produces the smallest of them.

 A four-by-four array holding every two-by-two block. A binary array, cyclic in both directions, drawn with its wrapped row and column, in which each of the sixteen two-by-two blocks appears exactly once. Computation

A page that knows where it is

A four-by-four array of bits, cyclic in both directions, in which every two-by-two block appears exactly once. Print it repeatedly across a sheet and any four marks on that sheet are an address.

 Eight circles touching three. Three given circles and the eight circles tangent to all of them, each labelled by which of the three it contains and which it lies outside. Geometry

Eight circles touching three

Draw three circles. How many circles touch all three? The answer is eight, the count is a fact about signs rather than about geometry, and the classical way to find them is to move the problem somewhere it becomes easy.

 Everybody's share of the 24 chains. The subsets of a set of 4, each labelled with the fraction of maximal chains it lies on; the shares of any antichain add to at most one, and to exactly one only for a whole layer. Discrete

Everybody's share of the chains

There are twenty-four ways to build a four-element set one element at a time. Every subset lies on some of them, and no two incomparable subsets share one — so an antichain is a set of disjoint shares of a single whole.

All themes