## binomial

The binomial coefficient
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 *x*^{r} 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

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*, *r*_{j}>*n*_{j}.
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*)
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+*x*^{p})^{m}(1+*x*)^{n}.
Now to get a term containing *x*^{rp+s}
we need the *x*^{s} term from the second factor,
and therefore the
*x*^{rp}=(*x*^{p})^{r}
term from the first. These come with factors of
and
,
respectively, attached. And we’re done ...

... except that I promised to explain why
((1+*x*)^{p})^{m}
and
(1+*x*^{p})^{m}
are equal modulo *p*.
Clearly it’s enough if
(1+*x*)^{p}
and
1+*x*^{p}
are equal modulo *p*.
Well, when you expand out
the former, the coefficient in front of each
*x*^{r} is (by definition)
. The coefficients
of *x*^{0} and *x*^{p}
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?)