Concept

Lattice paths

Paths on a grid built from steps in a fixed set, usually one to the right or one upward. Counting them is a matter of choosing which steps go which way, so their numbers are binomial coefficients, and families of them that never touch are counted by a determinant.

Named by 2 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

A determinant counting the 16 spanning trees. A small graph, the minor of its Laplacian, and every one of its spanning trees drawn as thumbnails.

A determinant that counts trees

Write down a graph's Laplacian, strike out one row and its column, take the determinant. The answer is the number of spanning trees — and the minus signs in the determinant are what cancel every subset of edges that is not one.

algebra · determinant

Named alongside it

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

Bijection Binary trees Cancellation Catalan numbers Convexity Counting argument Counting two ways Determinant Graph Involution Matrix Recursion

All concepts