Permutation and Combination problem

[Sam Morse]

Homework Statement

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 ...

Homework Equations

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

 

[mfb]

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.

 

[haruspex]

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.

Agreed.

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.

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.

 

[rcgldr]

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.

 

[Sam Morse]

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 ...

 

[haruspex]

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.

 

[Sam Morse]

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 ...

 

[mfb]

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.

You are right, that is even better.

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?

I don't see an easy way to use your first part in a correct solution. It is possible, but it gets messy.

 

[Sam Morse]

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.

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 ...

 

[mfb]

Don't forget the case(s) (1,4,0).

 

[rcgldr]

As a check, by using brute force method of counting all possible outcomes.

The possible set is (2,3,0)

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

How did you get 90.

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.

 

[Joffan]

How did you get 90.

as mentioned, brute force...

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

 

[Joffan]

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.

 

[Sam Morse]

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.

Please elaborate it a bit ...

 

[Joffan]

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.