Matpic
mathematics, in pictures
Theme

Counting the same thing twice — page 8

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.
A random labelled tree on 60 points. A tree drawn in horizontal layers by distance from a root point, with the leaves coloured differently from the internal points. Discrete

A random tree is one part in e leaves

Choose a labelled tree on n points uniformly at random. A point is a leaf exactly when its label never appears in the tree's Prüfer code, so the share of leaves is (1 − 1/n)^(n − 2) — half the points for a tree on four, 36.8% for a large one, the reciprocal of e. The whole degree distribution follows the same way: one plus a Poisson count with mean one.

 A line in every direction in the plane over GF(7), in 31 points. A square grid of the points of a small finite plane with the points of a Kakeya set filled, beside a list of the lines it contains, one for each direction. Computation

No set with a line in every direction is small

In the plane over the integers modulo 7 there are 49 points and lines in 8 directions. A set holding a whole line in every direction needs 31 of the points — more than half — and in any dimension such a set fills a fixed share of the space. In the real plane the same sets can have area zero. Over a finite field one polynomial of low degree shows they cannot be small.

 Credit for one prediction, three ways of leaving an input out. Groups of bars, one group for each way of filling in the inputs that are not known, each bar one input's share of the difference between the prediction and the starting value. Applied

What a missing input is worth

A model prices a house at 180 from its size, its garden and its bedrooms, and the question is how much of the price each input is responsible for. Make the inputs the players and the average over orders answers it — once somebody decides what the model says when an input is not known. Three reasonable decisions give bedrooms nothing, nothing, and sixteen, for a model that never reads them.

 Shares on two triangles and a go-between. A network of players with each node labelled by its share of what the whole network earns, and its number of links beneath it. Applied

Cutting a link costs both of its ends the same

Three players, any two of whom can earn 1 together — but only if they are linked. Link all three and each is due a third. Remove one link and the player holding both of the others is due two thirds. Averaging over orders on the game the network allows is the one rule under which breaking any link costs the two players it joined exactly the same, and it pays go-betweens more than their links.

 Loops on a torus that never cross themselves. Squares with opposite edges glued, each carrying one straight loop of a different slope, each labelled with its two crossing counts. Topology

The loops on a torus that never cross themselves

Every loop on a torus is classified by two whole numbers: how often it goes round one way and how often the other. Some classes can be drawn without the loop ever crossing itself and some cannot, and the rule is the oldest in arithmetic — the two numbers must have no common factor. The same two numbers say how often any two loops must meet.

 A twist along the horizontal loop, done once. Squares with opposite edges glued and a shaded horizontal band, showing one loop before and after the torus is twisted along the band. Topology

A twist that carries one loop to another

Cut a torus along a loop, turn one side of the cut once round, and glue it back. Nothing is torn, so every loop that did not cross itself still does not — but a loop of class (0, 1) is now a loop of class (1, 1). Two such twists reach every loop that never crosses itself, by Euclid's algorithm, and the symmetries they generate are exactly the whole-number matrices of determinant one.

All themes