Results 1 to 11 of 11

Math Help - Combinatorial proof for an identity

  1. #1
    Member
    Joined
    May 2008
    Posts
    87

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    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.
    Last edited by awkward; April 19th 2011 at 05:30 PM. Reason: typo
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2008
    Posts
    87
    Quote Originally Posted by awkward View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2008
    Posts
    87
    Quote Originally Posted by awkward View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1615
    Awards
    1
    Quote Originally Posted by awkward View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    May 2008
    Posts
    87
    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?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    May 2008
    Posts
    87
    Quote Originally Posted by awkward View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by posix_memalign View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove the identity using a combinatorial proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 25th 2011, 06:51 PM
  2. Combinatorial proof of derangement identity
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: July 29th 2010, 02:40 PM
  3. combinatorial identity problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 23rd 2010, 10:46 PM
  4. interesting combinatorial identity proof
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: November 29th 2009, 04:34 PM
  5. Combinatorial proof of a binomial identity
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 12th 2008, 02:42 PM

Search Tags


/mathhelpforum @mathhelpforum