Statistics problem dealing with Combinatorics

  • Thread starter tiger2030
  • Start date
  • #1
22
0

Homework Statement



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?

Homework 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


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

If this is not correct, please help to guide me to the correct answer, not simply provide the answer with the work. Thank you for any help.
 

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,847
966
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
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,722

Homework Statement



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?

Homework 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


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

If this is not correct, please help to guide me to the correct answer, not simply provide the answer with the work. Thank you for any help.

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

Think about "trinonmial coefficients" and the "trinomial expansion".
 
  • #4
Orodruin
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
Gold Member
17,387
7,276

Homework Statement



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?

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
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
37,148
7,273
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?

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


The Attempt at a Solution


I tried to break it into cases:
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.
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.
You've double counted.
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.
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
22
0
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
Orodruin
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
Gold Member
17,387
7,276
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.

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
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,722
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.

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
[tex] {n \choose k_1, k_2, k_3} \equiv \frac{n!}{k_1! k_2! k_3!} [/tex]
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
[tex] N = \sum_{K_n} {n \choose k_1, k_2, k_3}.[/tex]
One way to evaluate ##N## is to note the trinomial expansion
[tex] (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} [/tex]
Setting ##x_1 = x_2 = x_3 = 1## gives ##N = 3^n##.
 

Related Threads on Statistics problem dealing with Combinatorics

Replies
1
Views
1K
Replies
0
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
2
Views
886
Replies
3
Views
1K
  • Last Post
Replies
3
Views
1K
Top