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.