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?

Solution 1:

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.)

Solution 2:

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.