28 thoughts on “Distinct Objects in Identical Groups”

I am getting 46 as the answer.1st (5,0,0) in 1 way.then (4,1,0) in 5!/4!=5 ways.next (3,2,0) in 5!/3!*2!=10 and(2,2,1) in 5!/2!*2!=30ways.so total 46 ways.please let us know if I am doing it correctly.

Firstly, 2, 2, 1 needs to be again divided by 2 (see the cases above marked with a comment in brown!) since the groups with 2 and 2 will be identical. So it will be 15 and not 30 ways for that distribution.

Secondly, there will be a case of 3, 1, 1, which you have not taken into account. This will yield 10 more cases. Taking these two corrections into account, the result will be 41.

@catcracker – In one of your earlier posts u had mentioned… Number of ways of distributing n distinct objects into r identical groups… is given by (r^n) / r!
though i got the answer 41 in above case… the answer using the above formula come to 40.5
plz guide me…. on this topic

it is a very important question… in almost every book this formula is given for dividing distinct objects in identical groups…. but no book has mentioned any examples….

Actually, I had not mentioned this, as I have only talked of distinct groups till last week. The formula you mentioned would work, but one would have to take the greatest integer function for that if I recall correctly – [243/6] = 41 or in the earlier problem [2187/6] = 365. There is some correction required for multiple empty groups, I think. It is somewhat prone to confusion and hence risky to apply (as you found out!), so I am going by the slow and steady method of enumeration. I’ll check if I can find any further clarification on that formula and will comment if I do.

I generally prefer going by the underlying logic in most cases – CAT rarely asks a direct formula-based question and to solve the twists one has to understand the basic principles. Here, for example, CAT might ask “In how many ways can we distribute 7 distinct objects into 3 identical groups such that no two groups contain the same number of elements?”

Yes , definitely sir.. this method of listing is far better…
I have one more doubt sir… the mutual fund problem u had presented before us… which u solved graphically…can u please explain the method in detail…

The idea was of a minimax situation. Let me give you a discrete example. Suppose I say, you have 3 choices. If you pick A, you will either win $10 or $100 (equal probability of winning or losing). If you pick B you will either win $40 or $50. If you pick C you will win either win $ 20 or $80. Now the average (expected) earning from A and C are much higher than that from B. If you were to pick on that criterion alone, you would pick A.

However, if you are risk-averse and wish to maximise your GUARANTEED return, then you will pick B as you are guaranteed at least 40 which is higher than the other “worst-case” scenarios.

In the given problem, Shabnam can consider investing partly in A and partly in B – if she does, the red line shows her worst-case returns. As you see from the graph, the maximum case is at a point which is higher than the returns she would get from investing in C (which is a fixed value) and therefore to maximise her GUARANTEED returns she should choose that mix of investment.

There were other ways to do the problem, the graphical approach was just a different way of looking at it ðŸ™‚ It becomes like a co-ordinate geometry problem in this approach.

sir i wanted to ask that if in this case of ” distinct objects in identical groupos” we get a number jahan possibilities ko enumerate krna posible nhi hai unlike in this case jahan humne cases likhw nd fir evaluate kia.. den what to do??

Aashika, you would not get a problem like that in a CAT. In fact even this one here is slightly beyond what one could expect ðŸ™‚ So don’t worry. They will give something jo manually ho sakta hai, not where you would need esoteric knowledge….

I don’t understand the question. 7 different people to be divided into 3 identical groups? How can the groups be identical? Groups are named identical if the group size is same and some other differentiating factor (like 3 different sections of a school, 3 hobby classes) is not present.

Sanchi, consider one situation where we have 7 people PQRSTUV to be divided into 3 groups A B C. Then PQR in A, ST in B and UV in C is different from ST in A, PQR in B, and UV in C. But if we want to send these people off for a picnic and 3 cars are available, then it doesn’t matter who goes in which car, it only matters who are together. So (PQR), (ST) and (UV) will be only one case instead of 6 cases in the previous example.

