The n-Category Café

De Weger conjectured that every equation between binomial coefficients follows from the four known systematic equations and the seven coincidences I showed you:

• Benjamin M. M. de Weger, Equal binomial coefficients: some elementary considerations, Journal of Number Theory 63, no. 2 (1997), 373–386.

At that time, he and his collaborators checked there were no others involving binomial coefficients less than 10³⁰. Later they checked that there are none involving binomial coefficients less than 10⁶⁰:

• Aart Blokhuis, Andries Brouwer and Benne de Weger, Binomial collisions and near collisions.

At that time, he and his collaborators checked there were no others involving binomial coefficients less than 10³⁰. Later they checked that there are none involving binomial coefficients less than 10⁶⁰:

• Aart Blokhuis, Andries Brouwer and Benne de Weger, Binomial collisions and near collisions.

So, De Weger’s conjecture stands open. The four infinite families, by the way, are these:

$$\displaystyle{ \binom{n}{k} = \binom{n}{\,n-k\,}, \qquad 0 \le k \le n}$$

$$\displaystyle{ \binom{n}{0} = 1, \qquad n \ge 0 }$$

$$\displaystyle{ \binom{\binom{n}{k}}{1} = \binom{n}{k}, \qquad \qquad 0 \le k \le n}$$

and the only nontrivial one: the Lind–Singmaster family involving the Fibonacci numbers $F_i$ where $F_0 = 0,\ F_1 = 1$:

$$\displaystyle{ \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\,}, \qquad i = 1,2,3,\dots }$$

The first three equations in the Lind–Singmaster family are these:

$$\begin{array}{ccc} \displaystyle{ \binom{15}{5} } &= &\displaystyle{\binom{14}{6}} \\ \\ \displaystyle{\binom{104}{39} } &= &\displaystyle{\binom{103}{40}} \\ \\ \displaystyle{ \binom{714}{272} } &=& \displaystyle{\binom{713}{273}} \end{array}$$

I’ll explain the Lind–Singmaster family later. But here’s the question I’m most interested in:

Is there any good explanation for the seven binomial coefficient coincidences?

My collaborator Paul Schwahn found a beautiful explanation of the first one, namely

$$\displaystyle{ \binom{10}{3} = \binom{16}{2} }$$

His explanation uses representation theory. The Lie algebra $\mathfrak{so}(10)$ has a 10-dimensional representation, the ‘vector’ representation $V_{10}$, and also two 16-dimensional representations, the ‘left and right-handed spinor’ representations $S^\pm_{10}.$ There’s an isomorphism of representations

$$\displaystyle{\Lambda^2 S^+_{10} \cong \Lambda^3 V_{10} }$$

and similarly for $S^-_{10},$ but we might as well work with $S^+_{10}.$ Here $\Lambda^k$ means the kth exterior power. For any vector space $X$ we have

$$\displaystyle{ \dim(\Lambda^k X) = \binom{\dim X}{k} }$$

Thus, taking dimensions, the isomorphism of representations

$$\displaystyle{\Lambda^2 S^+_{10} \cong \Lambda^3 V_{10} }$$

instantly gives

$$\displaystyle{ \binom{16}{2} = \binom{10}{3} }$$

It is not super-easy to prove this isomorphism of representations, but it’s still nice to find a deeper layer of meaning underlying what might otherwise seem like a meaningless coincidence!

Can we find good explanations for the other six coincidences?

First let me explain two failed attempts using representation theory, and then three successes using combinatorics.

Representation theory

First: we can look for isomorphisms like

$$\displaystyle{\Lambda^2 S^+_{10} \cong \Lambda^3 V_{10} }$$

involving representations of $\mathfrak{so}(n)$ for larger $n.$ In fact this isomorphism is part of a pattern! The next one involves the vector and left-handed spinor representations of $\mathfrak{so}(12).$ But it’s this:

$$\displaystyle{ \Lambda^2 S^+_{12} \cong \Lambda^4 V_{12} \oplus \Lambda^0 V_{12} }$$

so it gives

$$\displaystyle{ \binom{32}{2} = \binom{12}{4} + 1 }$$

or

$$\displaystyle{ 496 = 495 + 1 }$$

So we fail to get an equation between binomial coefficients, but we’re close: we’re only off by one.

The second paper I cited, Binomial collisions and near collisions, presents a list of cases where two binomial coefficients differ by one. This is on the list. So we failed to explain an equation between binomial coefficients, but we explained a near-miss.

Here’s another failed attempt at explaining an equation between binomial coefficients. The equation

$$\displaystyle{ \binom{78}{2} = \binom{14}{6} = 3003 }$$

