using sets in combinatorial identity proof

Question

I'm trying to understand a portion of a class lecture where we proved a combinatorial identity using sets.

PROBLEM: prove that ${n \choose r} = {n \choose n-r}$

We were told to consider a set A such that $|A| = n$. We know that the LHS counts subsets of size r and RHS is counting the elements not put in the subset. [I understand this].

Then we were shown that: if $|S| = n - r$ then $|A \setminus S| = r$. We have a "one to one correspondence" between subsets of size r and of size n-r. This proves the identity.

I tried to draw this out with venn diagram, but I do not see how subset containing $n-r$ elements would equal a subset of $r$ elements.

Any helpful ways of rewording this or picturing it differently would be appreciative.

Answer 1

It's a correspondence of sets, not an equality of sets.

Choosing $r$ elements from $n$ elements is the same as choosing all but $n-r$ elements from $n$ elements. In other words, given $n$-elements, instead of choosing the $r$-elements you want, you can choose the $n-r$ elements you don't want, and remove them.

Another way to see it: Each set is uniquely determined by its complement. If the universal set $X$ has $n$ elements, then the complement of an $r$ element set is an $n-r$ element set. Mapping each $r$-element subset of the $n$-element set $X$ to its complement yields a one-to-one correspondence between $r$-element subsets of $X$ and $(n-r)$-element subsets of $X$. It follows that the collection of $r$-element subsets of $X$ has the same cardinality as the collection of $(n-r)$-element subsets of $X$.

For example, suppose $X=\{1,2,3,4,5\}$.

As shown below, by matching each $2$-element subset of $X$ with its complement, we get a one-to-one correspondence between $2$-element subsets of $X$ and $3$-element subsets of $X$. \begin{align*} \{1,2\}\;&{\Large{{\leftarrow}\!\!{\rightarrow}}}\;\{3,4,5\}\\ \{1,3\}\;&{\Large{{\leftarrow}\!\!{\rightarrow}}}\;\{2,4,5\}\\ \{1,4\}\;&{\Large{{\leftarrow}\!\!{\rightarrow}}}\;\{2,3,5\}\\ \{1,5\}\;&{\Large{{\leftarrow}\!\!{\rightarrow}}}\;\{2,3,4\}\\ \{2,3\}\;&{\Large{{\leftarrow}\!\!{\rightarrow}}}\;\{1,4,5\}\\ \{2,4\}\;&{\Large{{\leftarrow}\!\!{\rightarrow}}}\;\{1,3,5\}\\ \{2,5\}\;&{\Large{{\leftarrow}\!\!{\rightarrow}}}\;\{1,3,4\}\\ \{3,4\}\;&{\Large{{\leftarrow}\!\!{\rightarrow}}}\;\{1,2,5\}\\ \{3,5\}\;&{\Large{{\leftarrow}\!\!{\rightarrow}}}\;\{1,2,4\}\\ \{4,5\}\;&{\Large{{\leftarrow}\!\!{\rightarrow}}}\;\{1,2,3\}\\[4pt] & \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \text{which illustrates the identity}\\[4pt] \binom{5}{2}&\;\,=\;\,\binom{5}{3}\\ \end{align*}

Answer 2

The idea here is that we want to show that there exists a bijection between the two sets of sets.

Let $\mathcal{A}$ be the set of subsets of $\{1,2,3,\dots,n\}$ who have size $r$, i.e. $\mathcal{A}=\{A~:~A\subseteq\{1,2,3,\dots,n\},~|A|=r\}$.

Let $\mathcal{B}$ be the set of subsets of $\{1,2,3,\dots,n\}$ who have size $n-r$.

We define a function $f~:~\mathcal{A}\to\mathcal{B}$ such that $f(A)=\{1,2,3,\dots,n\}\setminus A$.

We can check that $f$ is indeed a valid function and is indeed a bijection. This proves as a result that $|\mathcal{A}|=|\mathcal{B}|$.

Since we know that $|\mathcal{A}|=\binom{n}{r}$ by definition, and similarly $|\mathcal{B}|=\binom{n}{n-r}$, it follows that $\binom{n}{r}=\binom{n}{n-r}$

---

In analogy, choosing $r$ winners from $n$ people and letting the rest be losers is equivalent to choosing $n-r$ losers from $n$ people and letting the rest be winners.