28 thoughts on “Identical objects, distinct groups, no group empty

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

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

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

    • 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

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

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

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

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

      regards
      J

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

      • 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s