Why ${n \choose k} = {n \choose n-k}$?

Question

They say that $${n \choose k}={n \choose n-k}.$$

Can someone explain its meaning?

---

Among many problems that use this proof, here is an example:

The english alphabet has $26$ letters of which $5$ are vowels (and $21$ are consonants).

How many $5$-letter words can we form by using $3$ different consonants and $2$ different vowels?

I understand where the answer says we have:

$$P(21,3) = 21\times 20\times 19 = 7980\ ,$$

and

$$P(5,2) = 5\times4 = 20\ .$$

We get the permutations for each category. Now we must place them into $5$ places, but it says this is done by computing:

$$C(5,3)$$

and it explains further:

For each case, the rest of the letters will be vowels.

(Aren't we supposed to check that case?)

It ends by multiplying all three together: $C(5,3)\times P(21,3)\times P(5,2)$

Answer 1

$$ \begin{align} \dbinom{6}{2} & \longleftrightarrow \dbinom{6}{6-2} \\[8pt] AB & \longleftrightarrow CDEF \\ AC & \longleftrightarrow BDEF \\ AD & \longleftrightarrow BCEF \\ AE & \longleftrightarrow BCDF \\ AF & \longleftrightarrow BCDE \\ BC & \longleftrightarrow ADEF \\ BD & \longleftrightarrow ACEF \\ BE & \longleftrightarrow ACDF \\ BF & \longleftrightarrow ACDE \\ CD & \longleftrightarrow ABEF \\ CE & \longleftrightarrow ABDF \\ CF & \longleftrightarrow ABDE \\ DE & \longleftrightarrow ABCF \\ DF & \longleftrightarrow ABCE \\ EF & \longleftrightarrow ABCD \end{align} $$ There are exactly as many ways to choose $2$ out of $6$ as to choose $6-2$ out of $6$ because each way of choosing $2$ out of $6$ has a corresponding way of choosing $6-2$ out of $6$ and vice-versa.

Answer 2

Consider a collection of $n$ objects. Choosing $k$ of them to place into a set is equivalent to choosing $n-k$ to leave out.

Edit: Consider a high school dodgeball game with a red team and a blue team. There are $n$ total students, and the blue team has $k$ students. Since every student plays, there are $n-k$ students on the red team.

Because the PE teacher is biased, he lets the blue team pick all of their players first. They have $\binom{n}{k}$ ways to do this. After that, the red team has no choices. They must pick all of the remaining $n-k$ students.

There would be an equal number of ways to do this if the teacher was biased towards red, so $\binom{n}{k} = \binom{n}{n-k}$.

Answer 3

When we have $n$ objects to choose from, and we choose to include $k$ of them, there are ${n\choose k}$ ways of choosing these objects. However, at the same time we are choosing not to include $n-k$ objects, and there are ${n \choose n-k}$ ways of excluding these objects. Thus we have that ${n \choose k} = {n \choose n-k}$.

Answer 4

If you have $n=a+b$ boxes of which $a$ contain a ball and $b$ are empty, you can choose $a$ to contain a ball in $\binom na$ ways or $b$ to be empty in $\binom nb$ ways. The two are clearly equivalent, because they are counting the same thing.

Answer 5

$\binom{n}{k}$ represents the cardinality of set of all subsets of cardinality $k$ from a set of cardinality $n$. The fact that $\binom{n}{k}=\binom{n}{n-k}$ represents that there are the same number of elements in the new set you obtain when you take the complement of each of the $k$ element subsets.

Answer 6

Symmetry of summation.

$$ (x+y)^n - (y+x)^n = 0, $$

so

$$ \sum_{k=0}^n {n \choose k} x^k y^{n-k} - \sum_{k=0}^n {n \choose k} y^k x^{n-k} = 0, $$

whence

$$ \sum_{k=0}^n \left[ {n \choose k} - {n \choose n-k} \right] x^k y^{n-k} = 0, $$

as valid for aribtrary $x$ and $y$ we obtain

$$ {n \choose k} = {n \choose n-k} $$

---

The physical meaning - indeed...

Given are $(k)$ white balls and $(n-k)$ black balls, we can form $\displaystyle n \choose \displaystyle k$ permutations.

Given are $(n-k)$ white balls and $(k)$ black balls, we can form $\displaystyle n \choose \displaystyle n-k$ permutations.

Both cases are symmetrical (black ball $\leftrightarrow$ white ball), so

$$ {n \choose k} = {n \choose n-k } $$

Answer 7

You can use the definition of $\binom{n}{k}=\frac{n!}{k!(n-k)!}$ :

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

In my experience this is the easiest proof that I found of this without having to go through a lot of combinatorial arguments. It just "drops out" from algebraic manipulation due to the inherit symmetry.