Concept

Binary trees

Trees in which every node has a left child and a right child, either of which may be absent. They are counted by the Catalan numbers, and the count is where several apparently unrelated families of objects turn out to be the same family.

Named by 2 essays across one field — 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

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

Named alongside it

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

Bijection Catalan numbers Lattice paths Recursion Triangulation Convexity Counting-two ways Non crossing partition

All concepts