Anonymous
Anonymous asked in Science & MathematicsMathematics · 7 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.

Relevance

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)

• Login to reply the answers
• 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.

• Login to reply the answers
• 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)!)

• Login to reply the answers
• 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!

• Login to reply the answers
• 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.

• Login to reply the answers
• 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)

• Login to reply the answers