14
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Ned
    Jun 27, 2014 at 22:41

7 Answers 7

16
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – Anna K.
    Jun 27, 2014 at 23:12
12
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ But we want both k and n-k (3+2) $\endgroup$
    – Anna K.
    Jun 27, 2014 at 20:06
  • 1
    $\begingroup$ 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. $\endgroup$
    – Roger Burt
    Jun 27, 2014 at 20:08
  • $\begingroup$ 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 $\endgroup$
    – Anna K.
    Jun 27, 2014 at 20:53
  • 2
    $\begingroup$ @ZlatanderZechpreller : I think the term is being construed quite broadly. $\endgroup$ Jun 27, 2014 at 23:47
9
$\begingroup$

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

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

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

$\endgroup$
0
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ That definition is only valid for n and k nonnegative integers with 0 <= k <= n. If, for example, you take n=-3 and k=2 then C(n,k)=6 but C(n,n-k) = 0. $\endgroup$ Feb 18, 2022 at 2:06
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .