# In how many ways can five letters be posted in 4 boxes?

Question : In how many ways can 5 letters be posted in 4 boxes?

Answer 1: We take a letter. It can be posted in any of the 4 boxes. Similarly, next letter can be posted in 4 ways, and so on. Total number = $4^5$.

Answer 2: Among the total number of positions of 5 letters and 3 dividers (between 4 boxes), positions of 3 dividers can selected in $\binom{8}{3}$ ways.

Which one is correct (I think the first one)? Why is the other one wrong and how does it differ from the right answer in logical/combinatorial perspective?

-
The trouble with using the second approach is that the specification of the problem does not require some post-box to receive any letters at all. There is no tidy way to make the count of how the letters are to be arranged if any box can receive any number of letters from zero to all five. In your first approach, you can think of it as assigning a destination box to each letter; that automatically counts all the possible arrangements. This avoids missing possibilities, as we see from, $4^5 > _8C_3$ . –  RecklessReckoner Apr 23 '13 at 18:22
May be the distinguishability of the letters gives the two results... –  user2204800 Apr 24 '13 at 8:45

The way to understand this problem (and decide which answer is correct) is to ask what you are counting exactly. If all the letters are distinct then the first answer sounds better because it counts arrangements that only differ by where each particular letter goes.

The second answer appears to make the letters and the dividers distinct, as well as counting as distinct the cases where two letters appear in a box in a different order. These seem to be counting different things.

If you modify the second answer to place 3 identical dividers in a row of 5 identical letters, (choose 3 from 6 ‘gaps’), then it works fine. But those ‘identical’s are not correct (are they?).

If we tried to ‘correct’ the second solution by multiplying by rearrangements (to take into account all possible rearrangements of letters, say) we would discover that some rearrangements would be introduced that weren’t supposed to be distinct. No, the second approach is wrong-headed: it counts the wrong things and it gets very complicated when you try to correct it.

So the answer is “the first solution is correct”. This applies when the letters are distinct and the boxes are distinct.

-
May be the distinguishability of the letters gives the two results... –  user2204800 Apr 24 '13 at 8:46
${6\choose3}=20$ is only correct if the letters are identical and if no gap can be chosen twice (which means that only the first and the last mailbox can be empty). If gaps can be chosen twice (i.e. any mailbox can be empty), then the correct answer (for identical letters) is indeed ${8\choose3}=56$, as the question suggests. –  Ilmari Karonen Jan 11 '14 at 1:54
@IlmariKaronen Yes, your first point is correct, of course. How do you derive $\binom{8}{3}$? Did you mean to only allow us to choose a gap twice? –  Steve Powell Apr 8 at 11:22
@StevePowell: The same way the OP did: mark 5 + 3 = 8 spots on a table, choose 3 of them to put dividers in, and fill the remaining 5 with letters. You now have 5 letters on the table, separated into 4 groups (some of which may be empty) by the 3 dividers. Proving that each choice of 3 spots for the dividers generates a distinct 4-tuple of group sizes, and that all 4-tuples summing up to 5 can be so generated, is a common exercise for an introductory combinatorics class. –  Ilmari Karonen Apr 8 at 11:31

Having looked at this again, the answer $4^5$ is correct for distinguishable letters (and boxes, as Steve Powell has said).

If we have something like form letters (all copies identical - we presume the mailboxes are still distinguishable) , then we do get your answers. I counted them this way:

Five identical letters going into four boxes will leave anywhere from zero to three boxes open.

For no open boxes, there is one more letter than boxes, which can go in one of 4 places.

With one open box, that can be one of 4. One letter goes into each of the three occupied boxes, so we only need to consider arrangements of two "excess" letters among those three boxes. Either the two remaining letters go in one of the three boxes ($\left(\begin{array}{cc}3\\1\end{array}\right) =$ 3 ways), or one letter goes into each of two out of the three boxes ( $\left(\begin{array}{cc}3\\2\end{array}\right) =$3 ways). So this case produces $4 \cdot (3 + 3) =$ 24 arrangements.

Two open boxes can occur in $\left(\begin{array}{cc}4\\2\end{array}\right) =$ 6 ways. There are three "excess" letters to distribute among the two occupied boxes: either all go into one ( $\left(\begin{array}{cc}2\\1\end{array}\right) =$ 2 ways) or two go into one and the remaining third excess letter into the other box (also $\left(\begin{array}{cc}2\\1\end{array}\right) =$ 2 ways). This case produces $6 \cdot (2 + 2) =$ 24 arrangements.

Finally, having three open boxes means that one of 4 possible occupied boxes gets all of the letters.

So, all told, there are only 56 arrangements for the identical letters. (I guess I find partioning easier to check, though having done so, I now see what you are describing in your second case. So distinguishability makes a huge difference in answering this question.)

-
An easier way to get 56 is as $\binom83$, just as the question describes it. You start at the first box, and perform a sequence of five "put a letter in the current box" and three "move to the next box" in some order. Each order gives rise to a different distribution, and each distribution can be made. –  Henning Makholm Jan 11 '14 at 5:03