13
$\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 '14 at 22:41
14
$\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
  • 2
    $\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 '14 at 23:12
11
$\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 '14 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 '14 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 '14 at 20:53
  • 2
    $\begingroup$ @ZlatanderZechpreller : I think the term is being construed quite broadly. $\endgroup$ Jun 27 '14 at 23:47
7
$\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 '20 at 11:08
  • 2
    $\begingroup$ I believe that the word you want here is contraposition. @Calydon $\endgroup$
    – Joel
    Sep 7 '20 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
2
$\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$

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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.