How often a number can appear in Pascal's triangle

Pascal’s triangle is built by a rule so simple that its rows can be written down by anyone: start with a 1, and make each entry the sum of the two above it. Every entry counts the routes to it read the entries as counts of paths, $\binom{n}{k}$ ways of choosing $k$ things from $n$, and Pascal’s triangle, in two colours found a fractal hiding in their parities. This essay asks a question about the triangle that sounds as though it should have an easy answer and does not: how many times can the same number appear in it?

Every number $a$ bigger than one appears at least twice, because the row beginning $1, a, \ldots$ is row $a$, whose second and second-last entries are both $a$. Most numbers appear exactly that often, and only at those edges. A few turn up deeper inside as well, and in 1971 David Singmaster asked how many times a number can appear in total. He proved that the count grows at most like the logarithm of the number and conjectured that it is in fact bounded — that there is a fixed number of appearances that no number ever exceeds. Fifty years later the conjecture is open, and the largest count known for any number is eight.

Where 3003 appears eight times #

The number that appears eight times is 3003.

It is $\binom{14}{6}$ and $\binom{14}{8}$ in row 14, and $\binom{15}{5}$ and $\binom{15}{10}$ in row 15. It is also $\binom{78}{2}$ and $\binom{78}{76}$, since $78 \times 77 / 2 = 3003$, and it is $\binom{3003}{1}$ and $\binom{3003}{3002}$ at the edges of its own row. Each appearance in the left half of the triangle has a mirror image in the right half, because $\binom{n}{k} = \binom{n}{n - k}$, so the count is always even unless the number sits exactly in the middle of a row; 3003 has four appearances in the left half and four mirror images.

Eight is surprising because the rows grow so fast. Row 14’s middle entry is already 3432, and the entries in the middle of a row grow like a power of two; for a number to appear in two neighbouring rows at different places, the slow growth near one edge of row $n$ has to match the faster growth further in, and for it to appear on the second diagonal as well, as $\binom{78}{2}$, is a third coincidence on top of the second.

How fast the rows grow #

The triangle’s diagonals grow at very different speeds, and that is the whole reason repeated numbers are rare. The first diagonal is $1, 2, 3, 4, \ldots$, every whole number in turn. The second is the triangular numbers $1, 3, 6, 10, 15, \ldots$, the sums $1 + 2 + \cdots + n$, which three triangular numbers, and no fewer met as the numbers Gauss proved can build every other in threes; they grow like $n^2/2$, so about $\sqrt{2X}$ of them lie below $X$. The third diagonal is the running sums of the second, as the run that lands one place along showed every diagonal is of the one before it, and it grows like $n^3/6$; the $k$-th grows like $n^k/k!$.

The middle of a row grows fastest of all. The central entry $\binom{2m}{m}$ is about $4^m/\sqrt{\pi m}$, so by row 40 the middle entries already exceed $10^{11}$, and a number of size $X$ can appear only in rows up to about $\log_2 X$ away from the edges. Near the middle the entries of consecutive rows are spread so far apart that two of them equalling each other, or equalling something on a low diagonal, requires an arithmetic accident — and most accidents that small numbers allow are exhausted quickly.

So every appearance of a number other than at the edges is a hit by one of a few thin sequences, and a number appearing six times has been hit by two of them at once. The census below is a list of all the double hits up to $10^{12}$.

Seven numbers below a million million #

How rare such coincidences are can be settled exactly for numbers up to any bound, by listing everything. The entries $\binom{n}{1} = n$ and $\binom{n}{2} = n(n - 1)/2$ are easy to recognise: every number is the first, and a number is the second exactly when $8a + 1$ is a perfect square. Everything else — the entries $\binom{n}{k}$ with $3 \le k \le n/2$ — is a short list: up to $10^{12}$ there are only 21,909 of them, because the rows grow so quickly away from the edges. So the search lists those 21,909 entries in whole-number arithmetic, tests each value for being also on the second diagonal, and adds up the appearances.

Seven numbers come out: 120, 210, 1,540, 3,003, 7,140, 11,628 and 24,310. Six of them appear six times and 3003 appears eight. No number up to a million million appears five times, seven times, or more than eight. Every one of the six appears as the first entry of its own row, once on the second diagonal, and once deeper: 120 is $\binom{16}{2}$ and $\binom{10}{3}$, 24,310 is $\binom{221}{2}$ and $\binom{17}{8}$. Only 3003 has two appearances deeper in, in neighbouring rows, as well as one on the second diagonal. The arithmetic has to be exact for the census to mean anything. Moving along the third diagonal multiplies an entry near $10^{12}$ by a row number in the tens of thousands, and the intermediate products pass $10^{16}$, beyond the point at which ordinary floating-point numbers stop representing every integer; a test for equality done that way could report a coincidence that is not there, or miss one that is. Every entry here is computed as a whole number of whatever length it needs, so two entries are equal in the census only if they are equal.

