Solutions for Chapter 5

Section Solutions for Chapter 5

Solutions to Exercise 5.1.5

5.1.5.2 There are

$\displaystyle 6^3$ ways for the teacher gifts to be chosen (each child can choose any one of the six types of prizes to give to his teacher). There are

$\displaystyle \multiset{6}{3}$ ways for Kim to choose his other three prizes;

$\displaystyle \multiset{6}{2}$ ways for Jordan to choose his other two prizes, and

$\displaystyle \multiset{6}{5}$ ways for Finn to choose his other five prizes. Thus, the total number of ways for the prizes (including teacher gifts) to be chosen is

$\begin{align*} 6^3 \multiset{6}{3}\multiset{6}{2}\multiset{6}{5}\amp= 6^3\binom{6+3-1}{3}\binom{6+2-1}{2}\binom{6+5-1}{5}\\ \amp= 6^3\binom{8}{3}\binom{7}{2}\binom{10}{5}\\ \amp= 6^3\cdot 56\cdot 21\cdot 252=64,012,032\text{.} \end{align*}$

5.1.5.3 Since the judges must choose at least one project from each age group, this is equivalent to a problem in which they are choosing only six projects to advance, with no restrictions on how they choose them. They can choose six projects from three categories in

$\displaystyle \multiset{3}{6}=\binom{3+6-1}{6}=\binom{8}{6}=28$ ways.

Solutions to Exercise 5.1.6

5.1.6.1 Combinatorial Proof. The problem: We will count the number of ways of choosing

$\displaystyle k$ items from a menu that has

$\displaystyle n$ different entries (including mac and cheese), in two ways.

Counting method 1: By definition, the answer to this is $\displaystyle \multiset{n}{k}\text{.}$

Counting method 2: We divide our count into two cases, according to whether or not we choose any orders of mac and cheese. If we do not choose any mac and cheese, then we must choose our $\displaystyle k$ items from the other $\displaystyle n-1$ entries on the menu. We can do this in $\displaystyle \multiset{n-1}{k}$ ways. If we do choose at least one order of mac and cheese, then we must choose the other $\displaystyle k-1$ items from amongst the $\displaystyle n$ entries on the menu (with mac and cheese still being an option for additional choices). We can do this in $\displaystyle \multiset{n}{k-1}$ ways. By the sum rule, the total number of ways of making our selection is $\displaystyle \multiset{n-1}{k}+\multiset{n}{k-1}\text{.}$

Conclusion: Since both of these methods are counting the same thing, the answers must be equal, so

$\displaystyle \multiset{n}{k}=\multiset{n-1}{k}+\multiset{n}{k-1}\text{.}$ ◾

Solutions to Exercise 5.2.5

5.2.5.1 There are

$\displaystyle 14$ words in the list. The word “the” appears three times; the words “on” and “child” appear twice each; the other seven words each appear once. Thus, the number of “poems” (orderings of the set) is

$\begin{equation*} \binom{14}{3,2,2,1,1,1,1,1,1,1} =\frac{14!}{3!2!2!}=3,632,428,800\text{.} \end{equation*}$