Theme

Counting the same thing twice — page 11

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 function on nine points, and the tree with two marks it becomes. Left: a function on 9 points as arrows, with cycles through 2, 5, 7 and trees hanging into them. Right: the tree Joyal's rule makes from it, a path from head 7 to tail 2 with the same trees hanging below. Discrete

Every function is a tree with two marks

There are n to the n functions from n points to themselves, and n to the n − 2 trees on those points. André Joyal noticed in 1981 that the missing factor of n² is a choice of two points — a head and a tail — and that a function, read the right way, simply is a tree with a head and a tail. The reading turns Cayley's formula into one line and hands over a fact about random trees from the birthday problem.

The 11 trees on 7 points, and how many labellings each has. All trees on 7 points with their numbers of symmetries and of distinct labellings; the labellings add to 16807. Discrete

Almost every tree can be turned over

Cayley's n^(n−2) counts trees with labels on their points. Take the labels off and the count has no formula, because a symmetric shape absorbs labellings: the star on seven points can be labelled only seven ways, the one asymmetric shape 5,040. The bookkeeping that reconciles the two counts says something unexpected — almost every tree, labelled or not, can be turned over onto itself, where almost every graph cannot.

Two ways to cut a hexagon, one total of radii. A cyclic hexagon triangulated two ways with the incircles drawn; the inradii sum to 1.1622 both times. Geometry

A total hung in a temple

Put a polygon's corners on a circle, cut it into triangles, and add up the radii of the circles inscribed in the triangles. Cut it a different way and the total is the same — for all fourteen ways of cutting a hexagon, to every digit. The fact was painted on a wooden tablet in a Japanese temple around 1800, and the reason for it is a theorem about one triangle and the distances from its circumcentre to its sides.

Four lists, merged in pairs, find a cancelling quadruple. A merge tree for four lists of 256 random 24-bit strings: two merges on the low 8 bits, then one on all 24, ending in 1 solution(s). Probability

Four lists find a collision sooner

Two lists of random 24-bit strings need about four thousand entries each before some string appears in both — the birthday bound. Ask instead for one string from each of four lists whose exclusive-or is zero, and lists of a few hundred suffice, because merging the lists in pairs manufactures the near-misses a direct search would have to find by luck. David Wagner's algorithm turns the square root into a cube root, and more lists into smaller roots.

One shared birthday, as a measurement of the year. Histogram over 20000 rooms of the estimate T(T − 1)/2 from the first shared birthday, averaging 361 against 365, spread widely. Probability

Counting a population by its repeats

The birthday problem runs forwards from a known year to the chance of a match. Run it backwards and the matches measure the year: count how many pairs among the draws came out the same, and the number of kinds is about the number of pairs divided by that. It costs the square root of the population rather than a census of it — and when the kinds are unevenly common, what the repeats measure is not how many kinds there are but how many they behave like.

A loop that cannot be undone, and the surface it bounds. The loop aba⁻¹b⁻¹ on the figure eight, which cannot be pulled tight, beside a square whose boundary reads the same word, showing that the loop bounds a surface. Topology

What homology forgets about a loop

Let the letters of a loop commute and the loop group of a space becomes its first homology group: a loop now records only how often it went round each hole. What is thrown away is exactly the loops that bound a surface. On the figure eight that is nearly everything — of the loops of sixty letters that homology calls nought, about one in 6,700 is a loop that actually shrinks.

Pascal's triangle mod 2, and the room for the 2-dimensional projective space. Pascal's triangle with odd entries filled, rows 0 to 15, with row 3 marked as the tangent ledger 1 + a + a² and row 1 as the normal ledger 1 + a. Topology

The room a projective space needs, read off Pascal's triangle

The projective plane cannot sit in three-dimensional space without crossing itself, and the reason can be written as arithmetic: a polynomial that records how a shape twists, which a room must cancel. For the n-dimensional projective space that polynomial is a row of Pascal's triangle read mod 2, its inverse is another row, and the inverse's last term says how many extra dimensions the room must have — exactly enough, at every power of two.

Closing a path into a tour: the crossing pair the counting forces. A path through 10 points in a row, arcs from its two ends to their neighbours, and the crossing pair at step 3 whose two arcs replace that step to make a closed tour. Discrete

