Sunday, September 28, 2008

Groupings and Distributions

I have been itching to write this particular article containing higher order fundamentals of permutation and combination. Although CAT 2007/ CAT 2008 aspirants may take a little time to digest this article, the article will clear a lot of doubts in this area. This particular area of grouping and distribution has been my bugaboo for many years until recently when I sat down and unraveled one thread of the mystery after another; the joys of discovering at leisure. Please do not fail to ask me any question that occurs to you after reading this article.

Number of ways of grouping dissimilar things

How would you divide seven different objects in two groups of four and three? Simple. You select four things out of those seven and three will be left behind. Or you can select three things out of those seven and four will be left behind. The number of ways you can accomplish this is 7C4 or 7C3. Now, how would you divide these seven different objects in three groups of one, two and four? Again, you can begin by choosing four things out of these seven, then two things out of the remaining three. The number of ways you can do this is 7C4 × 3C2. Therefore, to divide things into groups, you keep on selecting groups, except for the last group which will be automatically formed.

So how would you divide seven different things into groups of three, three and one?

Your answer would be to take our three things first, then three things next, i.e. 7C3 × 4C3 = 140, and your answer would be WRONG!

Why is your answer wrong? Is there anything wrong with the method? No. Only that you need to take some extra precautions when you are making equal groups. There are slight changes to be observed when you divide some number of things into equal groups.

Let’s start small. According to the method above, in how many ways can you divide 4 different things (say a, b, c and d) into two groups having two things each? Your answer would be to select two things out of the four and two would be left behind, i.e. 4C2 = 6. But are there really 6 ways?

Given below are shown the number of ways we can divide four things, a, b, c and d, into two groups of two:

CAT 2007 CAT 2008 mba 2008 XAT 2008 permutation and combination

You can keep trying if you want to, but there are only 3 ways of dividing the four things into two groups of two.

Where did the rest of 3 ways calculated through 4C2 = 6 disappear?

The answer is that they got merged. When you selected two things out of the four, the things selected were ab, ac, ad, bc, bd, and cd. But the last three groups are already formed when you select the first three groups, i.e. when you select ab, you automatically get cd. When you select ac, you automatically get bd, and so on.

Let’s do it again. According to the method above, in how many ways can you divide 6 different things (say a, b, c, d, e and f) into three groups having two things each? Your answer would be to select two things out of those six and then select two things from the remaining four so that two would be left behind, i.e. 6C2 × 4C2 = 90. But are there really 90 ways?

The table below shows the number of ways you can divide six different things into three groups of two each:

CAT 2007 CAT 2008 MBA 2008 XAT 2008 permutation and combination


Example: How would you divide 5 distinct objects into groups of 2, 2 and 1?

Answer: The single object can be chosen in 5C1 = 5 ways. The rest of the 4 objects can be divided into two equal groups in 3 ways. Therefore, the number of ways = 5 × 3 = 15.

Note that the answer by our first method will be 5C1 × 4C2 = 30 ways. This answer is incorrect.

Number of ways of grouping similar things

In how many ways can you divide five similar objects (say a, a, a, a, a) into three different groups? When we make groups of similar objects, the only way we can differentiate two different ways of grouping is by differentiating between groups when they have different size (number of objects). Therefore, in case of similar objects, the number of different ways we can group them is the number of different sizes of groups that we can make. Let’s see how many groupings of different sizes we can make for 5 similar objects.

cat permutation and combination

DISTRIBUTION

After you have made groups of some objects, you might want to distribute these groups in various places. For example, after you made groups of some toffees, you might want to distribute these groups among some children. Or, after dividing some number of balls into groups, you might want to distribute these groups into boxes. Just as the objects that we group can be similar or dissimilar, so can the places that we assign these groups to be similar or dissimilar. While distributing groups, we need to keep one rule in mind:

cat

Now let’s solve an all-encompassing example on what we have learnt.

Question: In how many ways can you put 5 balls in 3 boxes if

I. the boxes are similar and the balls are similar.
II. the boxes are different but the balls are similar.
III. the boxes are similar but the balls are different.
IV.
the boxes are different and the balls are different.

Answer: Sums up everything, doesn’t it? Well, here we go:

Case I: the boxes are similar and the balls are similar

cat

Case II: the boxes are different but the balls are similar

cat

cat

Case III: the boxes are similar but the balls are different

cat

Case IV: the boxes are different and the balls are different

cat

No comments: