Ask Uncle Colin: Why is nCr always an integer?

Dear Uncle Colin,

How do we know the binomial coefficients are always integer? I know we can do it by a counting of sets argument, but is there an arithmetic way?

Bloomin’ Isaac Newton Obviously Made It All Labyrinthine

Hi, BINOMIAL, and thanks for your message!

To restate the question: if you have something like ${}^{12}{C}_4=\frac{12!}{(4!)(8!)}$, it’s not immediately clear that it’s an integer. I’m going to work with the specific example first and then generalise.

I think it’s simplest to divide out the $8!$ to get $\frac{12\times 11\times 10\times 9}{4\times 3\times 2\times 1}$. How do we know the top has enough factors to cancel with everything on the bottom?

Well, we have four consecutive numbers. One of them must be a multiple of 4, and another a multiple of 2; at least one is a multiple of 3, and they’re all multiples of 1 - so it works just fine.

An alternative approach is to consider the prime factors of $12!$, $8!$ and $4!$.

What’s the power of 2 in the prime factorisation of $12!$? It gets a contribution from 12 ($2^2$), from 10 ($2^1$), from 8 ($2^3$), 6 ($2^1$), 4 ($2^2$) and 2 ($2^1$), for a total of $2^{10}$. There’s a pattern there, although it’s not necessarily easy to spot: you get a 2 for every multiple of 2 up to and including 12, another for every multiple of 4, and another for every multiple of 8.

That is, the power of 2 in the prime factorisation of $n!$ is $\lfloor \frac{n}{2}\rfloor +\lfloor \frac{n}{4}\rfloor +\lfloor \frac{n}{8}\rfloor +\dots$.

The same argument work for any prime: the power of prime $p$ in the prime factorisation of $n!$ is $\lfloor \frac{n}{p}\rfloor +\lfloor \frac{n}{p^2}\rfloor +\lfloor \frac{n}{p^3}\rfloor +\dots$.

So where does that leave us? We’re interested in three different factorials, $n!$, $r!$ and $(n-r)!$.

Let’s call $N_p$ the power of prime $p$ in the prime factorisation of $N$, so that:

• ${n!}_p=\lfloor \frac{n}{p}\rfloor +\lfloor \frac{n}{p^2}\rfloor +\lfloor \frac{n}{p^3}\rfloor +\dots$
• ${r!}_p=\lfloor \frac{r}{p}\rfloor +\lfloor \frac{r}{p^2}\rfloor +\lfloor \frac{r}{p^3}\rfloor +\dots$
• ${(n-r)!}_p=\lfloor \frac{n-r}{p}\rfloor +\lfloor \frac{n-r}{p^2}\rfloor +\lfloor \frac{n-r}{p^3}\rfloor +\dots$

“All” we need to do now is show that ${r!}_p+{(n-r)!}_p<{n!}_p$. ¹

And that boils down to, is $\lfloor \frac{a+b}{x}\rfloor$ at least as big as $\lfloor \frac{a}{x}\rfloor +\lfloor \frac{b}{x}\rfloor$ for all integers $a$, $b$ and $x$?

The answer is yes. Let $a=Ax+a^{\prime }$ with $0\le a^{\prime }<x$, and $b=Bx+b^{\prime }$ with $0\le b^{\prime }<x$, so that $\lfloor \frac{a}{x}\rfloor =A$ and $\lfloor \frac{b}{x}\rfloor =B$.

Then $a+b=(A+B)x+a^{\prime }+b^{\prime }$, and $\lfloor \frac{a+b}{x}\rfloor \ge A+B$.

This implies that each prime number appears at least as often in the prime factorisation of $n!$ as it does in the product $r!(n-r)!$ – so $\frac{n!}{r!(n-r)!}$ is an integer.

Phew. Hope that helps!

- Uncle Colin

* Thanks to Andrew Buhr for alerting me to a LaTeX error (fixed 2022-10-09 and again 2022-10-10)

Footnotes:

1. I was going to put an exclamation there, but risked an accidental factorial. We have enough deliberate ones of those, thankyouverymuch.