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 $\nCr{12}{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 $\floor{\frac{n}{2}} + \floor{\frac{n}{4}} + \floor{\frac{n}{8}} + \dots$.

The same argument work for any prime: the power of prime $p$ in the prime factorisation of $n!$ is $\floor{\frac{n}{p}} + \floor{\frac{n}{p^2}} + \floor{\frac{n}{p^3}} + \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 = \floor{\frac{n}{p}} + \floor{\frac{n}{p^2}} + \floor{\frac{n}{p^3}} + \dots$
  • ${r!}_p = \floor{\frac{r}{p}} + \floor{\frac{r}{p^2}} + \floor{\frac{r}{p^3}} + \dots$
  • ${(n-r)!}_p = \floor{\frac{n-r}{p}} + \floor{\frac{n-r}{p^2}} + \floor{\frac{n-r}{p^3}} + \dots$

“All” we need to do now is show that ${r!}_p + {(n-r)!}_p < {n!}_p$. ((I was going to put an exclamation there, but risked an accidental factorial. We have enough deliberate ones of those, thankyouverymuch.))

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

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

Then $a+b = (A+B)x + a’ + b’$, and $\floor{\frac{a+b}{x}} \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)