30 thoughts on “Identical objects, distinct groups, no group empty”
5 students are selected to participate in 3 diff competitions such that at least one participates in each competition,in how many diff ways can all the students participate in the competition?
Let the competitions be A, B, C. Now either the students can be split as (3, 1, 1) or as (2, 2, 1).
For the (3, 1, 1) case, we can select the group to have 3 in 3 ways, and select the students in it in 5C2 = 10 ways and send the other two to the remaining two competitions in 2 ways. 3 * 10 * 2 = 60 ways.
For the (2, 2, 1) case we can select the group to have 1 in 3 ways, send a student there in 5 ways, and divide the other 4 into 2 and 2 in 4C2 = 6 ways. So 3 * 5 * 6 = 90 ways.
{There could be other approaches, but they would yield the same answer. Set theory and the inclusion-exclusion principle for example (possibly I will do a post on that at a later date)}
Hi just a clarification for this solution… when you say ‘we can select the group to have 3 in 3 ways’ you mean the group can be arranged as (1,1,3 or 3,1,1 or 1,3,1) right because each arrangement would mean a different type of group
Also can you please explain this statement a little more ‘select the students in it in 5C2 = 10 ways and send the other two to the remaining two competitions in 2 ways. 3 * 10 * 2 = 60 ways” as I am unable to gain clarity on it
Let the groups be ABC and the people be VWXYZ. Now for the 3 1 1 case, the three people can be in X or Y or Z. (3 cases) Consider first case – 3 in X. Now which three? Choose any 3 out of 5 (5C3 cases). Consider one of these, say VWX in A. Then Y and Z can go to B and C in 2! = 2 ways.
In general, do try to work it out for yourself! It is more difficult than directly asking the answer, but it will ensure you both understand and remember 🙂
regards
J
can this 3*10*2 be understood as equivalent to 5*4*3 as we have 5 ways for the first time and 4 while second time and 3 while third time, is this approach correct too, or I am coincidentally getting the same answer?
I don’t think that works – but I am not sure what you have done….not sure where yuo got 5 ways?
regards
J
what i did is..
We have 5 ppl and 3 competitions, so for first competition , we have 5 options, then for second we have 4 options (in the sense 4 ppl), then 3 making 5*4*3..
I am afraid that is not correct – all the 5 people need to participate in the competitions.
regards
J
The set theory solution that you suggested above will be:
3^5 – {(competition A empty)OR(competition B empty)OR(competition C empty)}
=3^5 – [{(2^5)*3} -(1*3) +0]
=150
Are the following sums based on the partitioning logic ? If you could you explain them ? I can’t seem to differentiate them and get ’em into my head :-
1)7 different objects must be divided among 3 people.In how many ways can this be done if one or tow of them can get no objects?
(a)15120 (b)2187 (c)3003 (d)792
(2)7 different objects must be divided among 3 people.In how many ways can this be done if at least one out of them must get no objects?
(a)381 (b)36 (c)84 (d)174
(3)7 different objects must be divided among 3 people.In how many ways can this be done if at least one of them gets exactly one object?
(a)2484 (b)1176 (c)729 (d)None of these
No Vaibhav. The partitioning logic is for identical objects only, and all these problems have distinct objects.
The first one is straightforward – effectively there is no condition and so each of the objects can go to any of the 3 people so 3*3*3*3*3*3*3 = 2187 ways.
In the second, we can select 1 person to get no objects in 3 ways. Suppose we choose A, then we can distribute the objects to the other two B and C as above in 2^7 = 128 ways. Out of these, note that there is one case where B also gets nothing and one where C also gets nothing these will be counted again in B’s and C’s list respectively). The same thing can be done for B as the first person chosen to be empty-handed and for C giving us 128 * 3 = 384 ways. Now the three cases where two are empty-handed have been counted twice and hence we will subtract them to get 381.
Similarly you can try the third – first give A one object and distribute the other objects to B and C, find out common cases which are double counted and subtract them…
My approach let there are three people A, B and C. Lets consider a case when A gets singke object i.e 7C1 ways rest 6 objects can be distributed by 2^6 ways i.e. total no of ways = 7*64=448
But there are cases when other than A ie B or C may also get one object which could be possible in 7C1*6C1 ways and would be counted twice . Hence answer should be 3*( 448-42) =1218. Please tell me is it right or wrong?
I think it is correct. Logic seems fine, didn’t check the calculations 🙂
regards
J
This is correct 1218
hi, can you explain how those cases will be counted twice?
@appy Can you explain why 7C1*6C1 has been subtracted? The objects are distinct. So the cases where after giving single object to A; B or C also gets one object would be counted as separate. Please clarify.
Hi, why didn’t we considered 8*8*8 ways of three person getting 7 objects and one choice of not getting any.. ?
Sir, I had a query about the question Ratish posted. Here is my approach :-
Let us assume the the 5 students to be identical. Now, 5 students to be distributed to 3 competitions. Now using the logic in the fish – man case, we place 1 student in each competition. Now using the n+r – 1 c r-1 formula… we get 4 c 2 = 6 ways. But actually students are distinct, so we can arrange them in 6 x 5! ways = 720… this is way off from your answer of 150, so what is wrong in my logic ?
Vaibhav, consider a case like 3 1 1 distribution. When you are doing 5!, you are arranging all 5 students. However, you ought not to be arranging the three who are in the same group, correct? Hence your answer is significantly larger than it should be!
Because the students are distinct (something which I realise every day, as a teacher!) and hence must be divided, without arrangement, into groups. If arrangement within the groups is important, then it becomes the “rings and fingers” style case and there multiplying by 5! would be appropriate.
Note that people are always assumed distinct unless otherwise specified. Let “every child is special” be your watchword in these cases!
I m first selecting 1 object from 7 then out of six by formula of grouping 6 objects into two groups of 3 objects each =7c1*(6c2/(2!*(3!)^2)=70 .Is this correct ?
We are not arranging the groups among themselves. If we want to give 6 distinct toys to 4 children we do 4^6 not 4^6 * 4! right? Why would we arrange the children among themselves?
regards
J
Sir, why isn’t the number of ways in which groups can be selected taken into consideration here, as we did is past examples? Why isn’t it- 3*7C1*6C3*3C3?
By now there are so many variants of the question above that I am not sure which one you are referring to 🙂 Could you write the specific question and we will discuss that independently…
regards
J
Thank you sir..!
Was not on the same page…!
Your posts are amazing..! Thanks.!
CAT-holics 
5 students are selected to participate in 3 diff competitions such that at least one participates in each competition,in how many diff ways can all the students participate in the competition?
Let the competitions be A, B, C. Now either the students can be split as (3, 1, 1) or as (2, 2, 1).
For the (3, 1, 1) case, we can select the group to have 3 in 3 ways, and select the students in it in 5C2 = 10 ways and send the other two to the remaining two competitions in 2 ways. 3 * 10 * 2 = 60 ways.
For the (2, 2, 1) case we can select the group to have 1 in 3 ways, send a student there in 5 ways, and divide the other 4 into 2 and 2 in 4C2 = 6 ways. So 3 * 5 * 6 = 90 ways.
{There could be other approaches, but they would yield the same answer. Set theory and the inclusion-exclusion principle for example (possibly I will do a post on that at a later date)}
Hence total = 60 + 90 = 150 ways.
regards
J
Hi just a clarification for this solution… when you say ‘we can select the group to have 3 in 3 ways’ you mean the group can be arranged as (1,1,3 or 3,1,1 or 1,3,1) right because each arrangement would mean a different type of group
Also can you please explain this statement a little more ‘select the students in it in 5C2 = 10 ways and send the other two to the remaining two competitions in 2 ways. 3 * 10 * 2 = 60 ways” as I am unable to gain clarity on it
Let the groups be ABC and the people be VWXYZ. Now for the 3 1 1 case, the three people can be in X or Y or Z. (3 cases) Consider first case – 3 in X. Now which three? Choose any 3 out of 5 (5C3 cases). Consider one of these, say VWX in A. Then Y and Z can go to B and C in 2! = 2 ways.
In general, do try to work it out for yourself! It is more difficult than directly asking the answer, but it will ensure you both understand and remember 🙂
regards
J
can this 3*10*2 be understood as equivalent to 5*4*3 as we have 5 ways for the first time and 4 while second time and 3 while third time, is this approach correct too, or I am coincidentally getting the same answer?
I don’t think that works – but I am not sure what you have done….not sure where yuo got 5 ways?
regards
J
what i did is..
We have 5 ppl and 3 competitions, so for first competition , we have 5 options, then for second we have 4 options (in the sense 4 ppl), then 3 making 5*4*3..
I am afraid that is not correct – all the 5 people need to participate in the competitions.
regards
J
The set theory solution that you suggested above will be:
3^5 – {(competition A empty)OR(competition B empty)OR(competition C empty)}
=3^5 – [{(2^5)*3} -(1*3) +0]
=150
Exactly!
regards
J
Are the following sums based on the partitioning logic ? If you could you explain them ? I can’t seem to differentiate them and get ’em into my head :-
1)7 different objects must be divided among 3 people.In how many ways can this be done if one or tow of them can get no objects?
(a)15120 (b)2187 (c)3003 (d)792
(2)7 different objects must be divided among 3 people.In how many ways can this be done if at least one out of them must get no objects?
(a)381 (b)36 (c)84 (d)174
(3)7 different objects must be divided among 3 people.In how many ways can this be done if at least one of them gets exactly one object?
(a)2484 (b)1176 (c)729 (d)None of these
No Vaibhav. The partitioning logic is for identical objects only, and all these problems have distinct objects.
The first one is straightforward – effectively there is no condition and so each of the objects can go to any of the 3 people so 3*3*3*3*3*3*3 = 2187 ways.
In the second, we can select 1 person to get no objects in 3 ways. Suppose we choose A, then we can distribute the objects to the other two B and C as above in 2^7 = 128 ways. Out of these, note that there is one case where B also gets nothing and one where C also gets nothing these will be counted again in B’s and C’s list respectively). The same thing can be done for B as the first person chosen to be empty-handed and for C giving us 128 * 3 = 384 ways. Now the three cases where two are empty-handed have been counted twice and hence we will subtract them to get 381.
Similarly you can try the third – first give A one object and distribute the other objects to B and C, find out common cases which are double counted and subtract them…
What should be the answer for 3rd one?
My approach let there are three people A, B and C. Lets consider a case when A gets singke object i.e 7C1 ways rest 6 objects can be distributed by 2^6 ways i.e. total no of ways = 7*64=448
But there are cases when other than A ie B or C may also get one object which could be possible in 7C1*6C1 ways and would be counted twice . Hence answer should be 3*( 448-42) =1218. Please tell me is it right or wrong?
I think it is correct. Logic seems fine, didn’t check the calculations 🙂
regards
J
This is correct 1218
hi, can you explain how those cases will be counted twice?
@appy Can you explain why 7C1*6C1 has been subtracted? The objects are distinct. So the cases where after giving single object to A; B or C also gets one object would be counted as separate. Please clarify.
Hi, why didn’t we considered 8*8*8 ways of three person getting 7 objects and one choice of not getting any.. ?
do these type of questions come in CAT?
Sir, I had a query about the question Ratish posted. Here is my approach :-
Let us assume the the 5 students to be identical. Now, 5 students to be distributed to 3 competitions. Now using the logic in the fish – man case, we place 1 student in each competition. Now using the n+r – 1 c r-1 formula… we get 4 c 2 = 6 ways. But actually students are distinct, so we can arrange them in 6 x 5! ways = 720… this is way off from your answer of 150, so what is wrong in my logic ?
Vaibhav, consider a case like 3 1 1 distribution. When you are doing 5!, you are arranging all 5 students. However, you ought not to be arranging the three who are in the same group, correct? Hence your answer is significantly larger than it should be!
But then, why cant it be solved by the fish-man logic? Identical students, distinct competitions?
Because the students are distinct (something which I realise every day, as a teacher!) and hence must be divided, without arrangement, into groups. If arrangement within the groups is important, then it becomes the “rings and fingers” style case and there multiplying by 5! would be appropriate.
Note that people are always assumed distinct unless otherwise specified. Let “every child is special” be your watchword in these cases!
regards
J
Divide 7 different objects into groups of 3,3,1 .
I m first selecting 1 object from 7 then out of six by formula of grouping 6 objects into two groups of 3 objects each =7c1*(6c2/(2!*(3!)^2)=70 .Is this correct ?
Aditya, it is correct if the groups are identical. If they are not, then it will be 140.
regards
J
Sir, if the groups are not identical..why will we not multiply 140 by 3…(for cases 1,3,3 ; 3,1,3 ; 3,3,1)..?
We are not arranging the groups among themselves. If we want to give 6 distinct toys to 4 children we do 4^6 not 4^6 * 4! right? Why would we arrange the children among themselves?
regards
J
Sir, why isn’t the number of ways in which groups can be selected taken into consideration here, as we did is past examples? Why isn’t it- 3*7C1*6C3*3C3?
By now there are so many variants of the question above that I am not sure which one you are referring to 🙂 Could you write the specific question and we will discuss that independently…
regards
J
Thank you sir..!
Was not on the same page…!
Your posts are amazing..! Thanks.!