Half the neighbours forces a tour

Deciding whether a graph has a closed tour through every point is one of the hardest problems computers are asked to solve. Gabriel Dirac found a condition that settles it in one glance: if every point is joined to at least half the others, a tour exists. The proof is a counting argument on a single path, it runs as an algorithm, and two small graphs show that the half cannot be lowered — while random graphs show how much stronger than necessary it is.

A closed knight's tour of the 8 × 8 board. A 8 by 8 chequered board with a closed polygon joining the centres of all 64 squares in the order a knight visits them. Discrete

The boards a knight can tour

A knight can visit every square of a chessboard once and land a move from where it began. On a 5 × 5 board it cannot, on a 4 × 100 board it cannot, and on a 3 × 8 board it cannot, though on 3 × 10 it can in sixteen ways. Allen Schwenk found in 1991 the complete list of rectangles without a closed tour, and the reasons on it are of two kinds — a colouring that counts squares, and a second colouring that a tour would have to make agree with the first.

The five lunes that can be squared. Five crescents with arc ratios 2:1, 3:1, 3:2, 5:1, 5:3 and their equal-area kites; θ = 45.000°, 34.265°, 26.812°, 23.439°, 16.794°. Geometry

The five crescents that can be squared

The circle cannot be squared, but some regions bounded by circular arcs can: Hippocrates of Chios found a crescent with exactly the area of a triangle around 440 BC. The trick is to make two multiples of π cancel, and it works for a crescent whose two arcs turn through angles in the ratio m to n exactly when an angle defined by a polynomial can be drawn with ruler and compass. That happens for five ratios and no others.

The centre of a circle found with six circles and no straightedge. A circle with two marked points 37.3° apart and the six compass circles that construct its centre. Computation

The centre a compass finds in six circles

A circle is drawn and its centre was never marked. A straightedge alone can never find it again. A compass alone can, from two points on the circle, in six circles — and a search through every construction of five circles or fewer shows that six is the least. The reason six works is an inversion that turns the circle into a straight line; the price of discarding the straightedge is exactly one move.

The price of the centre, arc by arc. 10°: 5, 15°: 4, 20°: 4, 25°: 6, 30°: 3, 35°: 6, 40°: 6, 45°: 5, 50°: 5, 55°: 6, 60°: 2, 65°: 6, 70°: 5, 75°: 4, 80°: 6, 85°: 6, 90°: 5, 95°: 6, 100°: 4, 105°: 4, 110°: 5, 115°: 6, 120°: 6, 125°: 6, 130°: 5, 135°: 5, 140°: 4, 145°: 6, 150°: 3, 155°: 6, 160°: 6, 165°: 4, 170°: 5, 175°: 6. Computation

The arcs that make the centre cheap

Finding a circle's centre with the compass alone, from two points on it, costs six circles when the points are placed with no special relation — and as few as two when the arc between them is 60°. Searching every arc in steps of five degrees maps the price exactly, and it is not a smooth function of the arc: it is a list of coincidences, each one a small number of compass steps that happens to land on a chord equal to the radius.

A trefoil, and how far its tangent turns. The (2, 3) torus knot with tube radius 0.45; total curvature 16.8556 = 5.3653π. Topology

A knot must turn twice, and a little more

Follow a closed curve and add up how far its direction turns. Any closed curve turns through at least one full circle; a knotted one turns through more than two. The proof is a count of hilltops — the total turning equals 2π times the number of highest points the curve has, averaged over every direction to look from — and a curve with a single hilltop in any direction cannot be knotted.

Every pair of rearrangements of four letters, and what the two generate. A 24 by 24 grid of ordered pairs of permutations of four letters: 216 generate S4, 96 generate A4, 264 generate a smaller subgroup. Algebra

Two random shuffles reach every shuffle

Pick two ways of rearranging n letters at random and allow them to be repeated in any order. Almost always the two together reach every rearrangement there is, or every even one — and when they fail, the usual reason is a coincidence about a single letter that both happen to leave alone. Eugen Netto guessed it in 1882 and John Dixon proved it in 1969.