is fascinating to anyone who knows their exceptional Lie groups. 78 is the dimension of $\mathrm{E}_6,$ while 14 is the dimension of $\mathrm{G}_2.$ $\mathrm{G}_2$ is a subgroup of $\mathrm{E}_6$ because $\mathrm{G}_2$ is the automorphism group of the octonions and $\mathrm{E}_6$ is the isometry group of the bioctonionic plane. We’d get the above equation if the 2nd exterior power of the adjoint representation of $\mathrm{E}_6,$ upon being restricted to $\mathrm{G}_2,$ were isomorphic to the 6th exterior power of the adjoint representation of $\mathrm{G}_2.$

Amazingly, it seems these two representations of $\mathrm{G}_2$ are not isomorphic even though their dimensions are the same: both 3003.

Even more amazingly, $\mathrm{E}_6$ and $\mathrm{G}_2$ both have irreducible representations of dimension 3003, but they are not the representations I just mentioned.

I would be happy for someone to check these two claims.

Combinatorics

It turns out that the following three coincidences can all be explained by the same style of combinatorial argument:

$$\binom{21}{2} = \binom{10}{4}, \qquad \binom{153}{2} = \binom{19}{5}, \qquad \binom{78}{2} = \binom{14}{6}$$

The argument is not very elegant, but it’s moderately interesting. Mike Stay got it started by asking ChatGPT, and I finished it off.

In each case the argument has three steps. The first two steps are what combinatorialists call bijective proofs: we prove an equation between numbers by proving a natural isomorphism between structures on sets and then taking cardinalities. The third step is non-bijective because it involves taking an equation and dividing both sides by the same number. Maybe we can make it closer to bijective by using groupoid cardinality, which allows for division, but I haven’t tried that.

Step 1: pairs of edges in a complete graph

Starting from the left-hand binomial coefficient in each equation we’re trying to prove, note that the number on top is a triangular number:

$$21 = \binom{7}{2}, \qquad 153 = \binom{18}{2}, \qquad 78 = \binom{13}{2}$$

Note that $\binom{\binom{n}{2}}{2}$ counts unordered pairs of distinct edges in the complete graph on $n$ vertices. Two distinct edges either share a vertex or are disjoint, so there are two cases:

• Sharing a vertex: the pair spans 3 vertices and is determined by this 3-element set together with a choice of which vertex is shared. That gives $3\binom{n}{3}$ pairs.

• Disjoint: the pair spans 4 vertices and is determined by this 4-element set together with one of its 3 splittings into two pairs. That gives $3 \binom{n}{4}$ pairs.

By Pascal’s rule, $\binom{n}{3} + \binom{n}{4} = \binom{n+1}{4}.$ But this also has a bijective proof: add a new point to the set of $n$ vertices, and a 4-element subset of the enlarged set either contains the new point (so involves a 3-element subset of the old ones) or does not (so involves a 4-element subset of the old ones). Hence we have a bijective proof that

$$\binom{\binom{n}{2}}{2} = 3\binom{n+1}{4}$$

This holds for all $n.$ For our three cases we get bijective proofs of the following equations:

$$\binom{21}{2} = 3\binom{8}{4}, \qquad \binom{153}{2} = 3\binom{19}{4}, \qquad \binom{78}{2} = 3\binom{14}{4}.$$

It thus remains to prove

$$3\binom{8}{4} = \binom{10}{4}, \qquad 3\binom{19}{4} = \binom{19}{5}, \qquad 3\binom{14}{4} = \binom{14}{6}.$$

Step 2: a double count

Each of the above equations follows by counting a single set in two ways, and then a nonbijective step: dividing these counts by the same number.

• Showing $3\binom{8}{4} = \binom{10}{4}$. In a 10-element set, count triples $(S, x, y)$ in two different ways, where $S$ is a 4-element subset and $x, y$ are distinct points outside $S$. Choosing $S$ first we see there are $$\binom{10}{4} \cdot 6 \cdot 5 = 30\binom{10}{4}$$ triples. Choosing $x$ and $y$ first we see there are $$10 \cdot 9 \cdot \binom{8}{4} = 90\binom{8}{4}$$ triples. So, we get a bijective proof that $$90\binom{8}{4} = 30\binom{10}{4}$$ You can see what we’ll do next.

• Showing $3\binom{19}{4} = \binom{19}{5}.$ In a 19-element set, count pairs $A \subset B$ with $|A| = 4$ and $|B| = 5$. On the one hand, there are $\binom{19}{4}$ choices of $A,$ and for each there are 15 choices of $B$ since we can add an extra point in 15 ways. On the other hand, there are $\binom{19}{5}$ choices of $B,$ and for each there are 5 choices of $A$ since we can choose $A$ in $\binom{5}{4} = 5$ ways. So we get a bijective proof that $$15\binom{19}{4} = 5\binom{19}{5}$$ Again, you can see what we’ll do next!

