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.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

14 of 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 1234123412341234123412341234123412341234123412341234123412341234all 16 trees on 4 labelled points, found by taking every set of 3 edges and keeping the ones with no cycle4 to the power 2 is 16, which is the count — and the same rule gives 1,296 on six points, which is why they are not all drawn

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

Named alongside it

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

BijectionBinary treesCayleys formulaConvexityCounting argumentEncodingGraphLabelled treeLattice pathsLeafPrufer codeRecursion

All concepts