Distributing Presents

Section 9.5 Distributing Presents

This is an application of permutations with repeated events.

Subsection 9.5.1 Distributing Presents

Suppose we have $n$ presents to distribute to $k$ children, such that each of the $n$ children get $n_1, \dots, n_k$ presents, respectively. Also, we want to all presents are distributed (i.e. $n_1 + \dots + n_k = n$). Then, we want to determine the number of ways this distribution can be done.

We can determine this by arranging the $n$ presents in a row, and having the child 1 take the first $n_1$ presents starting from the left, then child 2 takes the next $n_2$ presents, and so on, until child $k$ takes the remaining $n_k$ presents.

There are $n!$ ways to arrange the presents, however, multiple arrangements can lead to the same result (i.e. every kid getting the same presents). If child 1 gets 5 presents, then the order in which those 5 presents are given to them doesn't matter. In general, the $i$th child can arrange their presents in $n_i!$ ways. Thus, the total number of ways to distribute the presents is,

\begin{equation*} \frac{n!}{n_1! n_2! \cdots n_k!} \end{equation*}

Subsection 9.5.2 Alternate Intuition

Alternatively, we can think of this problem as choosing $n_1$ presents to give to the first child (which there are $\binom{n}{n_1}$ ways), then choosing $n_2$ presents among the remaining $(n - n_1)$ to give to the second child ($\binom{n-n_1}{n_2}$ ways), and so on. In general, we choose $n_i$ presents among the remaining $(n - n_1 - n_2 - \dots - n_{i-1})\text{,}$ for $\binom{n-n_1-\dots-n_{i-1}}{n_i}$ ways.

Thus, the total number of ways to distribute the presents is,

\begin{align*} \amp \binom{n}{n_1} \binom{n-n_1}{n_2} \cdots \binom{n-n_1-\cdots-n_{k-1}}{n_k}\\ \amp = \frac{n!}{n_1! (n - n_1)!} \cdot \frac{(n - n_1)!}{n_2! (n - n_1 - n_2)!} \cdots \frac{(n - n_1 - \dots - n_{k-1})!}{n_k! (n - n_1 - \dots - n_{k-1} - n_k)!}\\ \amp = \frac{n!}{n_1! n_2! \cdots n_k!} \end{align*}

Subsection 9.5.3 Examples

Example 9.5.1.

If $n = k$ and $n_1 = n_2 = \cdots = n_k = 1\text{,}$ this represents distributing $k$ presents (same number of presents as children) and giving each child exactly one present.

This is just arranging the presents to determine which child gets which present, or $n!\text{.}$ From this formula, we see it is also,

\begin{equation*} \frac{n!}{1! 1! \cdots 1!} = n! \end{equation*}

Example 9.5.2.

If $n_1 = n_2 = \cdots = n_{k-1} = 1$ and $n_k = n - k + 1\text{,}$ this represents giving all child 1 present, except the last child who gets the remaining $(n - k + 1)$ presents.

This involves choosing $(k - 1)$ presents from the $n$ available to give to the $(k-1)$ children ($\binom{n}{k-1}$ ways), and then giving the remaining presents to the last child. From the formula, we get,

\begin{equation*} \frac{n!}{1!1! \cdots (n - k + 1)!} = \frac{n!}{(n - (k - 1))!} = \binom{n}{k-1} \end{equation*}