• Showing $3\binom{14}{4} = \binom{14}{6}.$ In a 14-element set, count pairs $A \subset B$ with $|A| = 4$ and $|B| = 6$. On the one hand, there are $\binom{14}{4}$ choices of $A,$ and for each there are 45 choices of $B$ since we can add 2 other points in $\binom{10}{2} = 45$ ways. On the other hand there are $\binom{14}{6}$ choices of $B$ and for each there are 15 choices of $A$ since we can choose 4 points in $\binom{6}{4} = 15$ ways. This gives a bijective proof that $$45\binom{14}{4} = 15\binom{14}{6}$$ Again you can see what we’ll do next.

Step 3: division

Having proved

$$90\binom{8}{4} = 30\binom{10}{4}, \qquad 15\binom{19}{4} = 5\binom{19}{5}, \quad 45\binom{14}{4} = 15\binom{14}{6}$$

we can now divide by 30, 5 and 15, respectively, and get

$$3 \binom{8}{4} = \binom{10}{4} , \qquad 3 \binom{19}{4} = \binom{19}{5}, \quad 3\binom{14}{4} = \binom{14}{6}$$

as we wanted, completing our proof that

$$\binom{21}{2} = \binom{10}{4}, \qquad \binom{153}{2} = \binom{19}{5}, \qquad \binom{78}{2} = \binom{14}{6}.$$

I don’t see how to use tricks of the same general sort to explain the remaining coincidences

$$\binom{56}{2} = \binom{22}{3}, \qquad \binom{120}{2} = \binom{36}{3}, \qquad \binom{221}{2} = \binom{17}{8}.$$

The Lind–Singmaster family

Lind and Singmaster were trying to find all $n,k$ with

$$\displaystyle{ \binom{n}{k} = \binom{n-1}{k+1} }$$

I’ll rapidly sketch the key steps of their argument. Simplifying the equation above we get

$$n(k+1) = (n-k)(n-k-1)$$

or

$$n^2 - (3k+2)n + (k^2+k) = 0$$

Solve for $n$ using the quadratic formula. This formula turns out to have

$$\sqrt{5k^2 +8k+4}$$

in it. So we need $5k^2 +8k+4$ to be a perfect square!

Now we’re trying to find integer solutions of

$$5k^2+8k+4 = m^2$$

A quadratic diophantine equation! Multiply by 5 and complete the square:

$$5m^2 = (5k+4)^2 + 4$$

$y = 5k+4$ is an integer when $k$ is, so we need to find integer solutions of

$$y^2 - 5m^2 = -4$$

This is a ‘Pell equation’, and people know how to solve these. In this particular case we get all the solutions from this fact:

$$L_n^2 - 5F_n^2 = 4(-1)^n$$

where $F_n$ are the Fibonacci numbers 0, 1, 1, 2, 3, … and $L_n$ are the Lucas numbers 2, 1, 3, 4, 7, …. These are two sequences satisfying the same famous recurrence relation, just with different initial conditions.

We want $n$ odd, to get

$$L_n^2 - 5F_n^2 = -4$$

It turns out $y = L_n, m = F_n$ with $n$ odd give all solutions of the Pell equation

$$y^2 - 5m^2 = -4$$

However, remember I said $y = 5k+4$ is an integer when $k$ is. But the converse isn’t always true, and we need $k$ to be an integer! This clearly happens iff $y \equiv 4 \bmod 5.$

So we need to know when $L_n \equiv 4 \bmod 5$ Apparently this happens iff $n \equiv 3 \bmod 4.$ I won’t think about this now… but this is the last hard step.

In summary, we’ve seen

$$\displaystyle{ \binom{n}{k} = \binom{n-1}{k+1} }$$

if and only if $y = 5k+4$ is a Lucas number $L_n$ with $n \equiv 3 \bmod 4.$ We could quit here, but people like to use the identity

$$L_{4i+3} - 4 = 5F_{2i} F_{2i+3}$$

to get a formula for $k$ in terms of Fibonacci numbers. This is gilding the lily, I’d say, but it eventually leads to the formula that de Weger presents:

$$\displaystyle{ \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\,}, \qquad i = 1,2,3,\dots }$$

The takeaway message is: our problem can easily be reduced to a quadratic diophantine equation, then put in Pell form… and it’s known that the sequence of integer solutions of a Pell equation obeys a linear recurrence relation! We luck out in this case and get solutions connected to Lucas and Fibonacci numbers.

There may be a simpler argument, but this is what I’ve seen.