Generator

Every triangulation of a 6-gon

A generator in the discrete library, called 36 times across 8 essays. Below: what it draws at its defaults 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.

At its defaults

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.

`show: "reflect"`

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.

`show: "paths"`

All 20 paths, sorted into two kinds. Every monotone lattice path across a 3 by 3 grid, drawn in a grid of small panels. 5 of them never go below the diagonal and are drawn heavily; the rest are faint.

`show: "catalan"`

The Catalan numbers. C(0) to C(8), each computed twice — by the convolution that defines them and by the closed form — and required to agree.

`show: "dyck"`

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.

`show: "chords"`

The 14 non-crossing pairings. Every way of pairing 8 points on a circle with non-crossing chords, drawn as 14 small diagrams. The count is the same Catalan number that counts the triangulations of a polygon.

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
Euler's relation holds on the solid these faces make ×1
every diagram pairs off all the points ×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
no two chords cross ×1
no two chords of the triangulation cross ×1
one flip at a time reaches every triangulation ×1
so the good ones are the difference of two binomial coefficients ×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 number of small triangles carrying all three colours is odd ×1
the reflection is one-to-one on the bad paths ×1
the second corner the second ×1
the successive ratio climbs at every step ×1
the triangle is cut into a grid of side between 3 and 12 ×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

Where it is called

Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.

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

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

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