Proof that ${m+n \choose m} = {m+n \choose n}$

Question

This proof follows quite easily using the factorial definition of ${n \choose k}$,

$${m+n \choose m} = \frac{(m+n)!}{m!((m+n)-m)!} = \frac{(m+n)!}{m!n!} = \frac{(m+n)!}{((m+n)-n)!n!} = {m+n \choose n}$$

However I am aware that ${n \choose k}$ is not thought as $\frac{n!}{k!(n-k)!}$ but rather the number of k element subsets of n, and can be proven to equate the the latter formula.

So, my question? What is another proof of this equation using the standard 'thought of' definition of ${n \choose k}$. How can this be proven in terms of subsets? Or simply, is there another way to prove the equation?

Answer 1

${M \choose a}$ is the number of ways of choosing $a$ objects from $M$ objects and putting them in a bag and taking them home with you.

But what if instead of putting those objects in the a bag and taking them home with you you left them on the table and put every thing else in the bag and took everything else home with you. For every way there is to take an object there is precisely one way of leaving that object.

The number of ways to take $a$ objects and leaving $M-a$ objects is the exact same number of ways of leaving $a$ and taking $M-a$ objects.

So ${M\choose a} = {M \choose M-a}$.

Answer 2

If $X$ is a set of cardinality $m+n$, then $A$ is a subset of $X$ of cardinality $m$ iff $X\setminus A$ is a subset of $X$ of cardinality $n$. Counting the subsets of $X$ of cardinality $m$ yields the same result as counting their complements in $X$.

Answer 3

Suppose we have ${a+b \choose a} = {a+b \choose b}$ if we let $n = a+b$ and $k=a$ we have that $b = n-k$ and ${n \choose k} = {n \choose n-k}$. Proofs of this equivalent statement are superfluous, however I will proceed to provide one in any case.

Lets see a an example with the power-set of [3], the subsets are $\{\emptyset, \{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$

by our supposed equation we have that the number of subsets of length $0$ is equal to the number of subset of length $3$. Also the number of subsets of length $1$ must be the same as the number of subsets of length $2$.

hence we must find a bijection that maps $\emptyset$ to $\{1,2,3\}$ and elements $\{1\},\{2\},\{3\}$ to elements $\{1,2\},\{1,3\},\{2,3\}$.

the mapping that does this is is the mapping that assigns subset of length k to their complements.

$$ \emptyset \mapsto (\emptyset^{c} = \{1,2,3\}) $$ $$ \{1\} \mapsto \{2,3\}$$ $$ \{2\} \mapsto \{1,3\}$$ $$ \{3\} \mapsto \{1,2\}$$ Now me must show that this mapping is indeed a bijection.

Now for the proof, let $A$ to be subsets of length $k$ and $B$ to be subsets of length $n-k$. Define a bijection $f:A \longrightarrow B$ as $f(S) = S^{c} = [n]\backslash S$. To prove $f$ is bijective we can show $f$ has an inverse. Define $g:B \longrightarrow A$ as $g(S) = S^c$, then $f(g(S)) = (S^c)^c = S$ and $g(f(S)) = (S^c)^c = S$, $g$ then must be an inverse to $f$ and hence f is a bijection. Since we have found a bijection from $A$ to $B$ we can conclude that they $|A| = |B|$. Thus there are equal numbers of subsets of length $k$ and $k-n$.

Answer 4

Any time you choose $m$ elements from a set of size $m+n$, you have implicitly also chosen $n$ elements: the ones you left out.

Answer 5

If you want to form a group of size $m$ out of $m + n$ people, you can either pick the $m$ people in the group or you can pick the $n$ people not in the group, the outcome would be the same.