Anonymous
Anonymous asked in Science & MathematicsMathematics · 3 months ago

Prove (n, k) = (n, n - k)?

(n, k) = "n choose k" combination

I can't use the formula for (n, k) = n!/[(n-k)!k!]

Is there an algebraic solution to it?

Update:

Textbook tells me to use one-to-one correspondence, but I'm not sure if that's what the professor wants.

6 Answers

Relevance
  • 3 months ago
    Favorite Answer

    ALGEBRAIC SOLUTION:

    I like to use this notation:

    C(n, k) = n! / [(n - k)! k!]

    That would mean:

    C(n, n - k) = n! / [(n - (n-k))! (n - k)!]

    C(n, n - k) = n! / [k! (n - k)!]

    C(n, n - k) = n! / [(n - k)! k!]

    Hence:

    C(n, k) = C(n, n-k)

    ONE-TO-ONE CORRESPONDENCE:

    As for a one-to-one correspondence, we know that C(n, k) represents the ways from n items to pick a combination of k items. Now for each and every case where you have picked a combination of k items, you have left (n - k) items behind. So if you instead started with n items and picked n - k items to leave behind, you'd get the same number of combinations.

    Example take the set {A, B, C, D, E} and pick combinations of 2 items (leaving 3 behind}:

    C(5,2) = C(5,3)

    {A, B} <--> {C, D, E}

    {A, C} <--> {B, D, E}

    {A, D} <--> {B, C, E}

    {A, E} <--> {B, C, D}

    {B, C} <--> {A, D, E}

    {B, D} <--> {A, C, E}

    {B, E} <--> {A, C, D}

    {C, D} <--> {A, B, E}

    {C, E} <--> {A, B, D}

    {D, E} <--> {A, B, C}

    So C(n,k) = C(n, n-k)

  • 3 months ago

    another proof of something that has been proved at least 1 million times before.

    Great

    have a look at Pascal's triangle.

    It is the simple and only needed proof.

    No teacher (not one) of math in the world today is at least as smart as Pascal was.

  • nCk = n! / (k! * (n - k)!)

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

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

    n! / ((n - k)! * (n - n + k)!) =>

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

    Which is the same as n! / (k! * (n - k)!)

  • 3 months ago

    Okay, (n, k) = (n,n-k) because i ******* say so.... and I'm the god of my own world, so I say its proven. NEXT!

  • How do you think about the answers? You can sign in to vote the answer.
  • 3 months ago

    In order to prove anything about (n, k), you need to have a definition of what (n, k) means. If it's not n!/[k!(n-k)!], then what is it?

    Probably something like "the number of combinations of n distinct items taken k at a time"; is that it?

    What they're probably trying to get you to understand is that picking k items out of n to make a combination is the same thing as picking the (n-k) items that are NOT in the combination. With that, then it's obvious that the number of different ways to pick k items for a combination must be the same number of ways to pick the n-k items that aren't there.

    About the update and 1:1 correspondence...

    One-to-one correspondence is set theory, so use sets.

    Let S be a set of n items and C_k be the set of all subsets of S with exactly k elements. [0<=k<=n] Then |C_k| = (n,k). Set up the 1:1 correspondence between C_k and C_(n-k) based on the fact that if U and V are subsets of S then U=V iff (S-U)=(S-V).

    If U is in C_k, then there's a unique V=S-U in C_(n-k), and vice versa.

  • Pope
    Lv 7
    3 months ago

    This does not rise to the level of proof, but a conceptual understanding might be useful.

    The value C(n, k) is the number of ways to choose k items from a pool of n distinct items. When the k items are chosen, we are also choosing (n - k) items to leave behind, so it is all one. Choosing k is equivalent to choosing (n - k).

    C(n, k) = C(n, n - k)

Still have questions? Get your answers by asking now.