Scribble, scribble, scribble

I suppose this is what they call a blog. Except that blogs are supposed to be updated more often than this is.

Feeds: Atom 1.0 (preferred), RSS 0.91. Front page: link.

< June 2011 >
SuMoTuWeThFrSa
    1 2 3 4
5 6 7 8 91011
12131415161718
19202122232425
2627282930  
Friday 2011-06-03

binomial

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?)