In how many ways can John send $8$ different pictures to his girlfriend in $5$ identical envelopes if each envelope contains at least one picture?

Question

I have a problem which I seem to be solving incorrectly. Here it goes.

John would like to send 8 different pictures to his girlfriend in 5 equal envelopes. In how many many ways can he send them given that each envelope must have at least one picture?

The solution I came with comes from the rationale that the 8 pictures can be sent into three major different ways:

1. Four pictures in one envelope and one picture in each of the remainder (4 + 1 + 1 + 1 + 1)

• In this case, we would have ${8}\choose{4}$.

2. Three pictures in one envelope, two pictures in another and one picture each of the remainder (3 + 2 + 1 + 1 + 1)

• In this case, we would have ${8}\choose{3}$ $\times$ ${5}\choose{2}$.

3. Two pictures in three of the envelopes and one picture in each of the remainder (2 + 2 + 2 + 1 + 1)

• In this case, we would have ${8}\choose{2}$ $\times$ ${6}\choose{2}$ $\times$ ${4}\choose{2}$.

Overall, we would have ${8}\choose{4}$ $+$ ${8}\choose{3}$ $\times$ ${5}\choose{2}$ $+$ ${8}\choose{2}$ $\times$ ${6}\choose{2}$ $\times$ ${4}\choose{2}$ $= 3150$

However, the answer seems to be $1050$. How come? What is wrong in this rationale?

Can you please help? Thank you very much. All the best.

Answer 1

If you wish to avoid a "division by symmetry" argument like the one that @Joffan uses in his answer, you may instead count the number of outcomes in case 3 in the following way:

Temporarily assume that the pictures have a particular order (e.g. when they were taken).

First, pick what six pictures are used for the envelopes that receive two pictures each. This can be done in $\binom{8}{6}$ ways.

Next, take the "smallest" (as per the order we discussed earlier, e.g. newest) picture and pick which of the remaining five of the designated pictures will be placed in the same envelope as it. Then, take the smallest of those remaining and pick what picture goes with that. Finally, the remaining two pictures will go into their own envelope together.

This gives a total of $\binom{8}{6}\cdot 5\cdot 3$ outcomes in this case (which happens to agree with Joffan's answer of $\binom{8}{2}\cdot\binom{6}{2}\cdot\binom{4}{2}\cdot \frac{1}{6}$)

Answer 2

In your case 3, the three envelopes with 2 pictures in each are interchangeable, so each of these cases is counted $3!=6$ times. Divide this case out by $6$ and you should get your book answer.