Thread: Combinatorial proof for an identity

How can I give a combinatorial proof for the identity C(n, r)C(r, k) = C(n, k)C(n - k, r - k)?

I have tried as follows:

Let S be a set with n elements, we want to choose a subset sub_1 of k elements and another disjoint subset of r - k elements, sub_2.

For the RHS we first choose sub_1 with C(n, k) and then sub_2 with C(n - k, r - k).
For the LHS we first choose sub_2 with C(n, r) and then sub_1 with C(r, k).

Is this correct at all? What am I doing wrong? It is really trivial to see algebraic but I find the combinatorial proofs hard.

Hi Posix,

I don't follow your computation of the LHS. It seems to me that you can choose sub_2 in C(n, r-k) ways, and then you can choose sub_1 in C(n-r+l, k) ways. This gives
C(n, k) C(n-k, r-k) = C(n, r-k) C(n-r+k, k),
which is true, but it's not what you set out to prove.

Originally Posted by awkward

Hi Posix,

I don't follow your computation of the LHS. It seems to me that you can choose sub_2 in C(n, r-k) ways, and then you can choose sub_1 in C(n-r+l, k) ways. This gives
C(n, k) C(n-k, r-k) = C(n, r-k) C(n-r+k, k),
which is true, but it's not what you set out to prove.

So my problem is that I don't show that the LHS counts what I set out to prove.
But is that a problem with my initial assumption about what is being counted, or is that a problem in that I simply show what the LHS counts in the wrong way?

As you don't mention anything wrong with the way I count the RHS nor the initial assumption about what is being counted I believe that I don't show how the LHS counts what it actually does count. I'm having trouble to see this though.

I don't see anything wrong with your counting of the RHS, but it may be that it's hard to show the LHS follows from the collections you are counting.

You might consider another collection of subsets-- something like A contained in B contained in C, where C consists of n elements.

Originally Posted by awkward

I don't see anything wrong with your counting of the RHS, but it may be that it's hard to show the LHS follows from the collections you are counting.

You might consider another collection of subsets-- something like A contained in B contained in C, where C consists of n elements.

I'm completely stuck on this one, as far as I see it the RHS counts the number of ways to choose a subset k elements from n elements in total, and then it chooses another subset of r - k elements out of the remaining n - k elements.

For the LHS I obviously want to show that it does the same, but I can't. When it is so trivial that they are algebraically equal, shouldn't this also be at least somewhat trivial?

The LHS has n elements in total, it counts the number of ways to first choose r elements out of the n total. Then it proceeds to choose k elements out of the r elements.

Am I allowed to rewrite the equation algebraically in a combinatorial proof? Or does that make the proof a hybrid between combinatorial and algebraic? Is there some technique as part of combinatorial proofs that I should be aware of? What do I need to do to be able to solve this problem?

I am not expert on combinatorial proofs, but I don't think you can do much in the way of algebraic rearrangement and still be considered "combinatorial".

Suppose you have sets A, B, C, with A contained in B contained in C. If C has n elements, in how many ways can you choose B and C so that B has r elements and C has k elements?

Originally Posted by awkward

I am not expert on combinatorial proofs

It is worth noting that often a so-called combinational proof is transparent only to the author of the question. Therefore, I am not sure what it means to be an expert in these proofs. That said, it seems to me that quite often such proofs can illuminate particular applications of these identities.

I'm sorry if it is obvious, but what should I do to make the LHS be counted correctly in the context that it should be equal to the RHS?

OK, I clearly am not very good at leading people into discovering this stuff on their own. (Sigh.) So--

Consider set A contained in B contained in C. C has n elements, B has r, C has k. We can pick B in C(n,r) ways, then we can pick A in C(r,k) ways.

But if we start by picking A first, this can be done in C(n,k) ways. Then we can pick the remaining elements of B in C(n-k, r-k) ways.

Originally Posted by awkward

OK, I clearly am not very good at leading people into discovering this stuff on their own. (Sigh.) So--

Consider set A contained in B contained in C. C has n elements, B has r, C has k. We can pick B in C(n,r) ways, then we can pick A in C(r,k) ways.

But if we start by picking A first, this can be done in C(n,k) ways. Then we can pick the remaining elements of B in C(n-k, r-k) ways.

Thank you for your patience.

I have written three somewhat different combinatorial proofs just for myself for this particular problem now, all I believe are faulty. One is actually quite similar to what you just wrote except that I didn't define that there is a set A contained in B, contained in C first.

I thought this was wrong as well as I don't really show how the remaining elements must equal C(n - k, r - k). I know that the remaining elements should equal this, but how does the combinatorial proof demonstrate this fact except to merely state that it is so? Is it trivial/obvious that the remaining elements should equal this? To me this is the very essence of the problem and I could never show this to myself without some further elaboration.

Originally Posted by posix_memalign

Thank you for your patience.

I have written three somewhat different combinatorial proofs just for myself for this particular problem now, all I believe are faulty. One is actually quite similar to what you just wrote except that I didn't define that there is a set A contained in B, contained in C first.

I thought this was wrong as well as I don't really show how the remaining elements must equal C(n - k, r - k). I know that the remaining elements should equal this, but how does the combinatorial proof demonstrate this fact except to merely state that it is so? Is it trivial/obvious that the remaining elements should equal this? To me this is the very essence of the problem and I could never show this to myself without some further elaboration.

I take it you are OK with the C(n,k) ways to select A.

Given A, we want to select the members of B, keeping in mind that A is a subset of B; in other words, we must expand A to B. Since B has r members, we must add r-k elements. Since we have already chosen k elements of C, there are n-k elements to choose from. So the selection can be made in C(n-k, r-k) ways.