The 3,600 pairs of icosahedral rotations, and what each pair generates. A 60 by 60 grid of ordered pairs of elements of A5 shaded by the order of the subgroup they generate; 2280 generate A5. Algebra

Nineteen copies and no more

Two of the icosahedron's rotations, chosen at random, generate all sixty of them nineteen times in thirty. Philip Hall found the number in 1936 by inclusion and exclusion over every subgroup at once, weighted by the Möbius function of the subgroups' order — and the same count says that nineteen copies of the group, side by side, can still be generated by two elements, while twenty cannot.

The 16 zigzag arrangements of 5 numbers. All alternating permutations of 1..5: 13254, 14253, 14352, 15243, 15342, 23154, 24153, 24351, 25143, 25341, 34152, 34251, 35142, 35241, 45132, 45231. Analysis

The tangent counts zigzags

Arrange the numbers 1 to n so that they go up, down, up, down. There are 1, 1, 2, 5, 16, 61, 272 such arrangements, and those are, multiplied by factorials, the Taylor coefficients of tan x and sec x — the odd lengths from the tangent, the even from the secant. Désiré André proved it in 1879 by splitting a zigzag at its largest number, and the split turns out to be the derivative of the tangent written out term by term.

Thirty-six domino tilings, cancelling in pairs until the signs are added. The 36 domino tilings of a 4×4 board with their determinant terms: unsigned, 18 positive and 18 negative (determinant 0); with Kasteleyn signs, all 36 positive. Discrete

Signs that make a determinant count

Hall's theorem says whether a board can be covered by dominoes. How many ways it can be covered is a different question, and for a general graph a hopeless one — the count is a permanent, and nobody expects an efficient way to compute permanents. On a flat board it is a determinant. Put a minus sign on the vertical pairs in every second column and the thirty-six coverings of a four-by-four board stop cancelling and add up; the chessboard has 12,988,816. A hole in the board breaks the rule in a way a cut repairs, and on K₃,₃, which cannot be drawn flat, no choice among its 512 signings works at all.

Where the equilibria of a random four-by-four game are found. 7 equilibria with supports (1, 1), (3, 2), (4, 3), (13, 12), (14, 13), (34, 23), (134, 123). Applied

Every random game has an odd number of equilibria

Find every equilibrium of eleven thousand random games — pure and mixed, by trying every pair of strategy sets the players might mix over — and the totals are 1, 3, 5, 7, … and never an even number. The count is a sum of signs: equilibria of index +1 outnumber those of −1 by exactly one in every game. The average grows about 28% with each strategy added, and searching for the game with the most turns up the coordination game's 2ⁿ − 1, a pattern that holds only up to five strategies.

A spider's matchings have real roots and its independent sets do not. Spider with legs 3, 3, 3: matching polynomial 1, 9, 27, 32, 12, roots -0.5000, -0.2324, -0.5000, -1.4343; independence polynomial 1, 10, 36, 57, 38, 9, 1, 4 non-real roots. Discrete

The roots every matching polynomial keeps real

Count a graph's matchings by size and make the counts the coefficients of a polynomial. On every one of 35,664 graphs tested, that polynomial has only real roots — a theorem of Heilmann and Lieb from 1972. Count independent sets instead and the roots wander off the axis on a growing share of graphs, but never on a graph without a claw, and matchings are the independent sets of a graph that never has one.

Two triangulations, the same sum of cos 3x, different sums of cos 2x. Cyclic heptagon, triangulations 0 and 29: Σcos3x 1.52896873 / 1.52896873; Σcos2x -0.789261 / -0.467086. Geometry

The sums a triangulation cannot change

The Japanese theorem says the inradii of any triangulation of a cyclic polygon add to the same total. Write the inradius as a sum of cosines of the angles, and the theorem becomes one case of a rule that fits in a line: a sum of f over every angle of every triangle ignores the triangulation exactly when f(x) + f(π − x) is constant. cos 3x qualifies, cos 2x does not, and the proof is the inscribed-angle theorem applied to a single flipped diagonal.

Two rays land at the root of every bulb. Parameter rays 1/3 & 2/3, 1/7 & 2/7, 5/7 & 6/7, 1/15 & 2/15, 13/15 & 14/15, 9/31 & 10/31, 21/31 & 22/31 to depth 160; furthest ray end from its root 0.0197. Algebra