The absence of five and seven is not an accident of the bound. An odd count needs an appearance in the exact middle of a row, a central binomial coefficient $\binom{2m}{m}$, and the central coefficients — 2, 6, 20, 70, 252, 924, and so on — would each have to coincide with another entry somewhere else. Apart from $6 = \binom{4}{2}$, which appears three times in all, no central coefficient up to $10^{12}$ appears anywhere except its own place in the middle and at the edges of its own row.

Almost every number sits only at the edges #

The reason coincidences are so rare is visible in how thinly the inner part of the triangle samples the numbers.

Up to $10^{12}$, 1,414,213 numbers lie on the second diagonal — about $\sqrt{2X}$ of them, since $\binom{n}{2}$ is about $n^2/2$ — and only 21,908 distinct numbers lie deeper, a count dominated by the third diagonal and growing roughly like the cube root of $X$. So a number up to $10^{12}$ has about one chance in seven hundred thousand of being on the second diagonal and about one in forty-five million of being deeper in. For a number to appear six times it must be in both sets at once, and if membership were independent the expected number of such numbers would be roughly the product of the two densities summed over all numbers — which grows so slowly that a handful of examples among the small numbers, and essentially none beyond, is exactly what the arithmetic predicts.

The heuristic suggests why Singmaster’s conjecture is believed: the sets of numbers on each diagonal thin out so fast that, beyond the first few, coincidences between three or more of them should simply stop happening. What it cannot do is rule out the special structure that makes a family of coincidences repeat for ever, and such a family exists.

Three times the third diagonal meets the second #

The simplest coincidence is between the second and third diagonals, the equation

$$\binom{n}{2} = \binom{m}{3}, \qquad \text{that is,} \qquad \frac{n(n - 1)}{2} = \frac{m(m - 1)(m - 2)}{6}.$$

As $m$ grows, $\binom{m}{3}$ lands between consecutive values of $\binom{n}{2}$ at offsets that look uniformly scattered, as though chosen at random, and it lands exactly on one only three times beyond the trivial $\binom{5}{3} = \binom{5}{2} = 10$: at 120, 1,540 and 7,140, all before $m = 40$. After that, nothing. That is a theorem, not just the end of the search. Clearing the fractions turns the equation into one for the integer points on a cubic curve — an elliptic curve — and a theorem of Carl Ludwig Siegel’s from 1929 says such a curve has only finitely many integer points; S. E. Avanesov found all of them for this one in 1966, and they are exactly the three in the figure.

The same is true of every pair of fixed diagonals: for fixed $k$ and $l$, the equation $\binom{n}{k} = \binom{m}{l}$ has finitely many solutions, each being a question about integer points on one particular curve. The trouble for Singmaster’s conjecture is that there are infinitely many pairs of diagonals, and finitely many solutions on each is consistent with unboundedly many in total.

Infinitely many numbers appear six times #

There is a family of solutions that runs across the diagonals rather than along a pair of them, and it was found by Douglas Lind in 1968 and again by Singmaster in 1975. Write $F_0, F_1, F_2, \ldots$ for the Fibonacci numbers $0, 1, 1, 2, 3, 5, 8, \ldots$. Then for every $i$,

$$\binom{F_{2i+2}F_{2i+3}}{F_{2i}F_{2i+3}} = \binom{F_{2i+2}F_{2i+3} - 1}{F_{2i}F_{2i+3} + 1}.$$

For $i = 1$ the identity reads $\binom{15}{5} = \binom{14}{6}$, which is 3003. For $i = 2$ it reads $\binom{104}{39} = \binom{103}{40}$, a number with 29 digits; for $i = 6$ the number has 66,416 digits, and the identity still holds exactly, as the whole-number arithmetic confirms. Each member appears at least six times: twice at the edges of its own row and twice in each of the two rows of the identity. So infinitely many numbers appear at least six times, and the six-times numbers in the census are a mixture of this family’s first member and sporadic coincidences like 120 and 24,310 that belong to no family.

