1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Statistics problem dealing with Combinatorics

  1. Aug 28, 2014 #1
    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

    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.
     
  2. jcsd
  3. Aug 28, 2014 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  4. Aug 28, 2014 #3

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

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

    Think about "trinonmial coefficients" and the "trinomial expansion".
     
  5. Aug 28, 2014 #4

    Orodruin

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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.)
     
  6. Aug 28, 2014 #5

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
  7. Aug 29, 2014 #6
    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.
     
  8. Aug 29, 2014 #7

    Orodruin

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  9. Aug 29, 2014 #8

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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##.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Statistics problem dealing with Combinatorics
  1. Combinatorics problem (Replies: 2)

  2. Combinatorics problems (Replies: 8)

Loading...