Permutation and Combination problem

  • Thread starter Sam Morse
  • Start date
  • #1
15
0

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
 
Last edited:

Answers and Replies

  • #2
34,458
10,572
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.
 
  • #3
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
33,735
5,541
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.
 
  • #4
rcgldr
Homework Helper
8,696
528
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:
  • #5
15
0
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 ....
 
  • #6
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
33,735
5,541
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.
 
  • #7
15
0
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 ...
 
  • #8
34,458
10,572
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.

Sam Morse said:
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.
 
  • #9
15
0
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 ....
 
  • #10
34,458
10,572
Don't forget the case(s) (1,4,0).
 
  • #11
rcgldr
Homework Helper
8,696
528
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.
 
Last edited:
  • #12
473
13
Sam Morse said:
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
 
  • #13
473
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.
 
  • #14
15
0
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 ....
 
  • #15
473
13
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.
 

Related Threads on Permutation and Combination problem

  • Last Post
Replies
2
Views
1K
Replies
2
Views
2K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
5
Views
6K
  • Last Post
Replies
6
Views
17K
Replies
3
Views
827
Replies
1
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
3
Views
1K
Top