Binomial coefficient
Named by 34 essays across 11 fields — each of them below, with the objects they name alongside it.
Pascal's triangle, in two colours
Shade the odd numbers in Pascal's triangle and a fractal appears. Nothing was designed to produce it, and the same shape arrives independently from a completely different construction.
The path folded at its first touch
Counting the walks that touch a line looks like a question about a walk's whole history. Fold each one where it first touches, and it becomes a question about where walks end up — which is a binomial coefficient, and is already known.
Always one before the double
A density says what happens on average and permits long empty stretches. This says something a density cannot — that the stretch from any number to twice it contains a prime, at every scale, without exception.
A polynomial that counts
Hang a counting sequence on the powers of a variable and the two ways of combining choices — this and that, this or that — become multiplication and addition, so a recursion turns into an equation and the equation can be solved.
The widest layer and the longest chain
Order sixteen subsets by inclusion and ask for the largest collection with no two comparable. The answer is the six subsets of size two — the widest layer — and no cleverer collection beats it. Ask instead for the fewest chains covering everything, and the answer is the same number again.
The colouring nobody has ever seen
Count the monochromatic sets a random colouring is expected to contain. If the average is below one, some colouring has none — and the argument is finished, having produced nothing anyone can look at.
Everybody's share of the chains
There are twenty-four ways to build a four-element set one element at a time. Every subset lies on some of them, and no two incomparable subsets share one — so an antichain is a set of disjoint shares of a single whole.
The cube cut into chains
Write a subset as a string of brackets, match them the ordinary way, and the unmatched ones say which chain it is on. Six chains cover all sixteen subsets of a four-element set, and the bound and the example arrive together.
The largest family that always meets
Change the question from "no two comparable" to "every two share an element" and the answer changes shape. The best antichain is a whole layer; the best intersecting family is a star, and the proof is a circle.
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.
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.
The run that lands one place along
Add up a run of entries down one of Pascal's diagonals and the total is another entry of the triangle — one row further down and one place along. The same triangle holds four more sums of that kind, and each is a different question answered by the same additive rule.
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.
The carries decide the divisibility
How many times a prime divides a binomial coefficient is not a fact about the coefficient at all. It is a count of the carries that happen when two numbers are added in that prime's base, which is a question about column addition and has nothing to do with choosing anything.
A remainder read two digits at a time
Lucas' theorem reads a binomial coefficient's remainder on division by a prime off its digits one at a time. On division by the prime's square the same reading is wrong at four odd entries in ten. What replaces it still reads digits — in overlapping pairs, with the prime taken out first and a sign that the carries decide.
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.
A dimension for every rate of crowding
Spread a unit of mass over an interval by splitting it unevenly, again and again, and the result covers the whole interval while crowding almost all of its weight onto a set of smaller dimension. Every rate of crowding picks out its own set of points with its own dimension, and the whole family is read off one curve.
Every third coefficient
Add every third number in the twelfth row of Pascal's triangle and the answer is 1366 — a third of 4096, rounded up. Which way the rounding goes is decided by two arrows of length one in the complex plane, and the same average over the roots of unity counts dice totals, subsets and necklaces.
The product that deals the labels
Multiplying two counting series pairs one choice with another. When the things being counted carry labels, the labels have to be dealt out as well, and the only series that survive the extra bookkeeping are the ones divided by n factorial.
The coefficient that is a polynomial
Add a second variable to track a statistic and each coefficient stops being a number. Set the new variable to one and the old count comes back untouched; leave it in and the mean of the statistic is a derivative rather than an average.
The walk through the middle levels
On seven places, the words with three ones and the words with four number thirty-five each. Is there a closed walk through all seventy, changing one place at a time and never leaving those two levels? On five places the answer is 24 walks, on seven and nine a search finds one in moments — and whether one exists for every odd length was open for thirty years, until Torsten Mütze proved in 2016 that it always does.
A sum of two sets modulo a prime cannot be small
Add every element of one set of residues to every element of another. Over the whole numbers the sums always number at least |A| + |B| − 1. Modulo a prime the sums can wrap round and collide, and still they never number fewer — the theorem Cauchy proved in 1813 and Davenport again in 1935. Modulo 12 they can. A polynomial of low degree explains the difference in a paragraph.
Every crowd holds a bowl or a dome
Among enough points in the plane, some k of them always bend upward like a bowl or some l bend downward like a dome. The number that forces it is a binomial coefficient, it is exactly right, and it proves that every large enough crowd contains a convex polygon — with a bound nobody could lower to the true answer for eighty years.
The row that proves a prime
Fermat's little theorem can be fooled: 561 passes it for every base and is not prime. Thread necklaces with a fixed number of black beads instead of any colours at all, and the count becomes a statement about a whole row of Pascal's triangle — every middle entry of row n is a multiple of n exactly when n is prime — which no composite can fake. Written as polynomials it is (x + a)ⁿ = xⁿ + a, and cut down to size it is the first proof that primes can be recognised in polynomial time.
The room a projective space needs, read off Pascal's triangle
The projective plane cannot sit in three-dimensional space without crossing itself, and the reason can be written as arithmetic: a polynomial that records how a shape twists, which a room must cancel. For the n-dimensional projective space that polynomial is a row of Pascal's triangle read mod 2, its inverse is another row, and the inverse's last term says how many extra dimensions the room must have — exactly enough, at every power of two.
How often a number can appear in Pascal's triangle
Every number bigger than one appears in Pascal's triangle at least twice, next to the 1 at each end of its own row. A few appear more often: 120 appears six times, and 3003 eight — as C(3003, 1), C(78, 2), C(15, 5) and C(14, 6), each twice. Counting every entry up to a million million finds seven numbers that appear more than four times and none that appear five, seven or more than eight. Whether any number appears ten times, or whether there is any limit at all, is unknown.
Five pyramids for every number
Stack balls in triangular pyramids and the piles hold 1, 4, 10, 20, 35, … balls. Frederick Pollock guessed in 1850 that every whole number is a sum of at most five such piles. Seventeen needs five — 10 + 4 + 1 + 1 + 1 — and so do 240 other numbers, the largest 343,867; past that, every number up to ten million needs four or fewer. Eight is proved to be enough. Five is not, and the reason is the same one that makes the three-dimensional cousins of the classical theorems hard.
The sum after Leibniz's, made geometric
Leibniz's series adds the reciprocals of the odd numbers with alternating signs and gives π/4. Square the odd numbers and the same pattern gives Catalan's constant, 0.915965…, about which almost nothing is known — not even whether it is a fraction. A formula of Ramanujan's turns its slow series into one whose terms shrink by a factor of four, which makes a thousand decimals cheap, and the decimals and continued fraction then say exactly how much digits can settle and where they stop.
Running a computation backwards with little memory
The reverse sweep that gives a whole gradient for the price of a few evaluations needs the computation's intermediate states in reverse order, and storing them all can cost more memory than the machine has. Keep only a few and recompute the rest, and the cheapest schedule has an exact answer found by Andreas Griewank in 1992: with c stored states and no step run more than r times, the longest chain that can be reversed is the binomial coefficient C(c + r, c). Pascal's triangle is the table of what memory buys.
The matches left in the other pocket
A smoker keeps a box of fifty matches in each pocket and picks a pocket at random. When one box is found empty, the other holds about seven, and none and one are exactly equally likely. Favour one pocket by a tenth and the answer is sixteen; give each box five thousand matches and a fair choice leaves seventy-nine while a bias of one in a hundred leaves nearly two hundred — because a fair remainder grows like a square root and any bias makes it grow in proportion, with the change-over at a bias of one over the square root of the box.
A vote worth a square root
Give each country in a council votes in proportion to its people, and a citizen of the largest has about fifteen times the say of a citizen of the smallest. Give each country one vote and the same ratio runs the other way. Lionel Penrose saw in 1946 that the fair weight is the square root of the population, because one voter's chance of deciding an election falls as one over the square root of the crowd. Computed for twenty-seven states, the best quota is 61.5%, and it holds the ratio to 1.006.
Multiply until every sign is positive
A form with a negative coefficient can still be positive wherever its variables are, and proving it usually takes an argument. Pólya found a certificate that needs none: multiply by a power of x + y and wait until every coefficient is positive. The power needed is finite exactly when the form never touches zero, and it grows like the reciprocal of how close it comes.
Venn diagrams that turn into themselves
A Venn diagram shows every combination of in and out exactly once. Ask for one that looks the same after a turn of 1/n, each curve rotating onto the next, and a counting argument forbids it unless n is prime. Five congruent ellipses manage it, certified by Euler's formula; four rotated copies cannot, and it took until 2004 to show that every prime can.
Numbers whose subset sums all differ
The powers of two 1, 2, 4, …, 64 have 128 subset sums and no two are equal. So do 20, 31, 37, 40, 42, 43 and 44, whose largest member is smaller, and an exhaustive search shows no seven numbers do it with less. A pigeonhole on the sums says the largest member must grow like 2ⁿ/n; a variance argument improves that to 2ⁿ/√n; the best known sets sit near 0.22 × 2ⁿ. Whether the truth is a constant times 2ⁿ is Erdős's five-hundred-dollar question, and the pigeonhole cannot reach it.
Named alongside it
The objects these essays reach for when they reach for this one.
Counting two waysBijectionConvolutionCounting argumentExhaustive searchGenerating functionPrimesRecursionCatalan numbersLucas' theoremModular arithmeticPolynomial