How to explain that n choose k is equal to n choose (n-k)?

[Eclair_de_XII]

Homework Statement

"Explain combinatorially (not algebraically) why ##\binom n k=\binom n {n-k}##. In other words, explain why this is true using words, and not algebraic manipulations."

Homework Equations

##\binom n k = \frac{n!}{k!(n-k)!}##

The Attempt at a Solution

"Suppose you have a set of ##n## elements ##S_n##. Partition this set into two disjoint subsets of ##k## elements ##S_k## and ##n-k## elements ##S_{n-k}##. There are ##\frac{n!}{(n-k)!}## total ways to create ##S_k##, and of those total ways, a given set of ##k## elements will have ##k!## permutations. So there are ##\binom n k = \frac{n!}{k!(n-k)!}## unduplicated sets of ##k## elements."

I'm having trouble seeing as how this is the same as creating all possible ##S_{n-k}##.

 

[Orodruin]

How many elements were not chosen when you picked out ##k## elements from ##n## elements?

 

[Orodruin]

Also, it is clearly a mathematical fact, since
$$
{n \choose n-k} = \frac{n!}{(n-k)!(n-(n-k))!} = \frac{n!}{(n-k)!k!} = {n \choose k}.
$$

 

[stevendaryl]

Homework Statement

"Explain combinatorially (not algebraically) why ##\binom n k=\binom n {n-k}##. In other words, explain why this is true using words, and not algebraic manipulations."

Homework Equations

##\binom n k = \frac{n!}{k!(n-k)!}##

The Attempt at a Solution

"Suppose you have a set of ##n## elements ##S_n##. Partition this set into two disjoint subsets of ##k## elements ##S_k## and ##n-k## elements ##S_{n-k}##. There are ##\frac{n!}{(n-k)!}## total ways to create ##S_k##, and of those total ways, a given set of ##k## elements will have ##k!## permutations. So there are ##\binom n k = \frac{n!}{k!(n-k)!}## unduplicated sets of ##k## elements."

I'm having trouble seeing as how this is the same as creating all possible ##S_{n-k}##.

Think concretely. You have a group of ##n## people and you have two tables, one with ##k## seats and one with ##n-k## seats. There are two different ways to think about assigning people to tables: (1) You can pick ##k## people for the first table. There are ##\left( \begin{array} \\ n \\ k \end{array} \right)## ways to do this. Anyone who isn't assigned to the first table is automatically assigned to the second table. (2) You can pick ##n-k## people to assign to the second table. There are ##\left( \begin{array} \\ n \\ n-k \end{array} \right)## ways to do this. Anyone not assigned to the second table is assigned to the first table.

Obviously, these are equivalent, so the number of ways should be the same.

 

[Ray Vickson]

Homework Statement

"Explain combinatorially (not algebraically) why ##\binom n k=\binom n {n-k}##. In other words, explain why this is true using words, and not algebraic manipulations."

Homework Equations

##\binom n k = \frac{n!}{k!(n-k)!}##

The Attempt at a Solution

"Suppose you have a set of ##n## elements ##S_n##. Partition this set into two disjoint subsets of ##k## elements ##S_k## and ##n-k## elements ##S_{n-k}##. There are ##\frac{n!}{(n-k)!}## total ways to create ##S_k##, and of those total ways, a given set of ##k## elements will have ##k!## permutations. So there are ##\binom n k = \frac{n!}{k!(n-k)!}## unduplicated sets of ##k## elements."

I'm having trouble seeing as how this is the same as creating all possible ##S_{n-k}##.

Every subset has a complement (which is another subset). The number of subsets equals the number of complements.