In the previous section, we completed a discussion on permutations. In this section, we will see combinations.
Some basics can be written based on an example. It can be written in 5 steps:
1. Consider a group of 3 players: Player A, Player B and Player C.
• We have to pick out a Captain and a Vice-Captain from among those 3 players.
• No player can hold more than one position. Let us see the various possibilities:
• Possibility 1:
♦ Player A is Captain
♦ Player B is Vice-Captain
• Possibility 2:
♦ Player A is Captain
♦ Player C is Vice-Captain
• Possibility 3:
♦ Player B is Captain
♦ Player A is Vice-Captain
• Possibility 4:
♦ Player B is Captain
♦ Player C is Vice-Captain
• Possibility 5:
♦ Player C is Captain
♦ Player A is Vice-Captain
• Possibility 6:
♦ Player C is Captain
♦ Player B is Vice-Captain
• We see that, there are six possibilities. We have seen this type of problems in the previous sections of this chapter. It is the permutation of 3 players taken two at a time.
• It is important to note that:
♦ The permutation with A as Captain and B as Vice-Captain
♦ is different from
♦ The permutation with B as Captain and A as Vice-Captain
• Similarly:
♦ The permutation with C as Captain and B as Vice-Captain
♦ is different from
♦ The permutation with B as Captain and C as Vice-Captain
◼ So each permutation is unique. There are a total of 6 permutations
2. Now consider the same problem, slightly modified:
• There are 3 players: Player A, Player B and Player C. We have to form a 2-member team, by picking out two players from among them. The two players will have equal status. The various possibilities are:
• Possibility 1:
♦ Player A is selected
♦ Player B is selected
• Possibility 2:
♦ Player A is selected
♦ Player C is selected
• Possibility 3:
♦ Player B is selected
♦ Player A is selected
• Possibility 4:
♦ Player B is selected
♦ Player C is selected
• Possibility 5:
♦ Player C is selected
♦ Player A is selected
• Possibility 6:
♦ Player C is selected
♦ Player B is selected
• We see that, there are 6 possibilities. For the time being, let us say that, the six possibilities are the six permutations.
3. Here we note three interesting facts:
• Fact 1
♦ The team with A selected and B selected
♦ is not different from
♦ The team with B selected and A selected
✰ This is because, A and B have equal status in the team.
• Fact 2
♦ The team with B selected and C selected
♦ is not different from
♦ The team with C selected and B selected
✰ This is because, B and C have equal status in the team.
• Fact 3
♦ The team with C selected and A selected
♦ is not different from
♦ The team with A selected and C selected
✰ This is because, A and C have equal status in the team.
4. So we cannot say that each of 6 possibilities is an unique possibility.
• The number of unique possibilities is in fact 3. We can write those unique 3 possibilities:
• Possibility 1:
♦ Player A is selected
♦ Player B is selected
• Possibility 2:
♦ Player B is selected
♦ Player C is selected
• Possibility 3:
♦ Player C is selected
♦ Player A is selected
• We cannot call those possibilities as permutations.
◼ We call them: Combinations of 3 objects taken 2 at a time.
In the present case, there are three unique combinations.
5. Let us write an important point. It can be written in 3 steps:
(i) Order of players in the team is not important
• For example:
♦ Team with player B and Player C
♦ is not different from
♦ Team with player C and Player B
(ii) If we take order also into consideration, it will be a permutation problem
• It will be the arrangement of 3 players taking two at a time.
• We get: ${}^3P_2~=~\frac{3!}{(3-2)!}~=~\frac{3!}{1!}~=~6$
This is the same result that we obtained in (2)
(iii) But we know that, here order is not important. So it is not a permutation problem.
• It is a combination problem. It is the combination of 3 objects taken two at a time.
Let us see another example. It can be written in 5 steps:
1. Seven people are sitting around in a circle as shown in fig.7.7(a) below.
 |
