Prove discrete math identity C(n,r)⋅C(r,k) = C(n,k)⋅C(n-k,r-k)?

Prove the identity C(n,r)⋅C(r,k) = C(n,k)⋅C(n-k,r-k), whenever n, r, and k are nonnegative integers with r≤n and k≤r,

a) Using a combinatorial argument

b) using an argument based on the formula for the number of r-combinations of a set with n elements

It really has me stumped!

4 Answers

Relevance
  • Awms A
    Lv 7
    8 years ago
    Best Answer

    Define

    [n] = {1, 2, ... , n}.

    Then choose a pair of subsets A and B such that

    (1) A is a subset of B

    (2) |A| = k

    (3) |B| = r.

    Either

    (1) Choose a subset of [n] with r elements and call it B. Then choose a subset of B with k elements and call it A. This corresponds to the product C(n,r)⋅C(r,k).

    or

    (2) Choose a subset of [n] with k elements and call it A. Then choose a subset of [n] \ A with r-k elements, call it X, and then define B = A U X. This corresponds to the product C(n,k)⋅C(n-k,r-k).

    Every such pair of subsets A,B is defined uniquely by such a procedure, so this proves the equality.

  • 8 years ago

    b) is just simple algebra.

    [n!/(r! (n-r)!] * [r!/(k! (r-k)!] = [n!/(k! (n-k)!)] * [(n-k)!/(r-k)! (n-r)!]

    In the last term I wrote (n - r) because (n-k)-(r-k) = (n-r).

    On the left the r! terms cancel out. On the right the (n-k)! terms cancel out. Everything else matches up, same terms on the left and the right.

    Part (a) means you have to come up with two ways of counting the same thing, one of which uses the expression on the left and the other uses the expression on the right.

    On the left you pick r things out of a group of n, and you also pick k things out of a group of r. On the right, first you pick k things out of a group of r, then you pick (r - k) things out of a group of (n - k). I have to think about a situation where multiplying those two things is a reasonable thing to do.

    OK, how about this: First I pick a committee of r people from a group of n, then I pick k people from the committee to be the officers. How many possible committee/officer combinations are there?

    Right hand side: What if first I pick the k officers, then the rest of the committee? Make an argument that the right-hand side is a correct way to count it.

  • pruski
    Lv 4
    3 years ago

    it rather is stressful. i'd desire to arise with a gaggle of random data approximately any journey and turn them into "eerie coincidences" too. occasion: Abraham Lincoln dies the suited same day the great sinks, different than 40 seven years earlier! The massive had the means to hold 3,547 passengers aboard! They the two have 40 seven! I truthfully think of terrorists don't have THAT lots time on their palms to take a seat and plan all of those issues out. they have extra desirable issues to do, like, blow themselves up.

  • 8 years ago

    I will prove using b.

    Left: ( n! / (n-r)!r! ) * (r! / (r - k)!k!)

    = n! / (n-r)!(r-k)!k!

    Right: (n! / (n-k)!k!) * (n-k)! / (n-k-r+k)!(r-k)!

    =(n! / (n-k)!k!) * (n-k)! / (n-r)!(r-k)!

    =n! / (n-r)!(r-k)!k!

    Hence the left and right are equal

Still have questions? Get your answers by asking now.