Distributing Money

Section 9.4 Distributing Money

This is an application of combinations.

Subsection 9.4.1 Distributing Money

Consider $n$ identical dollars to be distributed to $k$ people, such that each person gets at least 1 dollar.

Line up all the dollars (the order doesn't matter). Let the first person choose dollars from left to right, until we stop them. Then, let the second person continue collecting dollars from left to right, until they are stopped, and so on. In this way, the number of ways to distribute the dollars is equivalent to the number of ways to split up the $n$ dollars with “cuts” to specify where one person stops and the next starts.

Note that there are $n-1$ possible positions to place a cut, since you can only a cut before any of the $n$ dollars, except the first one. Also, there are $k-1$ cuts to make, since we need to put a marker to specify where each person starts collecting, except the first person which will always start at the beginning. Thus, there are $\binom{n-1}{k-1}$ ways to do this.

Theorem 9.4.1.

The number of ways to distribute $n$ identical objects to $k$ people, such that each person gets at least one of the objects, is,

\begin{equation*} \boxed{\binom{n-1}{k-1}} \end{equation*}

This result can be used to consider a more general case, where $n$ identical dollars are distributed to $k$ people (with no requirement that everyone gets at least one).

Instead, borrow 1 dollar from each person, and distribute the resulting $n+k$ dollars such that every person gets at least 1 dollar. In this way, every person will at least have their 1 dollar returned, and they may or may not get more than that. From the previous problem, the number of ways to distribute $n+k$ dollars among $k$ people, such that every person gets at least 1, is,

\begin{equation*} \binom{n+k-1}{k-1} \end{equation*}

Theorem 9.4.2.

The number of ways to distribute $n$ identical objects to $k$ people is,

\begin{equation*} \boxed{\binom{n+k-1}{k-1}} \end{equation*}

Note that this number is clearly larger than the previous case.

Example 9.4.3.

Determine the number of ways to distribute $n$ identical dollars to $k$ people, such that each person gets at least 2 dollars.

First, give 1 dollar to each person, so that there are $n-k$ dollars left. Then, distribute those $-k$ dollars such that every person gets at least 1 dollar. In this way, each person will get at least 2 dollars. From the previous problem, there are,

\begin{equation*} \binom{n-k-1}{k-1} \end{equation*}

ways to distribute $n-k$ dollars to $k$ people, such that each person gets at least 1 dollar.

Example 9.4.4.

Determine the number of ways that $k$ people can be seated in $n$ consecutive seats, such that no two people sit next to one another.

First, “Remove” $k-1$ seats to leave $n - (k-1) = n - k + 1$ seats remaining. The number of ways that $k$ people can be arranged in $n - k + 1$ seats (where they can sit next to each other) is,

\begin{equation*} \binom{n-k+1}{k} \end{equation*}

Then, insert the remaining $k-1$ seats to the right of every person, except the last person. In this way, person $i$ will not sit next to person $i+1\text{,}$ as there will be at least one seat between them.

Example 9.4.5.

Determine the number of ways that $n$ identical dollars can be distributed to $k$ boys and $l$ girls, such that every girl gets at least one dollar (but the same restriction does not hold for boys).

First, borrow 1 dollar from each boy, and distribute the resulting $n+k$ dollars such that everyone gets at least 1 dollar. Then, the girls will all get at least 1 dollar, and the boys will have at least 0 dollars. Then, the number of ways to do this is,

\begin{equation*} \binom{n+k-1}{k+l-1} \end{equation*}

Example 9.4.6.

A group of $k$ earls are playing cards. Originally, they each have $p$ pennies. At the end of the game, they count how much money they have. They do not borrow from each other, so that each cannot lose more than his $p$ pennies. How many possible results are there?

This is equivalent to determining the number of ways to distribute the $kp$ total pennies ($p$ pennies per earl and $k$ earls) among $k$ earls. Thus, there are,

\begin{equation*} \binom{kp + k - 1}{k-1} \end{equation*}

ways.