Concept

Catalan numbers

The sequence 1, 1, 2, 5, 14, 42 and onward, counting bracket sequences, polygon triangulations and binary trees alike. Each term is computed from the ones before it by a convolution, and the same sequence counts a dozen apparently unrelated families.

Named by 17 essays across 5 fields — each of them below, with the objects they name alongside it.

Every triangulation of a 6-gon. All 14 ways of cutting a convex 6-gon into triangles with non-crossing diagonals — the 4th Catalan number, counted by drawing them.

One sequence, counting everything

The number of ways to cut a polygon into triangles is 1, 2, 5, 14, 42. So is the number of ways to bracket a product, the number of binary trees, and the number of paths that never cross a diagonal. They are the same count, and the reason is one picture.

discrete · Catalan numbers
All 16 trees on 4 labelled points. Every tree on 4 labelled points, drawn one by one. There are 16 of them, which is 4 to the power 2.

Sixteen trees on four points

How many ways are there to connect n labelled points into a single tree? The answer is n to the power n minus two, which is a strange enough formula to demand an explanation — and the explanation is a code that turns every tree into a short list of numbers, and every short list of numbers back into a tree.

discrete · Labelled trees
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.

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.

discrete · Generating functions
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.

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.

discrete · Catalan numbers
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.

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.

discrete · Catalan numbers
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.

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.

discrete · Catalan numbers
The 14 triangulations, joined by single flips. The flip graph of a 6-gon: 14 triangulations drawn as small polygons and joined by 21 edges, one for each pair differing in a single diagonal.

The solid whose corners are triangulations

Take the triangulations of a hexagon as points and join two of them when a single diagonal can be swapped for another. The result is not merely a graph — it is the edge skeleton of a genuine convex polyhedron, with fourteen corners, three square faces and six pentagonal ones.

discrete · Catalan numbers
Permutations of n things, by how many pairs they put in the wrong order. A table whose row n and column k hold the number of permutations of size n whose inversions is k, with each row's total beside it — the plain count the one-variable series gives.

The coefficient that is a polynomial

Add a second variable to track a statistic and each coefficient stops being a number. Set the new variable to one and the old count comes back untouched; leave it in and the mean of the statistic is a derivative rather than an average.

discrete · Generating functions
Every way to pair the edges of a hexagon. Chord diagrams of all 15 pairings of a 6-gon's edges, shaded by the surface each gluing makes: 5 spheres, 10 tori.

Every way to pair a polygon's edges

A hexagon's six edges can be paired in fifteen ways. Glue each pair head to tail and five of the fifteen give a sphere and ten give a torus; an octagon's 105 pairings give 14 spheres, 70 tori and 21 surfaces with two handles. The spheres are exactly the pairings whose chords never cross, and the whole table obeys one recurrence found in 1986.

topology · Surface classification
A random pairing of 24 edges. Chord diagram of one uniformly random pairing of a 24-gon's edges, corners coloured by the vertex they become. a 24-gon with its edges paired at random and glued head to tail: the 24 corners fall into 3 vertices, so the surface has genus 5, against a most possible of 6.

The surface a random gluing makes

Pair the edges of a large polygon at random and glue each pair head to tail. The surface almost always has nearly as many handles as the polygon allows: a thousand edges leave about seven and a half vertices, and the genus is within four of its ceiling of 250. The vertices behave like the cycles of a random permutation, and their average is a harmonic number.

topology · Surface classification
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.

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.

geometry · Inscribed angle
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.

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.

geometry · Inscribed angle
Seven flips between the octagon's farthest triangulations. A shortest flip path of length 7 between two of the 132 triangulations of the octagon.

How far apart two triangulations can be

Any triangulation of a polygon can be turned into any other by flipping one diagonal at a time. On an octagon seven flips always suffice; on a polygon with m vertices the worst case is 2m − 10 flips once m reaches thirteen, a value Sleator, Tarjan and Thurston proved with hyperbolic geometry in 1988. Breadth-first search over all 58,786 triangulations of the 13-gon finds the sixteen.

discrete · Catalan numbers
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.

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.

discrete · Catalan numbers
When to stop tossing a coin. 1:1 2:2 3:3 4:2 5:3 6:2 7:3 8:2 9:3 10:4 11:3 12:4 13:3 14:4 15:3 16:4 17:5 18:4 19:5 20:4 21:5 22:4 23:5 24:4 25:5 26:4 27:5 28:4 29:5 30:6

When to stop tossing a coin

Toss a fair coin as many times as you like and stop whenever you choose; you are paid the proportion of heads so far. Stopping after a first head pays one, so the only question is what to do after a tail. Waiting for the first moment heads lead pays exactly π/4 on average. Waiting for a lead of two pays exactly ln 2. The best possible rule pays about 0.79295, a number known to six decimal places only since 2013 — and it stops when the lead reaches about 0.84 times the square root of the number of tosses, a constant that comes from Brownian motion.

probability · Optimal stopping
A Kloosterman sum, drawn one term at a time. p=1009: K(1,1;p)=20.255823, 2√p=63.529521, angle 71.407°.

A sum that never leaves its circle

Add up e^(2πi(x + x̄)/p) over the nonzero x modulo a prime, where x̄ is the inverse of x. A thousand unit steps could go a thousand units; Kloosterman's sum never goes beyond 2√p, and at a fixed prime its values over every choice of coefficient fall on a semicircle whose moments are the Catalan numbers. Follow one sum through the primes instead and the same semicircle appears — and nobody can prove it.

computation · Finite fields
A curve that crosses a line twelve times. n=6: upper 9,8,7,6,5,4,3,2,1,0,11,10; lower 3,2,1,0,7,6,5,4,11,10,9,8; meanders 1828 of 17424.

Curves that cross a line and close

Draw a closed curve that crosses a straight line 2n times and never crosses itself. Above the line it is a set of nested arches, below it another, and every such curve is a pair of the Catalan number's arch systems that happen to close into one loop. There are 1, 2, 8, 42, 262, 1,828 of them, and every count computed so far grows by a factor creeping towards 12.26 — a number nobody can prove, with an exponent conjectured from the physics of random surfaces.

topology · Homotopy

Named alongside it

The objects these essays reach for when they reach for this one.

TriangulationCounting two waysGenerating functionBijectionBinary treesBinomial coefficientExhaustive searchGraphLattice pathsPermutationRecursionAsymptotics

All concepts