Comments on "binomial"

[Hide] original entry

The binomial coefficient \[\tbinom{n}{r}\] 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 \[\tbinom{n}{r}\] 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}.\]

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}\] 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}\] and \[\tbinom{m}{r}\], 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}\]. 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 \[\tbinom{p}{r}\]: 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?)

(There are no comments on this entry yet.)

Post a comment:

Name:(will be shown with comment)
Email:(will be kept private)
Web page:(optional; will be linked from your name)
Secret word:(the secret word is two plus two)

You may use Markdown to format your comment, or just include HTML tags. All comments are moderated, so don't waste your time trying to abuse this.