Catalan numbers
Named by 17 essays across 5 fields — each of them below, with the objects they name alongside it.
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.
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.
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.
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, 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 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 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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
TriangulationCounting two waysGenerating functionBijectionBinary treesBinomial coefficientExhaustive searchGraphLattice pathsPermutationRecursionAsymptotics