Combinatorial ProofDate: 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. |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/