Section Solutions for Chapter 4
Solutions to Exercise 4.1.3
Solutions to Exercise 4.2.10
Counting method 1: From the n dogs, we first choose the r who will enter the competition. This can be done in (nr) ways. For each of these ways, we can choose k of the r competitors to become finalists in (rk) ways. Thus, there are a total of (nr)(rk) ways to choose the dogs.
Counting method 2: From the n dogs, choose k who will be the finalists. This can be done in (nk) ways. For each of these ways, we can look at the remaining n−k dogs and choose r−k to be the competitors who will not be finalists, in (n−kr−k) ways. Thus, there are a total of (nk)(n−kr−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 (nr)(rk)=(nk)(n−kr−k). ◾Counting method 1: From the 2n total people, choose n of them for the random sample. This can be done in (2nn) ways.
Counting method 2: Let r represent the number of men who will be in the sample. Notice that r may have any value from 0 up to n. We divide the problem into these n+1 cases, and take the sum of all of the answers. In each case, we can choose the r men for the sample from the n men, in (nr) ways. For each of these ways, from the n women, we choose r who will not be part of the sample (so the remaining n−r will be in the sample, for a total of r+n−r=n people in the sample). There are (nr) ways to do this. Thus the total number of ways of choosing r men and n−r women for the sample is (nr)2. Adding up the solutions for all of the cases, we obtain a final answer of n∑r=0(nr)2.
Conclusion: Since both of these solutions count the answer to the same problem, the answers must be equal, so we have n∑r=0(nr)2=(2nn). ◾