Hi J,
While grouping 7 people, say in groups of (4,2,1), are we selecting 4 from 7, then 2 from remaining 3, that effectively give us 7C4 * 3C2. And in case we have identical groups, say (3,3,1) we are selecting 3 from 7, then 3 from 4, that effectively gives us 7C3*4C3/2! (division because we have 2 identical groups).. and so on for each case
Now if we have another situation where we have to divide 6 guys in a groups of (2,2,2) will the case be 6C2*4C2/3! (because we have 4 identical groups)?? am i extending the logic correctly?

Yes. You could also do the first part 6C2 * 4C2 directly as 6! / (2!2!2!) (see the post on distinct objects in distinct groups) so the answer here would be 6! / (2!2!2!3!)

So if you want to divide let’s say 30 people into 6 groups of 5, then it could be done in 30! / [(5!)^6 * 6! ] ways

In the given solved example (6,1,0) and (6,0,1) should be two distinct cases right? I am asking this since you’ve considered only (6,1,0) as a case and not the other.

What about a case like distinct objects into distinct groups, for example put ten distinct balls into three different boxes, considering the order in which the balls are put in the boxes.

Hi,
I have a doubt on why the first set that is 7,0,0 is just 1, I get it by logic but based on what we are doing for others, wouldn’t it be 7!/7!2! since we have 2 sets with the same no of balls and they are identical.

Not really. I agree it is confusing, but when we put 0 people in two groups, they are already identical so have not been arranged in the first place. When we put 1 person in each of two groups (as in 5, 1, 1), the two groups end up appearing distinct and hence being arranged among themselves, while they should not be, hence we need to further divide.

Another way to look at it it: when we want (7, 0, 0), we just do 7C7 to put all into one group. Similarly when we want (5, 1, 1) we do 7C5 to choose the 5 in a single group. However, in this approach, the case of (3, 3, 1) becomes confusing, requiring another extra level of care!

I know that isn’t a very coherent explanation, but it is the best I can manage. Maybe some other reader will be able to offer one that is easier to grasp! On the bright side, this is very very unlikely to come in any of the exams (identical groups, till now, have only come in the sub-case where all the groups are the same size; for example, “distribute 12 books among 3 people such that each receives 4 books”). So, don’t worry if you are uncomfortable with this. It is included here more for completeness!

I have a question with regard to this line: “When we put 1 person in each of two groups (as in 5, 1, 1), the two groups end up appearing distinct and hence being arranged among themselves, while they should not be, hence we need to further divide”.

Following this logic, we might as well divide by 3! because, when we put 5 persons in the first group, the first group becomes distinct as well.

I feel (but do not understand why) my assertion is not correct. Can you please help me explain why?

Regards,
Alex

The first group with 5 is indeed distinct. We divide by 2 because the other two are NOT in fact distinct. When we say &!/5!1!1! we are treating all 3 as distinct, but in fact the 2 with 1 are not distinct.

regards
J

Hi catcracker!

I do not get why in (5,1,1) “the other two are NOT in fact distinct”.

A group of 5 is distinct. The first group of 1 is also distinct (because one unique object placed there makes the whole group distinct). The second group of 1 is distinct as well (for the same reason).

Hence, all the 3 groups are distinct and therefore arranged. To get rid of the order, we need to divide by 3!.

What is my mistake?

Best regards,
Alexander

They are only distinct after placing the objects. They are identical before putting anything in. Both are “group with one vacancy”

I am getting 46 as the answer.1st (5,0,0) in 1 way.then (4,1,0) in 5!/4!=5 ways.next (3,2,0) in 5!/3!*2!=10 and(2,2,1) in 5!/2!*2!=30ways.so total 46 ways.please let us know if I am doing it correctly.

IN (2,2,1) it should be 5!/2!2!2! = 15 . see the solution above ..Plus you have not taken a combination 3,1,1 ..