Why Fibonacci numbers? Two entries $\binom{n}{k}$ and $\binom{n - 1}{k + 1}$ in adjacent rows are equal exactly when the ratio between them is one, and that ratio works out to $n(k + 1)/\big((n - k)(n - k - 1)\big)$. So the question is when $n(k + 1) = (n - k)(n - k - 1)$, a quadratic equation in two whole numbers, and its solutions are generated by a recurrence of the kind that solves Pell’s equation — which is where the Fibonacci numbers come in. One solution that makes all the others found the same structure in $x^2 - 2y^2 = 1$, every solution a power of the smallest; here the Fibonacci numbers play the part of those powers, and each member of the family is the next turn of the same crank. The family also has a shape inside the triangle. The position $k$ of each member’s appearance, as a fraction of its row $n$, is $F_{2i}/F_{2i+2}$, and those ratios of Fibonacci numbers converge to $1/\varphi^2 = 0.38196\ldots$, where $\varphi$ is the golden ratio: for the sixth member the fraction is $87{,}840/229{,}970 = 0.38196$ to five places. So the family’s coincidences march down Pascal’s triangle along a straight ray, leaning a fixed amount off the centre line, at the angle the golden ratio sets — the same ratio the rectangle that eats itself found by cutting squares off a rectangle. Nothing else in the census lines up this way; the sporadic coincidences at 120 or 24,310 sit wherever their arithmetic puts them.

3003 is the first member of this family that happens also to be a triangular number, which gives it its two extra appearances and its eight. Whether any later member is also triangular, or lies on some other diagonal, is not known; the computation here checks only that the family’s identity holds, not where else its members appear.

What has been proved #

Singmaster’s own bound of 1971 takes three lines. Suppose $a$ appears as $\binom{n}{k}$ with $k \le n/2$. Since $n \ge 2k$, the entry is at least the central entry of row $2k$, and that is at least $2^k$: so $a = \binom{n}{k} \ge \binom{2k}{k} \ge 2^k$, and $k$ is at most $\log_2 a$. And for each such $k$ there is at most one row $n$ in which $\binom{n}{k} = a$, because along a fixed diagonal the entries only increase. So the left half of the triangle contains $a$ at most once for each $k$ from 1 to $\log_2 a$, and with mirror images the total is at most about $2\log_2 a + 2$. The argument uses nothing but the growth of the diagonals, and it gives a bound that grows, though slowly. Successive improvements have lowered it: Harvey Abbott, Paul Erdős and Denis Hanson in 1974, and Daniel Kane in 2007, whose bound grows a little more slowly than $\log a$ divided by the cube of $\log \log a$. All of these bounds still grow without limit.

The most striking recent result attacks the conjecture where the triangle is widest. In 2021 Kaisa Matomäki, Maksym Radziwiłł, Xuancheng Shao, Terence Tao and Joni Teräväinen proved that, away from the entries very close to the edges of the triangle, every sufficiently large number appears at most four times — at most two pairs of mirror images in the interior. Their argument combines the size estimates that govern how fast rows grow with results about how primes divide binomial coefficients, the kind of question the carries decide the divisibility answered with Kummer’s theorem and a remainder read two digits at a time refined with Lucas’s. What remains is the region near the edges, where the second, third and other low diagonals live, and where coincidences like those in the census occur.

What the pictures cannot show #

The census is exact for every number up to $10^{12}$ and says nothing beyond it. That nothing appears more than eight times up to a million million is a fact; that nothing appears more than eight times at all is Singmaster’s conjecture in its strongest hoped-for form, and much larger searches by others, while finding no exception, prove nothing either. The near-miss figure shows offsets that look random, and its randomness is an impression rather than a theorem; Avanesov’s result, that the three hits are all there are, is the theorem, and it is not drawn.

The triangle in the first figure stops at row 16 because its middle entries are already five digits long there; 3003’s other appearances, in rows 78 and 3003, are hundreds of rows further down and cannot be drawn on the same page as the first four. Nor do the pictures show why the Fibonacci identity holds — the family figure checks six members exactly, which is evidence and not proof — or what the 2021 interior theorem says precisely, which depends on a boundary between “near the edge” and “interior” that the triangle drawn here is far too small to show.

Still open: whether there is any bound at all #

Is there a number $N$ such that no integer bigger than one appears in Pascal’s triangle more than $N$ times? Singmaster conjectured yes; the largest count known is eight, for 3003, and no number is known to appear exactly five, seven, nine or ten times. The proved bounds all grow like a logarithm divided by a slowly growing factor, the interior theorem caps the count at four away from the edges for large numbers, and the gap between them is the strip near the edges where the low diagonals meet one another.

Closing it would mean showing that coincidences between the second diagonal, the third and the others near them cannot pile up on a single number, uniformly across all the infinitely many pairs of diagonals at once. Each pair is a curve with finitely many integer points, and the Fibonacci family shows that infinitely many curves can share a common pattern of solutions. Whether that pattern can ever deliver a ninth or tenth appearance to some enormous number is the whole question, and the triangle’s own rows — easy enough to compute by hand at the top — give no hint of the answer.