The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » Math Topics » alt.math.undergrad

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: binomial question
Replies: 18   Last Post: Feb 8, 2008 3:33 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
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
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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 k-subsets 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.

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.