Sharmi – You have made two small mistakes.

Firstly, 2, 2, 1 needs to be again divided by 2 (see the cases above marked with a comment in brown!) since the groups with 2 and 2 will be identical. So it will be 15 and not 30 ways for that distribution.

Secondly, there will be a case of 3, 1, 1, which you have not taken into account. This will yield 10 more cases. Taking these two corrections into account, the result will be 41.

regards

J

oh.yes.my mistake.thanks for pointing out

@catcracker – In one of your earlier posts u had mentioned… Number of ways of distributing n distinct objects into r identical groups… is given by (r^n) / r!

though i got the answer 41 in above case… the answer using the above formula come to 40.5

plz guide me…. on this topic

it is a very important question… in almost every book this formula is given for dividing distinct objects in identical groups…. but no book has mentioned any examples….

Hi Girish,

Actually, I had not mentioned this, as I have only talked of distinct groups till last week. The formula you mentioned would work, but one would have to take the greatest integer function for that if I recall correctly – [243/6] = 41 or in the earlier problem [2187/6] = 365. There is some correction required for multiple empty groups, I think. It is somewhat prone to confusion and hence risky to apply (as you found out!), so I am going by the slow and steady method of enumeration. I’ll check if I can find any further clarification on that formula and will comment if I do.

I generally prefer going by the underlying logic in most cases – CAT rarely asks a direct formula-based question and to solve the twists one has to understand the basic principles. Here, for example, CAT might ask “In how many ways can we distribute 7 distinct objects into 3 identical groups such that no two groups contain the same number of elements?”

regards

J

Yes , definitely sir.. this method of listing is far better…

I have one more doubt sir… the mutual fund problem u had presented before us… which u solved graphically…can u please explain the method in detail…

I assume you are referring to this? https://crackthecat.wordpress.com/2013/01/24/weighted-averages-cat-scan/

The idea was of a minimax situation. Let me give you a discrete example. Suppose I say, you have 3 choices. If you pick A, you will either win $10 or $100 (equal probability of winning or losing). If you pick B you will either win $40 or $50. If you pick C you will win either win $ 20 or $80. Now the average (expected) earning from A and C are much higher than that from B. If you were to pick on that criterion alone, you would pick A.

However, if you are risk-averse and wish to maximise your GUARANTEED return, then you will pick B as you are guaranteed at least 40 which is higher than the other “worst-case” scenarios.

In the given problem, Shabnam can consider investing partly in A and partly in B – if she does, the red line shows her worst-case returns. As you see from the graph, the maximum case is at a point which is higher than the returns she would get from investing in C (which is a fixed value) and therefore to maximise her GUARANTEED returns she should choose that mix of investment.

There were other ways to do the problem, the graphical approach was just a different way of looking at it ðŸ™‚ It becomes like a co-ordinate geometry problem in this approach.

regards

J

Thank u sir…. ðŸ™‚

sir i wanted to ask that if in this case of ” distinct objects in identical groupos” we get a number jahan possibilities ko enumerate krna posible nhi hai unlike in this case jahan humne cases likhw nd fir evaluate kia.. den what to do??

Aashika, you would not get a problem like that in a CAT. In fact even this one here is slightly beyond what one could expect ðŸ™‚ So don’t worry. They will give something jo manually ho sakta hai, not where you would need esoteric knowledge….

regards

J

I don’t understand the question. 7 different people to be divided into 3 identical groups? How can the groups be identical? Groups are named identical if the group size is same and some other differentiating factor (like 3 different sections of a school, 3 hobby classes) is not present.

Sanchi, consider one situation where we have 7 people PQRSTUV to be divided into 3 groups A B C. Then PQR in A, ST in B and UV in C is different from ST in A, PQR in B, and UV in C. But if we want to send these people off for a picnic and 3 cars are available, then it doesn’t matter who goes in which car, it only matters who are together. So (PQR), (ST) and (UV) will be only one case instead of 6 cases in the previous example.

