2
$\begingroup$

I've 'indirectly' studied combinatorics earlier in probability courses, but now it's part of the math course I'm taking. I always thought it was very hard, and well, here I am again...

The problem is, I'm guessing, fairly simple, but I just don't know how to attack it.

There are five letters and three mailboxes. In how many ways can the letters be put into the mailboxes such that at most one box is empty?

By writing out the different distribution alternatives I've come to the conclusion that the answer must be 18, since the allowed combinations are:

  1. 1, 1, 3
  2. 1, 3, 1
  3. 3, 1, 1
  4. 1, 2, 2
  5. 2, 1, 2
  6. 2, 2, 1
  7. 0, 1, 4
  8. 0, 2, 3
  9. 0, 3, 2
  10. 0, 4, 1
  11. 1, 0, 4
  12. 2, 0, 3
  13. 3, 0, 2
  14. 4, 0, 1
  15. 1, 4, 0
  16. 2, 3, 0
  17. 3, 2, 0
  18. 4, 1, 0

I've tried arriving at this answer by more direct calculation, but I can't seem to get it right because I can't really wrap my head around how to formulate it -- for example, if the letters are distributed to boxes 1 1 2 2 3 that, to me, is equivalent to 1 2 1 2 3. Thus, I need to adjust the 'unconditional' calculation $3^5$ -- but how? Can someone please point me in the right direction?

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ The question is a little unclear to me on whether one can tell the difference between each of the 5 letters. Concretely, in case 7, are there 5 possibilities depending on which letter is in the second box, or do you consider all of these equivalent? $\endgroup$ – mdp Sep 9 '13 at 13:25
  • $\begingroup$ @MattPressland I'm not sure I can clarify it further, this is what was given to me. But I would think the letters themselves are not important. $\endgroup$ – hejseb Sep 9 '13 at 13:27
  • $\begingroup$ I think the question is so framed that the letters are distinct. However, the attempt of the OP takes the letters to be same. $\endgroup$ – Vishal Gupta Sep 9 '13 at 13:29
2
$\begingroup$

It appears the mailboxes are distinct, but the letters are not. In that case, (a) one mailbox is empty. You have three ways to pick an empty mailbox and for each you have four ways to distribute the letters for twelve. (b) If no mailbox is empty, you have a stars-and-bars problem with four places to put two bars for six.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Nice, that makes sense and sounds not very complicated. Thanks! $\endgroup$ – hejseb Sep 9 '13 at 13:57
1
$\begingroup$

If the letters, as well as the boxes, are distinguishable from one another, we have the following:

There are $3^5=243$ ways of putting the letters in the boxes without restriction. We have to discount those configurations with two (or more, but this is impossible) empty boxes. There are exactly three, as we have to put all of the letters into one box, and there are three choices of box. So there are $3^5-3=240$ possible configurations with at most one empty box.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.