1

Can someone explain to me why these 2 formulas are equivalent: $${n \choose k} = {n \choose n-k}$$

gebruiker
  • 6,154
A_for_ Abacus
  • 1,899
  • An idea on why this works: consider the symmetry of Pascal's triangle. This isn't a proof by any means, but it is a memory aid. – apnorton May 05 '14 at 19:52

4 Answers4

2

Think of it this way: Say we have a collection of $n$ things and will be taking $k$ of them with us. Then we can either choose which $k$ to take with us--which we can do in $\binom{n}{k}$ ways--or choose which $n-k$ not to take with us--which we can do in $\binom{n}{n-k}$ ways. Both approaches yield exactly the same result, so the counts are the same.

Cameron Buie
  • 102,994
2

You can see they are the same after a couple arithmetic operations.

${n \choose k} = {n! \over k!(n-k)!}$

${n \choose n-k} = {n! \over (n-k)!(n-(n-k))!} = {n! \over (n-k)!(n-n+k))!} = {n! \over (n-k)!(k)!} = {n! \over k!(n-k)!}$

joebloggs
  • 156
1

If you are choosing $k$ things out of a whole of $n$ is the same as not choosing the remaining $n-k$.

gebruiker
  • 6,154
  • 1
    @user2619038 Look at it this way: If you want to single out 3 out of 5 people for a prise, you can either say which 3 people are the lucky ones OR you can say wich 2 people are the losers. It does the same ting. – gebruiker May 05 '14 at 18:21
0

Consider a set $A$, and the cardinality of $A$, $|A|=n,\ n\in\mathbb{Z}^{\geqslant}$. The two subsets, $\mathcal{P}_r(A)$ and $\mathcal{P}_{n-r}(A)$ of the power set of $A$, $\mathcal{P}(A)$, have the same cardinality, i.e., $$ {n \choose r}={n \choose n-r}. $$

Teddy Frei
  • 427