Statistics problem dealing with Combinatorics

1. Aug 28, 2014

tiger2030

1. The problem statement, all variables and given/known data

How many ways can 5 different letters be posted in 3 boxes, if
any number of letters can be posted in all of the three post boxes?

2. Relevant equations
Order of the letters being put into the box doesn't matter, only which letter or letters ends up in which box. A box can have 0 letters in the box

3. The attempt at a solution
I tried to break it into cases:

Case 1:
All five letters go into one box
(5C5)(3C1)=1*3=3
Reasoning:Out of the five letters I choose five. Out of the three boxes, I am choosing one to put these letters.

Case 2:
Four letters go into one box, remaining letter into one box
(5C4)(3C1)(1C1)(2C1)=5*3*1*2=30
Reasoning:Out of the five letters I choose four. Out of the three boxes, I am choosing one to put these letters. Then I am choosing the remaining letter. Out of the two boxes left, I am choosing one to put the letter in.

Case 3:
Three letters go into one box, remaining two letters go into one box
(5C3)(3C1)(2C2)(2C1)=10*3*1*2=60
Reasoning:Out of the five letters I choose three. Out of the three boxes, I am choosing one to put these letters. Then I am choosing the remaining letters. Out of the two boxes left, I am choosing one to put the letters in.

Case 4:
Three letters go into one box, one letter goes into second box, one letter goes into third box
(5C3)(3C1)(2C1)(2C1)=10*3*2*2=120
Reasoning:Out of the five letters I choose three. Out of the three boxes, I am choosing one to put these letters. Then I am choosing one of the remaining letters. Out of the two boxes left, I am choosing one to put this letter in.

Case 5:
Two letters go into one box, two letters go into second box, one letter goes into third box
(5C2)(3C1)(3C2)(2C1)=10*3*3*2=180
Reasoning:Out of the five letters I choose two. Out of the three boxes, I am choosing one to put these letters. Then I am choosing two of the remaining letters. Out of the two boxes left, I am choosing one to put these letters in.

Total possibilities equal to the sum of all the cases
3+30+60+120+180=393

2. Aug 28, 2014

HallsofIvy

It looks to me like it should be much more straight forward than that. Since each mail box will hold none or all 5 letters, there are 3 choices for in which mail box to put each of the 5 letters.

3. Aug 28, 2014

Ray Vickson

I get a total of $3^5 = 243.$

Think about "trinonmial coefficients" and the "trinomial expansion".

4. Aug 28, 2014

Orodruin

Staff Emeritus
Is this the full problem statement? Including your attempt, we have had three out of three people interpreting the question differently ... The letters being different suggests to me that Ray's interpretation would be the correct one, but it is unclear what a "way" of posting the letters is. (Is "Posting 3 letters in box 1, 2 in box 2 and 0 in box 3" a "way" or is "Posting letter 1 in box 3, letter 2 in box 1, letter 3 in box 1, letter 4 in box 2, and letter 5 in box 3" a "way"? The letters being different would suggest the second interpretation.)

5. Aug 28, 2014

haruspex

I agree with Ray's interpretation and result. Your interpretation seems to be the same, but you've gone about it in an unnecessarily complicated way and made some mistakes.
You've double counted.
Another double count. E.g. letters A&B in box 1, then C&D in box 2, also arises as C&D in box 2, then A&B in box 1.
Eliminating the double counts gets you to 243.

6. Aug 29, 2014

tiger2030

I know see that 35 would have been the easiest way to go about this because letter 1 has three options, letter 2 has three options, and so on, giving you 3*3*3*3*3.

For the way I did it, in order to make the result number come out I know that I have an extra 'x2' or '(2C1)' factor in case 4 and case 5. From your last example I see how I am getting repeats but I am still not seeing why.

My reasoning for case 5 was pick two of the five letters[(5C2)] and put those into one of the three boxes[(3C1)]. Then I would still have to pick two of the three remaining letters[(3C2)] and put them into one of the two remaining boxes[(2C1)]. Then the last letter is put into the remaining box.

I guess what I am asking is where did that reasoning falter?

Thanks for the help so far.

7. Aug 29, 2014

Orodruin

Staff Emeritus
It does not matter which box you pick first and which you pick second. Thus, you have (3C2) = 3 possibilities of picking two boxes in which to put two letters, not (3C1)*(2C1) = 6.
For a combination where you first picked letter A and B and picked box 1 to put them in and C and D and picked box 2 to put them in, there is also an equivalent combination where you first pick letters C and D and pick box 2 to put them in and then pick letters A and B and pick box 1 to put them in. This is where your double counting comes from.

8. Aug 29, 2014

Ray Vickson

The number of different ways to put $n$ distinct items into 3 boxes---with $k_i \geq 0$ items in box $i$ and $k_1 + k_2 + k_3 = n$---is the trinomial coefficient
$${n \choose k_1, k_2, k_3} \equiv \frac{n!}{k_1! k_2! k_3!}$$
Let $K_n = \{(k_1,k_2, k_3) \in \mathbf{Z}^3: k_1 + k_2 + k_3 = n \}$. The answer you want is
$$N = \sum_{K_n} {n \choose k_1, k_2, k_3}.$$
One way to evaluate $N$ is to note the trinomial expansion
$$(x_1 + x_2 + x_3)^n = \sum_{K_n} {n \choose k_1, k_2, k_3} x_1^{k_1} x_2^{k_2} x_3^{k_3}$$
Setting $x_1 = x_2 = x_3 = 1$ gives $N = 3^n$.