Matpic
mathematics, in pictures
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 7 essays across 3 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 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.

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 · 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 35 routes across a 4 by 3 grid. A grid with each cell holding the number of monotone routes reaching it. The far corner holds 35, which is the binomial coefficient of 7 choose 3.

Every entry counts the routes to it

Turn Pascal's triangle forty-five degrees and it becomes a grid of street corners, with each entry counting the ways of walking there. Identities between the entries then become statements about routes, and the statements are proved by cutting the routes in one place.

discrete · Pascals triangle A polygon of 4 points averaged down to its curve at t = 0.40. A control polygon of 4 points, the 3 rounds of weighted averaging at t = 0.40 drawn as nested polylines, the single point they end at, and the whole curve those points trace. The weights on the control points are 0.216, 0.432, 0.288, 0.064.

Averaging down the triangle

Change one word in the rule that builds Pascal's triangle — take a share of each entry above instead of adding them — and the triangle stops counting and starts averaging. The same rule then draws smooth curves from polygons and approximates every continuous function by polynomials, at a rate that no amount of smoothness can improve.

discrete · Pascals triangle What a left glove is worth as the market tips. For 20 players and L from 1 to 19: the core value of a left glove (1 below 10, any value at 10, 0 above) and the Shapley value, from 0.950 to 0.003.

One glove too many

Give some people left gloves and others right ones, and let any group sell the pairs it can make. If the two sides are equal, the core — the splits no group can beat by walking out — is every price at once. If one side has a single glove more, the core is one split: the scarce side takes the whole of every pair and the other side gets nothing, however large the market. The average over orders of arrival barely notices the difference, and the two rules disagree about almost everything a market is.

applied · The core

Named alongside it

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

BijectionCounting two waysBinomial coefficientCatalan numbersRecursionBallot problemBinary treesTriangulationAlgebraic identityApproximationBinomial distributionCancellation

All concepts