1.2.3 problem 21

(a)

Case 1: If Tony is in a group by himself, then we have to break the remaining $n$ people into $k-1$ groups. This can be done in $$\left\{\begin{array}{c}n\\ k-1\end{array}\right\}$$

ways.

Case 2: If Tony is not in a group by himself, then we first break up the remaining $n$ people into $k$ groups. Then, Tony can join any of them. The number of possible groups then is

$$k\left\{\begin{array}{c}n\\ k\end{array}\right\}$$

Case 1 and 2 together count the number of ways to break up $n+1$ people into $k$ non empty groups, which is precisely what the left side of the equation counts.

(b)

Say Tony wants to have $m$ in his group. That is to say he does not want $n-m$ people. These $n-m$ people must then be broken into $k$ groups.

The number of people Tony wants to join his group can range from $0$ to $n-k$. The reason for the upper bound is that at least $k$ people are required to make up the remaining $k$ groups.

Taking the sum over the number of people in Tony’s group we get

$$\sum _{j=0}^{n-k}\left(\frac{n}{j}\right)\left\{\begin{array}{c}n-j\\ k\end{array}\right\}$$

Now, instead of taking the sum over the number of people Tony wants in his group, we can equivalently take the sum over the number of people Tony does not want in his group. Hence,

$$\sum _{j=0}^{n-k}\left(\frac{n}{j}\right)\left\{\begin{array}{c}n-j\\ k\end{array}\right\}=\sum _{i=n}^k\left(\frac{n}{i}\right)\left\{\begin{array}{c}i\\ k\end{array}\right\}$$

Since the sum counts all possible ways to group $n+1$ people into $k+1$ groups, we have

$$\sum _{i=n}^k\left(\frac{n}{i}\right)\left\{\begin{array}{c}i\\ k\end{array}\right\}=\left\{\begin{array}{c}n+1\\ k+1\end{array}\right\}$$

as desired.