binomial
The binomial coefficient
![\[\tbinom{n}{r}\]](/g/tex-images/be901d7e0657346931ab67fd47d7814b.png){kind=small}
is the number of ways, if you have n things,
of choosing r of them; equivalently, the number
of n-digit strings, all digits 0 or 1, with
r 1s and the rest 0s; equivalently, the
coefficient of xr when you
expand out (1+x)n.
There’s a nice (and well known) theorem that says: this is odd precisely when subtracting r from n in binary requires no borrowing. (So, e.g., if n is a power of 2, then this happens only when r=0 or r=n.) There’s a very pretty generalization of this which isn’t so well known. (So far as I can remember, I found it myself, but others got there long before me.) Here it is:
Theorem: Suppose you are interested in
modulo p, a prime number. (That is, you don’t care
if your answer is wrong by a multiple of p.) Then
you can compute it as follows. Write down n and r
in base p. If r’s base-p representation
is shorter than n’s, pad it on the left with zeros
to make it the same length. Then
![\[\binom{n}{r}=\binom{n_k}{r_k}\binom{n_{k-1}}{r_{k-1}}\cdots\binom{n_0}{r_0} \pmod{p}.\]](/g/tex-images/345844d0dfd830d5df023fa9f4a17b67.png){kind=small}
In other words: compute one binomial coefficient for each corresponding pair of digits, and multiply them all together.
You’ll get 0 – i.e., a multiple of p – if and only if one of the factors is a multiple of p, which (it turns out to be easy to prove) happens if and only if for some j, rj>nj. In the case p=2 this (it turns out to be easy to prove) is the same as the condition I mentioned earlier about subtracting r from n.
Proof:
it’s enough to show that (mod p)
![\[\tbinom{mp+n}{rp+s}=\tbinom{m}{r}\tbinom{n}{s}\]](/g/tex-images/5f4d98b2c85b2275097a44322d288cf6.png){kind=small}
since that lets us split off the last base-p digit,
and we can then repeat until we’ve done all the digits.
So, consider
(1+x)mp+n.
This equals
((1+x)p)m(1+x)n.
and modulo p this equals (for reasons I’ll explain
in a moment)
(1+xp)m(1+x)n.
Now to get a term containing xrp+s
we need the xs term from the second factor,
and therefore the
xrp=(xp)r
term from the first. These come with factors of
![\[\tbinom{n}{s}\]](/g/tex-images/dc660a5a7d9498be38a6875781753faa.png){kind=small}
and
![\[\tbinom{m}{r}\]](/g/tex-images/67ad8974e3498a07baa6229d8ee4c2b1.png){kind=small}
,
respectively, attached. And we’re done ...
... except that I promised to explain why
((1+x)p)m
and
(1+xp)m
are equal modulo p.
Clearly it’s enough if
(1+x)p
and
1+xp
are equal modulo p.
Well, when you expand out
the former, the coefficient in front of each
xr is (by definition)
![\[\tbinom{p}{r}\]](/g/tex-images/c9e498087137e25e5f8b8a1517aed140.png){kind=small}
. The coefficients
of x0 and xp
are both 1, obviously. What about the others? We need
to prove that they’re all multiples of p.
Well, remember another definition of
: the number of
p-bit strings of 0s and 1s containing r 1s.
If 0<r<p then a “rotation”
of such a string (e.g., 01100 gives 00110, 00011, 10001, 11000)
still contains exactly r 1s,
and all the p different rotations are different
(why?). Hence the number of such strings is a multiple
of p, as I claimed.
(You can also prove the theorem more “directly” via a combinatorial argument involving counting the ways of selecting rp+s things from mp+n, and actually that’s how I first proved it. It’s also the proof sketched on the theorem’s Wikipedia page. Maybe there’s an even simpler proof?)