| Fig.7.7 |
Each of them shakes hands with all others. How many hand shakes will be there in total?
2. We are inclined to think in this way:
• The first person will be seeing 6 people. So he will have 6 hand shakes.
• The second person will be seeing 6 people. So he will have 6 hand shakes.
• The third person will be seeing 6 people. So he will have 6 hand shakes.
• So on . . .
• So altogether, there will be (7 × 6) = 42 hand shakes.
3. But is this answer correct?
Let us analyze fig.b:
• Consider the chord 1-2
♦ Person 1 shaking hands with Person 2
♦ is same as
♦ Person 2 shaking hands with Person 1
♦ It is indicated by the chord 1-2
• Consider the chord 4-7
♦ Person 4 shaking hands with Person 7
♦ is same as
♦ Person 7 shaking hands with Person 4
♦ It is indicated by the chord 4-7
◼ In this way, the number of chords will give the actual number of hand shakes.
4. Let us count the number of chords in fig.b
• There are 6 green chords radiating out from 1
• There are 5 magenta chords radiating out from 2
♦ (green is already counted)
• There are 4 cyan chords radiating out from 3
♦ (green and magenta are already counted)
• There are 3 yellow chords radiating out from 4
♦ (green, magenta and cyan are already counted)
• There are 2 orange chords radiating out from 5
♦ (green, magenta, cyan and yellow are already counted)
• There is 1 brown chord radiating out from 6
♦ (green, magenta, cyan, yellow and orange are already counted)
• All chords radiating out from 7 are already counted.
◼ So we get:
Number of chords = 6+5+4+3+2+1 = 21
◼ Thus we can write:
There are 21 hand shakes.
5. Let us write an important point. It can be written in steps:
(i) Order of hand shakes is not important
• For example:
♦ Person 3 shaking hands with Person 7
♦ is not different from
♦ Person 7 shaking hands with Person 3
(ii) If we take order also into consideration, it will be a permutation problem
• It will be the arrangement of 7 people taking two at a time.
• We get: ${}^7P_2~=~\frac{7!}{(7-2)!}~=~\frac{7!}{5!}~=~42$
This is the same result that we obtained in (2)
(iii) But we know that, hand shakes do not have order. So it is not a permutation problem.
• It is a combination problem. It is the combination of 7 objects taken two at a time.
• Consider the number of combinations of n objects taken r at a time.
♦ Let us denote it as: ${}^n C_r$
◼ Based on the first example that we saw above, we can write: ${}^3 C_2~=~3$
♦ Recall that ${}^3 P_2~=~6$
♦ Is there any relationship between ${}^3 P_2$ and ${}^3 C_2$ ?
◼ Based on the second example that we saw above, we can write: ${}^7 C_2~=~21$
♦ Recall that ${}^7 P_2~=~42$
♦ Is there any relationship between ${}^7 P_2$ and ${}^7 C_2$ ?
◼ In general, is there any relationship between ${}^n P_r$ and ${}^n C_r$ ?
To find the relationship, we can analyze the first example. It can be written in 4 steps:
1. In example 1, we obtained three combinations: AB, BC and AC
2. Consider the combination AB
• There are two members, A and B
• Those two members can be arranged among themselves in 2! ways.
♦ 2! ways is (2 × 1) = 2 ways.
♦ They are: AB and BA
3. In this way, inside each combination, there are 2 permutations.
• So the three combinations together will give (3 × 2) = 6 permutations
• Recall that, ${}^3 P_2$ is also 6
4. Now we get an idea about the relation:
♦ Number of combinations of n objects taking r at a time $\left({}^n C_r \right)$
♦ Multiplied by
♦ Number of permutations inside each combination $(r!)$
♦ Will give
♦ The number of permutations of n objects taking r at a time $\left({}^n P_r \right)$
• So we can write: ${}^n C_r~ × ~ r!~=~{}^n P_r$
Let us analyze the second example and see whether we get the same relation. It can be written in 4 steps:
1. In example 2, we obtained 21 combinations: 1-2, 1-3, 1-4, . . .
2. Consider the combination 1-2
• There are two people, 1 and 2
• Those two people can be arranged among themselves in 2! ways.
♦ 2! ways is (2 × 1) = 2 ways.
♦ They are: 1-2 and 2-1
3. In this way, inside each combination, there are 2 permutations.
• So the 21 combinations together will give (21 × 2) = 42 permutations
• Recall that, ${}^7 P_2$ is also 42
4. Now we get the same idea as before:
♦ Number of combinations of n objects taking r at a time $\left({}^n C_r \right)$
♦ Multiplied by
♦ Number of permutations inside each combination $(r!)$
♦ Will give
♦ The number of permutations of n objects taking r at a time $\left({}^n P_r \right)$
• So here also, we can write: ${}^n C_r~ × ~ r!~=~{}^n P_r$
• We analyzed two examples. In both of those examples, we obtained the same result.
• In both of those examples, the number of objects inside the combinations were ‘2’.
• In the next section, we will see another example in which the number of objects inside the combinations is 3.
No comments:
Post a Comment