Results 1 to 5 of 5

Math Help - Combinatorial proof

  1. #1
    Member
    Joined
    May 2008
    Posts
    87

    Combinatorial proof

    I'm having trouble trying to prove the identity "C(n, m) * C(m, k) = C(n, k) * C(n-k, m-k)" (for 0 <= k <= m <= n where n, m and k are natural numbers), using a combinatorial proof, could someone assist?


    Thanks in advance! :-)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by posix_memalign View Post
    I'm having trouble trying to prove the identity "C(n, m) * C(m, k) = C(n, k) * C(n-k, m-k)" (for 0 <= k <= m <= n where n, m and k are natural numbers), using a combinatorial proof, could someone assist?


    Thanks in advance! :-)
    L.H.S. = \frac{n!}{m! (n - m)!} \frac{m!}{k! (m - k)!} = \frac{n!}{(n-m)! (m-k)! k!}.

    R.H.S. = \frac{n!}{k! (n - k)!} \frac{(n-k)!}{(m - k)! (n-m)!} = \frac{n!}{(m-k)! (n-m)!k!}.

    What do you notice?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2008
    Posts
    87
    Quote Originally Posted by mr fantastic View Post
    L.H.S. = \frac{n!}{m! (n - m)!} \frac{m!}{k! (m - k)!} = \frac{n!}{(n-m)! (m-k)! k!}.

    R.H.S. = \frac{n!}{k! (n - k)!} \frac{(n-k)!}{(m - k)! (n-m)!} = \frac{n!}{(m-k)! (n-m)!k!}.

    What do you notice?
    I notice that they are similar of course :-)
    But I don't know quite how to formulate it in words; does the example for double counting at Combinatorial proof - Wikipedia, the free encyclopedia use the same logic that should be applied here?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by posix_memalign View Post
    I notice that they are similar of course :-)
    But I don't know quite how to formulate it in words; does the example for double counting at Combinatorial proof - Wikipedia, the free encyclopedia use the same logic that should be applied here?
    There are many techniques that can be applied. If all you want to do is prove that the statement is true, what I've done in this instance is probably the simplest approach.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by posix_memalign View Post
    I'm having trouble trying to prove the identity "C(n, m) * C(m, k) = C(n, k) * C(n-k, m-k)" (for 0 <= k <= m <= n where n, m and k are natural numbers), using a combinatorial proof, could someone assist?

    Thanks in advance! :-)
    Lets say, there are three boxes N,M and K. N has 'n' distinct balls, M needs 'm' balls from N and finally K needs 'k' balls from M. The total number of ways to do this is of course your left hand side. Here we first gave to M and then to K.

    But look at what finally happens...
    There are k balls in K which are from M and in turn from N. And there are 'm-k' balls in M from N. (*)

    So we can now do the same division with first K and then M. Give 'k' balls to K from N(how many combinations?) and then out of the remaining 'n-k' balls in N, give 'm-k' balls to M(how many combinations?). So the end situation is identical to (*). And the total number of combinations is your R.H.S

    So we have counted the same procedure in two different ways.....
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 10th 2011, 01:42 PM
  2. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 21st 2010, 02:47 AM
  3. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: June 4th 2010, 04:12 PM
  4. Combinatorial proof help
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 30th 2009, 05:43 PM
  5. Combinatorial proof?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 24th 2008, 06:20 PM

Search Tags


/mathhelpforum @mathhelpforum