1. Limited time only! Sign up for a free 30min personal 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!

Permutation and Combination problem

  1. Mar 8, 2013 #1
    1. The problem statement, all variables and given/known data

    The total number of ways in which 5 balls of different colours can be distributed among 3 persons so that each person gets at least one ball is ...

    2. Relevant equations



    3. The attempt at a solution

    I began by finding the number of ways of distributing 5 balls among 3 people --->

    1) Number of ways of selecting 3 balls out of 5 is 10
    2) Number of ways of arranging the 3 balls among 3 people is 6.
    Hence total number of ways = 60

    Now, the remaining 2 balls have to be distributed among 5 people ---->

    1) both the balls can be given to one man or can be distributed
    2) if both the balls are given to a single man, then total ways = 3
    3) if one ball is given to one of the three, then total ways = 6.
    Hence total number of ways = 6+3 = 9

    So, in my view, the answer should be 60+9 = 69.
    But the answer is 150 ... far more than my answer.

    I don't want to know a new method because a lot are available on the internet. Please let me know what's wrong with my approach ...

    Thanks in advance for any help
     
    Last edited: Mar 8, 2013
  2. jcsd
  3. Mar 8, 2013 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    You cannot add two independent things like that. Each distribution of all 5 balls would have to pick one out of those 60 options and afterwards one out of the 9 options. Your approach would give you 60*9, not 60+9 options. BUT: This would count several possible distributions twice.

    I think it is easier to drop the requirement "each person gets at least one ball" first, and consider the special cases "one person does not get a ball" and "two do not get a ball" afterwards.
     
  4. Mar 8, 2013 #3

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Agreed.
    No, I think it's easier to break it down the counts of balls much as in the OP: each gets a ball, so it's only a question of how the remaining two are given out: both to one person or to two different people. The mistake is worrying about the colours at all before breaking it down that way.
     
  5. Mar 8, 2013 #4

    rcgldr

    User Avatar
    Homework Helper

    As a check, by using brute force method of counting all possible outcomes. There are 5 balls that can go to any of 3 people. That's 3^5 = 243 total possiblities. Of the 243, 3 of these include all the balls going to exactly 1 person, and 90 of these include all of the balls going to exactly 2 persons, leaving 150 going to 3 persons, so 150 is the correct answer.

    I think we're waiting for your next attempt at an answer using normal methods.
     
    Last edited: Mar 8, 2013
  6. Mar 8, 2013 #5
    I have understood the whole thing you all want to say and I am going to attempt it once more. But I am still not getting why my approach doesn't hit the point...

    As mfb replied that it's 60*9, I agree with that but how does it count outcomes twice? please explain it ....
     
  7. Mar 9, 2013 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Suppose one person ends up with a green ball and ared ball. In your scheme, there are two ways that could happen. The red ball might be allocated as one of the first three and the green later, or the other way around.
     
  8. Mar 9, 2013 #7
    Ya, you are right ... thanks for helping me figure out the error. I believe first part of the solution is all right ... and the second part has an error as you pointed. But how can it be corrected? Also I have found a similar question like that and again the same problem. First you please let me know how do I do it this way then I am going to post the next one. Thanks once again ...
     
  9. Mar 9, 2013 #8

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    You are right, that is even better.

    I don't see an easy way to use your first part in a correct solution. It is possible, but it gets messy.
     
  10. Mar 10, 2013 #9
    When I calculated for the case when all balls go to only 2 people --->

    The possible set is (2,3,0)

    So, Applying combinations 5C2 * 3C3 = 10
    also, the elements of the set can be arranged among themselves in 6 ways therefore my answer turns out 6*10 = 60 . How did you get 90 ....
     
  11. Mar 10, 2013 #10

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Don't forget the case(s) (1,4,0).
     
  12. Mar 10, 2013 #11

    rcgldr

    User Avatar
    Homework Helper

    and as posted above, (1,4,0).

    as mentioned, brute force. I used an archaic but high level interactive / programming languaged called APL to generate all 243 possible outcomes as a matrix of 243 by 5 single digit numbers base 3, then "counted" how many of these involved 1, 2, or 3 persons. I could have used a convention programming language, but stuff like this goes pretty fast if you know a language like APL. To give you an idea of the first step in APL, in english, creating the matrix is done with M = transpose (3 3 3 3 3) encode iota 243. "iota 243" generates a list of numbers 0 to 242. "(3 3 3 3 3) encode" encodes the list producing a 5 by 243 matrix base 3, "tranpose" tranposes the matrix into a 243 by 5 matrix.
     
    Last edited: Mar 10, 2013
  13. Mar 15, 2013 #12
    cases where all balls go to exactly two people
    = (select 2 people from 3) * ( (all balls go to two people) - (all balls go just one of the two) )
    = 3 * (2^5 - 2) = 3* 30 = 90
     
  14. Mar 15, 2013 #13
    For you original solution, you will need to break down the (60x3) three-ball case and the (60x6) two two-ball case. There are multiple routes to each solution which means you need to divide the result by the possible ways to achieve each.
     
  15. Mar 24, 2013 #14
    Please elaborate it a bit ....
     
  16. Mar 24, 2013 #15
    In the 60x3 routes to complete the case where one person ends up with three balls, that person has balls of three different colours, eg red, green, blue. However, there are three different routes to get to that, corresponding to which of the three balls was the initial allocation (and the other two being hand out in the second phase). So in fact there are only (60x3)/3 = 60 variations for that case.
     
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: Permutation and Combination problem
Loading...