Combinatorial Proof

Date: 7/16/96 at 20:49:34
From: Scott Turner
Subject: Combinatorial Proofs

I'm trying to do a combinatorial proof on C(n,r)C(r,k) = 
C(n,k)C(n-k,r-k) where k <= r <= n. I have the hint "think of choosing 
a subset of k elements and another, disjoint, subset with r-k 
elements."

Unfortunately, I can't really find a "formula" for this type of proof 
so other than the hint I'm not sure where to go with it.  My book just 
has one example and it is for Pascal's identity.

Can you maybe give me a better hint?

Thanks.
ST

Date: 7/17/96 at 8:8:22
From: Doctor Anthony
Subject: Re: Combinatorial Proofs

This can be proved very quickly if you use the formula for nCr.

nCr = n!/(r!.(n-r)!)    Apply this to equation you quote.

nCr*rCk = nCk*(n-k)C(r-k)

   n!          r!         n!       (n-k)!
-------- * --------  = -------- * ---------  
r!(n-r)!   k!(r-k)!    k!(n-k)!   (r-k)!(n-r)!


If you cancel r! on top and bottom lines of the left hand side, and 
(n-k)! on top and bottom lines of the right hand side then each side 
reduces to

     n!
------------       and so the two expressions are equal.
(n-r)!k!(r-k)!


-Doctor Anthony,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 7/17/96 at 10:38:5
From: Scott Turner
Subject: Re: Combinatorial Proofs

I understand what you wrote, but that isn't a "combinatorial proof", 
is it?  Isn't it just a proof based on the def of nCr?

Thanks.
ST

Date: 7/17/96 at 19:54:53
From: Doctor Sydney
Subject: Re: Combinatorial Proofs

Dear Scott,

I'm glad you wrote back.  Dr. Anthony gave a nice algebraic proof of 
the equality, but you are right that it wasn't a combinatorial proof.  
Combinatorial proofs rely on counting arguments, not algebraic 
manipulation.   So, let's see if we can work out a combinatorial proof 
to this problem.  

When I am working on combinatorial proofs, I find it easier to have 
just one thing on one of the sides of the equation, because that way 
it is easier to put into words what a given quantity represents.  
Thus, rather then trying to prove the equation in the form it is 
above, I would rewrite the equation as follows:  

Prove that :     C(n,k) = C(n,r)C(r,k)/C(n-k,r-k)

That way, I can clearly understand what at least one of the sides of 
the equation is trying to represent.  Here, in this case, I know that 
the left hand side of the equation represents the number of ways to 
choose k objects from n objects.  Then, the only thing left to do is 
show that the right hand side of the equation also represents the 
number of ways to choose k objects from n objects.  

So, let us attempt to do just that.  First, let's think about what the 
numerator represents.  C(n,r) is the number of ways to pick up r 
objects from a set of n objects, and C(r,k) is the number of ways to 
pick up k objects from a set of r objects.  So, what would multiplying 
these values together represent?  It would be the number of ways of 
choosing k objects from n objects in the following manner:  We first 
choose a set of r objects from the set of k objects, and then from 
those r objects, we choose a set of k objects.  So, basically, it is 
the number of ways to choose k objects from n objects, except that it 
overcounts.  It is hard to put into words -- this is something you 
kind of have to think through on your own.  

To finish up the proof, we must figure out how to account for this 
"overcounting."  Okay, so to be honest, if we believe that the 
equation is true, we only have to explain why dividing by C(n-k,r-k) 
takes care of the overcounting.  

But let us try to figure out by how much we overcounted when we did 
the C(n,r)C(r,k) counting thing.  In other words, given a set of k 
items, how many times did we count it?  Well, every time that set of k 
items was in the set of r that we chose in the first step, we counted 
it, right?  So how many times is a given set of k items in a set of r 
items?  

Let's figure this out.  We have n items total, and we want to know how 
many sets of r items contain a given set of k items.  Well, if we have 
a set of r items containing our given set of k items, then we know for 
sure that those k items are in the set of r items  (duh!).  So, how 
many choices do we have for the other r-k items?  Well, we can choose 
the other r-k items from the remaining n-k items (remember that we've 
already designated k items to belong to our set), so we have 
C(n-k,r-k) ways to do this.  Thus, each set of k items belongs to 
C(n-k,r-k) sets of r items, and thus each set of k items was counted 
C(n-k,r-k) times.  

From here on out, I'm sure you can fill in the details for the proof.  
I hope that helps and makes sense.  If this way doesn't make sense, 
you can try to approach it by proving the equation as it is written 
and translating each side into understandable language and showing 
that they are equal.  Or, instead of solving for C(n,k) as I did, you 
can solve for one of the other things, like C(n-k,r-k).  Then, you 
would want to follow the same general procedure -- translate one side 
into something that makes sense, and then show the other side is 
equivalent.  Essentially, combinatorial proofs boil down to providing 
two different ways to count something. They are nice, because they are 
fairly flexible -- you can go about them in several different ways.    

Good luck and feel free to write back if you have any more questions.

-Doctor Sydney,  The Math Forum
 Check out our web site!

Date: 03/06/2001 at 12:31:37
From: Rob Pratt
Subject: Combinatorial Proof (7/96)

On 7/16/96, Scott Turner asked for a combinatorial proof of

C(n,r)C(r,k) = C(n,k)C(n-k,r-k).

The identity becomes clear when one thinks of committees and 
subcommittees. Both sides count the number of ways to select, from 
among n people, a committee of r containing a subcommittee of k.

For the left-hand side, we first select the r committee members and 
then select the k subcommittee members from among these r.

For the right-hand side, we first select the k subcommittee members 
and then select the remaining r-k committee members from among the 
remaining n-k people.