Combinatorics

4.1.3.1 When counting the number of subsets of an \(\displaystyle n\)-set, we saw that there is a bijection between that number and the number of binary strings of length \(\displaystyle n\text{:}\) identify each element of the set with a position in the string, and put a \(\displaystyle 0\) in that position if the element is not in the subset, and a \(\displaystyle 1\) if it is.

Analogously, we can find a bijection between the number of these structures and the number of ternary strings of length \(\displaystyle n\) (strings containing \(\displaystyle 0\text{,}\) \(\displaystyle 1\text{,}\) or \(\displaystyle 2\) in each position). Identify each element of the set with a position in the string, put a \(\displaystyle 0\) in that position if the element is not in the structure, a \(\displaystyle 1\) if it occurs once, and a \(\displaystyle 2\) if it occurs twice. Thus, we can form \(\displaystyle 3^n\) structures from the set \(\displaystyle \{1,\ldots, n\}\text{:}\) there are 3 choices for each of the \(\displaystyle n\) entries in the ternary string.

4.1.3.3 We identify each of the ten Olympic contenders with a crib, and each of the three dolls with one of the three medals. If the doll corresponding to the gold medal goes into crib \(\displaystyle i\text{,}\) this corresponds to the competitor corresponding to crib \(\displaystyle i\) winning the gold medal. Similarly, if the doll corresponding to the silver medal goes into crib \(\displaystyle j\text{,}\) this is equivalent to the contender corresponding to crib \(\displaystyle j\) winning the silver medal; and the doll corresponding to bronze going into crib \(\displaystyle k\) is equivalent to the contender corresponding to crib \(\displaystyle k\) winning the bronze medal.

4.2.10.2 Combinatorial Proof. The problem: We use the problem given to us in the hint, so will be counting the number of ways to start with \(\displaystyle n\) dogs, determine \(\displaystyle r\) who will enter a competition and \(\displaystyle k\) of those who will be finalists.

Counting method 1: From the \(\displaystyle n\) dogs, we first choose the \(\displaystyle r\) who will enter the competition. This can be done in \(\displaystyle \binom{n}{r}\) ways. For each of these ways, we can choose \(\displaystyle k\) of the \(\displaystyle r\) competitors to become finalists in \(\displaystyle \binom{r}{k}\) ways. Thus, there are a total of \(\displaystyle \binom{n}{r}\binom{r}{k}\) ways to choose the dogs.

Counting method 2: From the \(\displaystyle n\) dogs, choose \(\displaystyle k\) who will be the finalists. This can be done in \(\displaystyle \binom{n}{k}\) ways. For each of these ways, we can look at the remaining \(\displaystyle n-k\) dogs and choose \(\displaystyle r-k\) to be the competitors who will not be finalists, in \(\displaystyle \binom{n-k}{r-k}\) ways. Thus, there are a total of \(\displaystyle \binom{n}{k}\binom{n-k}{r-k}\) ways to choose the dogs.

Conclusion: Since both of these solutions count the answer to the same problem, the answers must be equal, so we have \(\displaystyle \binom{n}{r}\binom{r}{k}=\binom{n}{k}\binom{n-k}{r-k}\text{.}\) ◾

4.2.10.3 Combinatorial Proof. The problem: We will count the number of ways to choose a random sample of \(\displaystyle n\) people from a class of \(\displaystyle n\) men and \(\displaystyle n\) women.

Counting method 1: From the \(\displaystyle 2n\) total people, choose \(\displaystyle n\) of them for the random sample. This can be done in \(\displaystyle \binom{2n}{n}\) ways.

Counting method 2: Let \(\displaystyle r\) represent the number of men who will be in the sample. Notice that \(\displaystyle r\) may have any value from \(\displaystyle 0\) up to \(\displaystyle n\text{.}\) We divide the problem into these \(\displaystyle n+1\) cases, and take the sum of all of the answers. In each case, we can choose the \(\displaystyle r\) men for the sample from the \(\displaystyle n\) men, in \(\displaystyle \binom{n}{r}\) ways. For each of these ways, from the \(\displaystyle n\) women, we choose \(\displaystyle r\) who will not be part of the sample (so the remaining \(\displaystyle n-r\) will be in the sample, for a total of \(\displaystyle r+n-r=n\) people in the sample). There are \(\displaystyle \binom{n}{r}\) ways to do this. Thus the total number of ways of choosing \(\displaystyle r\) men and \(\displaystyle n-r\) women for the sample is \(\displaystyle \binom{n}{r}^2\text{.}\) Adding up the solutions for all of the cases, we obtain a final answer of \(\displaystyle \sum_{r=0}^n\binom{n}{r}^2\text{.}\)

Conclusion: Since both of these solutions count the answer to the same problem, the answers must be equal, so we have \(\displaystyle \sum_{r=0}^n\binom{n}{r}^2=\binom{2n}{n}\text{.}\) ◾

4.2.11.1 We could use this expression to count the number of ways of choosing one leader and some number (which could be zero) of other team members for a project, from a group of \(\displaystyle n\) people. There are \(\displaystyle n\) ways to choose the leader, and for each of these, there are \(\displaystyle 2^{n-1}\) ways of choosing a subset of the other \(\displaystyle n-1\) people to be team members.

4.2.11.3 We could use this expression to count the number of ways of starting with a collection of \(\displaystyle n\) books, choosing \(\displaystyle r\) books to put out on bookshelves and some other number (which could be zero) of other books to keep but not display. We break this down into cases depending on the total number \(\displaystyle k\) of books that are kept (including the displayed books), which could be anywhere from \(\displaystyle r\) up to \(\displaystyle n\text{.}\) We will take the sum of all of the answers. In each case, there are \(\displaystyle \binom{n}{k}\) ways of choosing the \(\displaystyle k\) books to keep, and for each such choice, there are \(\displaystyle \binom{k}{r}\) ways of choosing the \(\displaystyle r\) books to display from the books that are kept. Thus, there are a total of \(\displaystyle \sum_{k=r}^n\binom{n}{k}\binom{k}{r}\) solutions to this problem.