Two rays for every fraction

Seen from far away, every point of the Mandelbrot set's outside has an angle, and the curves of constant angle come in to land on the set. At the root of the p/q bulb exactly two of them land, and their angles are written by the staircase under a line of slope p/q. The limbs those pairs fence off share out the whole circle of angles between them, by the identity Σ φ(q)/(2^q − 1) = 1.

Strings that overlap themselves leave more behind. 00: 253.293; 01: 230.283; 02: 230.299; 03: 230.315; 04: 230.330; 05: 230.345; 06: 230.361; 07: 230.376; 08: 230.390; 09: 230.405; 10: 220.887; 11: 244.784; 12: 222.442; 13: 223.049; 14: 223.575; 15: 224.033; 16: 224.438; 17: 224.798; 18: 225.120; 19: 225.410; 20: 225.673; 21: 225.913; 22: 249.163; 23: 226.334; 24: 226.520; 25: 226.692; 26: 226.852; 27: 227.001; 28: 227.140; 29: 227.270; 30: 227.393; 31: 227.508; 32: 227.617; 33: 250.747; 34: 227.817; 35: 227.910; 36: 227.998; 37: 228.081; 38: 228.161; 39: 228.237; 40: 228.310; 41: 228.380; 42: 228.446; 43: 228.510; 44: 251.598; 45: 228.631; 46: 228.688; 47: 228.743; 48: 228.796; 49: 228.847; 50: 228.896; 51: 228.944; 52: 228.990; 53: 229.035; 54: 229.078; 55: 252.146; 56: 229.161; 57: 229.201; 58: 229.239; 59: 229.277; 60: 229.313; 61: 229.348; 62: 229.383; 63: 229.416; 64: 229.449; 65: 229.481; 66: 252.538; 67: 229.543; 68: 229.572; 69: 229.601; 70: 229.630; 71: 229.657; 72: 229.684; 73: 229.711; 74: 229.737; 75: 229.762; 76: 229.787; 77: 252.837; 78: 229.835; 79: 229.859; 80: 229.882; 81: 229.904; 82: 229.927; 83: 229.948; 84: 229.970; 85: 229.991; 86: 230.011; 87: 230.031; 88: 253.077; 89: 230.071; 90: 230.090; 91: 230.109; 92: 230.128; 93: 230.146; 94: 230.164; 95: 230.182; 96: 230.199; 97: 230.216; 98: 230.233; 99: 253.275. Analysis

What a missing string of digits leaves behind

Strike from the harmonic series every term whose denominator contains 42 and the rest adds up to 228.45. Strike out 99 instead and it adds up to 253.28. The difference is not about which numbers are lost but about waiting: 99 overlaps itself, so it takes 110 random digits on average to turn up where 42 takes 100, and the sum is almost exactly ln 10 times that wait.

Press everything and the odd degrees light. Pressing every vertex lights exactly the odd-degree vertices; all 1024 all-odd-degree graphs on 6 vertices are litable; overall 18259 of 32768. Computation

Half the chance for every silent set

In the lights game where a press toggles only the neighbours, a random network can be lit about 56 times in a hundred when it has an even number of vertices and 44 when odd. The numbers are 0.560562 and 0.439438, they add to one, and they come from a chain: each new vertex raises or lowers the dimension of the silent sets by one, and each dimension halves the chance.

The flip graph of the hexagon, given a direction. Tamari lattice T4: 14 elements 3210, 3200, 3010, 3100, 3000, 0210, 0200, 1010, 0010, 2100, 2000, 0100, 1000, 0000; 21 covering relations; 68 intervals. Discrete

Pairs of trees that count planar maps

Give every flip of a triangulation a direction and the triangulations become an order, the Tamari lattice. Counting the pairs that are in order — 1, 3, 13, 68, 399, 2,530, 16,965, 118,668, 857,956 — gives 2(4n + 1)!/((n + 1)!(3n + 2)!), which is exactly Tutte's 1962 count of planar triangulations. Chapoton noticed the match in 2006; a pair of trees and a map on a sphere turn out to be the same thing.

All themes