Associated Topics || Dr. Math Home || Search Dr. Math

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.
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search