Generator

Every triangulation of a 6-gon

A generator in the discrete library, called 48 times across 10 essays. Below: what it draws with nothing chosen and at each mode an essay asks for, what it checks while drawing, and everywhere it is used.

triangulation is one function. Everything below came out of it during this build, at parameters taken from the essays rather than invented for this page — so a figure here is the same figure a reader meets in an essay, and if the generator changes, this page changes with it.

With nothing chosen

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.

A bad path, and the path it reflects to

All 20 paths, sorted into two kinds

The Catalan numbers

Seven flips between the octagon's farthest triangulations

The diameter reaches 2m − 10 at thirteen

What it checks while it draws

Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.

and it agrees with the closed form at n = 0 ×13
the coefficient of x^1 is the convolution the equation demands ×12
C(0) two ways ×9
a 6-gon has C(4) triangulations ×4
every triangulation has 3 flips available ×3
the paths that stay above number the 5-th Catalan number ×3
the non-crossing pairings of 8 points number C(4) ×2
a hexagon has fourteen triangulations ×1
a polygon to be cut into triangles has between 3 and 10 sides ×1
a triangle that is not rainbow has exactly one other door ×1
a triangulation of the polygon has three fewer chords than the polygon has sides ×1
and every path is one or the other ×1
and one step below it ×1
and six are pentagons ×1
and so is the number of doors along the bottom edge ×1
and stays under four ×1
and the edge count is the handshake count ×1
and the one drawn ends in a triangle carrying all three colours ×1
and the scaled sequence climbs towards one from below ×1
and the third the third ×1
and twenty-one flips between them ×1
at least one corridor from the bottom edge ends in a rainbow triangle ×1
by the largest term drawn the scaled value is as close to one as Stirling predicts ×1
each cut uses n−3 diagonals ×1
each diameter matches the published value ×1
Euler's relation holds on the solid these faces make ×1
every diagram pairs off all the points ×1
every length in between occurs ×1
every pairing is drawn, so the point count is small ×1
every path is drawn, so the grid is small ×1
every reflected path ends one step right of the corner ×1
every triangulation of a hexagon has three flips ×1
every vertex carries a colour its position allows ×1
for every triangulation of the decagon, the distance to the fan at vertex 0 is m − 3 minus its diagonals at vertex 0 ×1
four nodes give fourteen binary trees ×1
no two chords cross ×1
no two chords of the triangulation cross ×1
no two triangulations are more than 2m − 6 flips apart ×1
one flip at a time reaches every triangulation ×1
rotating towards the right reaches exactly the trees whose vectors are componentwise larger ×1
so the good ones are the difference of two binomial coefficients ×1
successive interval counts grow by a factor approaching 256/27 ×1
the 13-gon's diameter is 2m − 10 = 16 ×1
the bad paths number the paths to the shifted corner ×1
the first corner takes the first colour ×1
the flip graph is drawn for a polygon of 4 to 6 sides ×1
the good paths number the Catalan number ×1
the grid is between 3 and 8 on a side ×1
the grid the triangle is cut into has side between 3 and 12 ×1
the hexagon's flip graph has 21 edges, each one covering relation ×1
the lattice has 68 intervals ×1
the longest has n(n − 1)/2 steps ×1
the number of comparable pairs is 2(4n + 1)!/((n + 1)!(3n + 2)!) ×1
the number of small triangles carrying all three colours is odd ×1
the octagon's flip graph has diameter seven ×1
the path found has exactly that many flips ×1
the place-by-place maximum is not always a tree's list ×1
the place-by-place minimum of any two trees' lists is again a tree's list ×1
the reflection is one-to-one on the bad paths ×1
the second corner the second ×1
the shortest maximal chain has n − 1 steps ×1
the successive ratio climbs at every step ×1
the triangle is cut into a grid of side between 3 and 12 ×1
the triangulations number the Catalan number ×1
the view is one the family draws ×1
the walk never enters the same triangle twice ×1
the word is a balanced one that never goes negative ×1
the words of this length number the Catalan number ×1
three of the faces are squares ×1
two random triangulations are typically more than half the diameter apart, and well short of it ×1
two triangulations at the greatest distance share no diagonal ×1
whenever two triangulations share a diagonal, their distance is the sum of the distances on its two sides ×1

Where it is called

Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.

Discrete

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

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

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

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

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

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

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

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

Three colours force a triangle

Cut a triangle into small ones and colour the corners under one restriction. However the cutting and the colouring are done, some small triangle ends up with all three colours — and the number of them is always odd.

Topology

Two trees, and every edge in exactly one of them

Euler's formula is usually proved by deleting things until nothing is left. There is a better argument that deletes nothing — a tree through the corners and a tree through the faces, which between them use every edge once and can therefore be counted.

The whole library · What the figures prove