regards

J

Hi J,

While grouping 7 people, say in groups of (4,2,1), are we selecting 4 from 7, then 2 from remaining 3, that effectively give us 7C4 * 3C2. And in case we have identical groups, say (3,3,1) we are selecting 3 from 7, then 3 from 4, that effectively gives us 7C3*4C3/2! (division because we have 2 identical groups).. and so on for each case

Now if we have another situation where we have to divide 6 guys in a groups of (2,2,2) will the case be 6C2*4C2/3! (because we have 4 identical groups)?? am i extending the logic correctly?

Yes. You could also do the first part 6C2 * 4C2 directly as 6! / (2!2!2!)

(see the post on distinct objects in distinct groups)so the answer here would be 6! / (2!2!2!3!)So if you want to divide let’s say 30 people into 6 groups of 5, then it could be done in 30! / [(5!)^6 * 6! ] ways

regards

J

In the given solved example (6,1,0) and (6,0,1) should be two distinct cases right? I am asking this since you’ve considered only (6,1,0) as a case and not the other.

The groups are identical, so the order won’t matter…

regards

J

What about a case like distinct objects into distinct groups, for example divide ten distinct balls into three different boxes?

This will just be 3^10 as discussed in an earlier post

regards

J

What about a case like distinct objects into distinct groups, for example put ten distinct balls into three different boxes, considering the order in which the balls are put in the boxes.

If the order of balls going into boxes is important then we can use the rings-and-fingers logic discussed in this post:

https://cat100percentile.com/2013/05/23/rings-and-fingers/

regards

J

Hi,

I have a doubt on why the first set that is 7,0,0 is just 1, I get it by logic but based on what we are doing for others, wouldn’t it be 7!/7!2! since we have 2 sets with the same no of balls and they are identical.

Not really. I agree it is confusing, but when we put 0 people in two groups, they are already identical so have not been arranged in the first place. When we put 1 person in each of two groups (as in 5, 1, 1), the two groups end up appearing distinct and hence being arranged among themselves, while they should not be, hence we need to further divide.

Another way to look at it it: when we want (7, 0, 0), we just do 7C7 to put all into one group. Similarly when we want (5, 1, 1) we do 7C5 to choose the 5 in a single group. However, in this approach, the case of (3, 3, 1) becomes confusing, requiring another extra level of care!

I know that isn’t a very coherent explanation, but it is the best I can manage. Maybe some other reader will be able to offer one that is easier to grasp! On the bright side, this is very very unlikely to come in any of the exams (identical groups, till now, have only come in the sub-case where all the groups are the same size; for example, “distribute 12 books among 3 people such that each receives 4 books”). So, don’t worry if you are uncomfortable with this. It is included here more for completeness!

regards

J

Hi catcracker!

I have a question with regard to this line: “When we put 1 person in each of two groups (as in 5, 1, 1), the two groups end up appearing distinct and hence being arranged among themselves, while they should not be, hence we need to further divide”.

Following this logic, we might as well divide by 3! because, when we put 5 persons in the first group, the first group becomes distinct as well.

I feel (but do not understand why) my assertion is not correct. Can you please help me explain why?

Regards,

Alex

The first group with 5 is indeed distinct. We divide by 2 because the other two are NOT in fact distinct. When we say &!/5!1!1! we are treating all 3 as distinct, but in fact the 2 with 1 are not distinct.

regards

J

Hi catcracker!

I do not get why in (5,1,1) “the other two are NOT in fact distinct”.

A group of 5 is distinct. The first group of 1 is also distinct (because one unique object placed there makes the whole group distinct). The second group of 1 is distinct as well (for the same reason).

Hence, all the 3 groups are distinct and therefore arranged. To get rid of the order, we need to divide by 3!.

What is my mistake?

Best regards,

Alexander

They are only distinct after placing the objects. They are identical before putting anything in. Both are “group with one vacancy”

regards

J