Matpic
mathematics, in pictures
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 10 essays across 2 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

Named alongside it

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

BijectionBinomial coefficientCounting two waysGenerating functionLattice pathsPermutationRecursionTriangulationBinary treesConvolutionEuler characteristicGenus

All concepts