Using Combinations to Make Groups
BY KARISHMA, VERITAS PREP
Let’s continue our discussion on combinations here. From the previous posts, we understand that combination is nothing but “selection.” Today we will discuss a concept that confuses a lot of people. It is similar to making committees (that we saw last week), but with a difference. Read the two questions given below:
Question 1: In how many ways can one divide 12 different chocolate bars equally among four boys?
Question 2: In how many ways can one divide 12 different chocolate bars into four stacks of 3 bars each?Do you think the 2 questions are the same and the answer would be the same in both cases? After all, once you divide the chocolates into four stacks, it doesn’t matter who you give them to! Actually, it does! The two questions are different. Since the chocolates are different, the four stacks will be different. So how you distribute the stacks among the 4 boys is material.
Let us take a simple case first.
Say, there are just 4 chocolate bars: A, B, C, D
We want to split them in 2 groups containing 2 chocolate bars each. There are two ways of doing this:
Method IIn group 1, we can put any 2 chocolate bars and we will put the remaining 2 chocolate bars in group 2.
We could put them in two distinct groups in the following 6 ways:
1. Group1: A and B, Group2: C and D
2. Group1: C and D, Group2: A and B (If you notice, this is the same as above. The only difference is that A and B is group 2 and C and D is group 1 here)
3. Group1: A and C, Group2: B and D
4. Group1: B and D, Group2: A and C (This is the same as above. The only difference is that A and C is group 2 and B and D is group 1 here)
5. Group1: A and D, Group2: B and C
6. Group1: B and C, Group2: A and D (Again, this is the same as above. Here, B and C is group 2 and A and D is group 1)
We have to put the four chocolates in two different groups, group 1 and group 2. It is similar to distributing 4 chocolates between 2 boys equally. Boy 1 could get (A and B) or (C and D) or (A and C) or (B and D) or (A and D) or (B and C). Boy 2 gets the other 2 chocolates in each case.
Method IIThe two groups can be made in the following three ways:
A and B, C and D
A and C, B and D
A and D, B and C
In this case, the groups are not named/distinct. You have 4 chocolates in front of you and you just split them in 2 groups. (A and B, C and D) is the same as (C and D, A and B). There are a total of 3 ways of doing this i.e. half of the number of ways we saw in method 1. It is logical, isn’t it? You divide the answer you get above by 2! because the two groups are not distinct in this case.
Let’s look at the original two questions now:
Question 1: In how many ways can one divide twelve different chocolate bars equally among four boys?You need to divide 12 chocolate bars among four boys i.e. you have to make four distinct groups. To boy 1, you can give the first chocolate in 12 ways, the second chocolate in 11 ways and the third chocolate in 10 ways. But we don’t want to arrange the chocolates so you can select 3 chocolates for boy 1 in 12*11*10/3! ways (this is equivalent to 12C3 if you follow the formula). Similarly, you can select 3 chocolates for the second boy in 9*8*7/3! ways (i.e. 9C3), for the third boy in 6*5*4/3! ways (i.e. 6C3) and for the fourth boy in 3*2*1/3! ways (i.e. 3C3)
Therefore, you can distribute 12 chocolates among 4 boys equally in (12*11*10/3!) * (9*8*7/3!) * (6*5*4/3!) * (3*2*1/3!) = 12!/(3!*3!*3!*3!) ways
Alternatively, you can visualize putting the 12 chocolates in a row in 12! ways and drawing a line after every three chocolates to demarcate the groups.
OOO l OOO l OOO l OOO
Since the chocolates within the groups are not arranged, we divide 12! by 3! for every group. Since there are 4 groups, number of ways of making 4 distinct groups = 12!/(3!*3!*3!*3!)
Question 2: In how many ways can one divide 12 different chocolate bars into four stacks of 3 bars each?What do you think will the answer be here? Will it be the same as above? No. Here the 4 stacks are not distinct. You need to divide the answer you obtained above by 4! (similar to the simple example with just 4 chocolates we saw above).
In this case, the required number of ways = 12!/(3!*3!*3!*3!*4!)
Since the groups are not distinct here, your answer changes. When the question says that you need to make n groups/bundles/teams that are not distinct, you need to divide by (n!). If the groups/bundles/teams are distinct then you do not divide by (n!).
Let’s look at another question that uses the same concept.
Question 3: 8 friends want to play doubles tennis. In how many different ways can the group be divided to make 4 teams of 2 people each?(A) 420
(B) 2520
(C) 168
(D) 90
(E) 105
Solution: It is quite clear here that the teams are not distinct i.e. we don’t have team 1, team 2 etc. But let’s solve this question by first making team 1, team 2, team 3 and team 4. Later we will adjust the answer.
Out of 8 people, in how many ways can we make team 1? In 8*7/2! ways (i.e. 8C2).
Out of 6 people, in how many ways can we make team 2? In 6*5/2! ways (i.e. 6C2).
Out of 4 people, in how many ways can we make team 3? In 4*3/2! ways (i.e. 4C2).
Out of 2 people, in how many ways can we make team 4? In 2*1/2! ways (i.e. 2C2).
In how many ways can we make the 4 teams? In 8*7*6*5*4*3*2*1/(2!*2!*2!*2!) = 8!/(2!*2!*2!*2!) ways. But here, we have considered the 4 teams to be distinct. Since the teams are not distinct, we will just divide by 4!
We get 8!/(2!*2!*2!*2!*4!) = 105
Answer (E) This question is discussed HERE.
I hope the explanation makes sense. We will continue with Combinatorics in the next post. I told you that once we get into it, it takes a long time to get out of it
In Q 1 - If the question had not mentioned equally, the answer would have been 4^12? - Same as Q1 in topic: Unfair Distributions in Combinatorics - Part 1
a. if r >= 0 n+r-1 C r-1
b. If r > 1 , n-1 C r-1