Ways to give gems to pirates (w/ restrictions)

Question

3. Given $X=15$ gold pieces and $Y=5$ pirates, find the number of ways to distribute the gold to the pirates with the requirement that each pirate must receive at least one gold piece.

4. Instead of gold pieces, suppose the $Y=5$ pirates are dividing up $X=8$ rare gems, each with its own unique and bloody history, so that the pirates care which gems they get. How many ways are there to distribute the gems so that each pirate receives a gem?

Let's say in #3, instead of there being distinct pirates, there are the same pirates. If there were distinct pirates, the solution would be $\binom{14}{4}$, from finding number of non-negative integer solutions in $a+b+c+d+e=10$.

If each pirate was the same, then the only different step would be to restrict the equation so that $a\le b\le c\le d\le e$. How would I find out the number of solutions given this restriction?

For #4, I don't know where I'm overcounting and how to fix it. My method is to choose an initial 5 gems, taking account that they are distinct: $\binom{8}{5}5!$. Then I multiply this by the number of ways to distribute the remaining 3 gems among 5 pirates: $5^3$, giving a final solution of $5^3\binom{8}{5}5!$.

But this would mean that giving Gem 1, 2, 3, and 4 to pirate 1 is different from giving him Gem 2, 1, 3, and 4. This is one case which I counted as $4!$, where it is actually 1. How do I fix this?

Answer 1

Imagine instead of five pirates, you had two. You could use the Principal of Inclusion-Exclusion (PIE) as follows:

The total number of ways to distribute eight gems to two pirates: Take each gem, choose a pirate, and give it to him/her. Unfortunately, this includes the possibility of giving all the gems to one of the two pirates. We must exclude (subtract) these possibilities:

\begin{align} \text{Give a gem to any pirate}: & & 2^8\\ \text{Subtract the ways to give gems to only one pirate} & &- {2 \choose 1} \cdot 1^8 \end{align}

---

Now imagine you have three pirates. We use the same method:

\begin{align} \text{Give a gem to any pirate}: & & 3^8\\ \text{Subtract the ways to give gems to only two pirates} & &- {3 \choose 2} \cdot 2^8 \\ \text{Add the ways to give gems to only one pirate} & & +{3 \choose 1} \cdot 1^8 \end{align}

The common way to think about the Principal of Inclusion-Exclusion is to imagine a Venn Diagram. Each of the three sets could be pirates A, B, or C. When we subtract the ways to only select two pirates, we subtract too much. Included in the count of ways to give gems to only pirates (A, B) or pirates (A, C) is the possibility that we give all the gems to pirate A. We don't want to count this, but we subtracted it twice. We must add it back in once.

This pattern of plus, minus, plus, minus, plus is the heart of PIE. With a bit of algebra, the pattern gives the answer for five pirates.

Answer 2

In #3, if the pirates were given to be indistinguishable, you are trying to calculate $p_5(15)$, the number of ways to partition $15$ into $5$ positive parts. The recurrence relation for restricted partition numbers is $p_k(n) = p_k(n − k) + p_{k−1}(n − 1)$ with $p_0(0)=1$ and otherwise entries at or below $0$ are $0$. Or you can let an online calculator do the work and tell you that $p_5(15)=30$.

In #4, as you are assuming again that the pirates are distinguishable, you are trying to find the number of surjective mappings with a domain of eight gems and a codomain of five pirates. The solution to this is $5!\{{8\atop5}\}=120\cdot1050=126000$ where the expression in the brackets is a Stirling number of the second kind (which counts the number of ways to partition a set with eight elements into five non-empty equivalence classes).