Ladnor Geissinger
Posts:
313
From:
University of North Carolina at Chapel Hill
Registered:
12/4/04


Re: binomial question
Posted:
Feb 8, 2008 3:33 PM


The arguments so far given for why C(2^r,k) is even for all 0<k<2^r involve elementary number theory and the formula for computing binomial coefficients. I prefer whenever possible to not use the formula but instead use a combinatorial proof. It seems to me clearer and more direct and perhaps more insightful. And sometimes we see the result as a special case of a more general method.
Suppose that 0<=k<=n and we think of C(2*n,k) as counting subsets of size k of a set S of size 2*n. Let's take n different A's and n different B's for our set S. So we have S={A1,A2,...,An,B1,B2,...,Bn} and let's let T be the permutation of S which switches Ai for Bi forall i (an involution). Now each subset D of size k of the set S gets carried into another subset TD  just replace each Ai in D by Bi and each Bp in D by Ap to get TD. Of course if we apply T again to TD then we get back to D (T acts as an involution of the collection of ksubsets of S).
(1) The collection of all D for which TD /=D can be counted by pairs {D,TD} (orbits) and so the number of these is even. (2) Notice that TD =D iff (forall i, Ai is in D iff Bi is in D), and if so then k=2*r. So such a D is determined by the subset of size r consisting of the Ai that are in D. Hence the number of such D is C(n,r)=C(n,k/2).
Thus, if k is odd then C(2*n,k) is even, and if k is even then C(2*n,k) has the same parity as C(n,k/2).
You can do a similar proof of Wilson's theorem and a generalization of it by considering the set Un of invertible residues in Zn (residues modulo n), pairing each with its inverse, and noting that the product of all residues in Un is then the same as the product W of all the elements of order 2. And then W = 1 if 1 is the only residue of order 2, but W = 1 if there are residues of order 2 besides 1. Of course this also works for any finite abelian group.

