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

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)$

• Concerning the specific problem at the end, use the multiplication principle with steps (1) choose 3 spots for the consonants, (2) place 3 consonants in those chosen spots, (3) place two vowels in the other two spots.
– Ned
Jun 27 '14 at 22:41

\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.

• NOTE TO FUTURE USERS: This combined with TheSparkThatThought's answer and Ned's comment at the original question will guide you to the way someone must think. Jun 27 '14 at 23:12

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}$.

• But we want both k and n-k (3+2) Jun 27 '14 at 20:06
• Once you have chosen the elements to include, (exclude) all the other elements will be implicitly excluded (included). So you need only choose one set. Jun 27 '14 at 20:08
• Don't we care about the priority? If $C(5,3)$ is the placement of 3 (different) consonants and $P(21,3)$ the projection of specific letters to those 3 places, how do we reason the rest...? :S Jun 27 '14 at 20:53
• @ZlatanderZechpreller : I think the term is being construed quite broadly. Jun 27 '14 at 23:47

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}$.

• This explanation made it 'click' for me. Is it fair to say that n choose n-k is the inverse of n choose k? Sep 5 '20 at 11:08
• I believe that the word you want here is contraposition. @Calydon
– Joel
Sep 7 '20 at 2:42

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 }$$

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.

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.

$\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.