In the previous section, we saw a relation between number of permutations and number of combinations of n objects taken r at a time.
• 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’.
• Let us see another example in which the number of objects inside the combinations is 3. It can be written in 4 steps:
1. Consider five objects A, B, C, D and E
• We want to make combinations of these five objects, taking 3 at a time.
• Some of the possible combinations are: ABC, BCD, ADE, . . .
2. We want to know how many such combinations are possible.
• In other words, we want to calculate ${}^4 C_3$.
3. Consider the combination ABC. In this combination, the order is not important.
• But the three objects A, B and C can be arranged among themselves in 3! ways.
◼ So we can write:
Number of combinations × 3! = Number of permutations
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 get the same relation in all three examples.
• We can confirm that the relation between ${}^n C_r$ and ${}^n P_r$ is: ${}^n C_r~ × ~ r!~=~{}^n P_r$
• Now, we already have the formula: ${}^n P_r~=~\frac{n!}{(n-r)!}$
• So the relation becomes: ${}^n C_r~ × ~ r!~=~\frac{n!}{(n-r)!}$
• This can be rearranged as: ${}^n C_r~=~\frac{n!}{r!~ × ~(n-r)!}$
• Thus we get the formula for ${}^n C_r$
Let us see some important results related to the above formula
Result 1:
This can be written in 3 steps:
1. ${}^n C_r$ is the number of combinations when n objects are taken r at a time.
• Now, instead of r, what if we take all the n objects?
2. Using the formula, we can write:
${}^n C_r~=~{}^n C_n~=~\frac{n!}{n!~ × ~(n-n)!}~=~\frac{n!}{n!~ × ~0!}~=~\frac{n!}{n!~ × ~1}~=~1$
3. That means, if we take all objects at a time, there is only one combination possible.
Result 2:
This can be written in 3 steps:
1. ${}^n C_r$ is the number of combinations when n objects are taken r at a time.
• Now, instead of r, what if we take zero objects?
2. Using the formula, we can write:
${}^n C_r~=~{}^n C_0~=~\frac{n!}{0!~ × ~(n-0)!}~=~\frac{n!}{1~ × ~n!}~=~1$
3. Taking zero objects means that, we are leaving behind all the n objects.
All the n objects can have a combination of only 1.
Result 3:
This can be written in 2 steps:
1. Based on the results 1 and 2, we can say that r can be equal to both zero or n.
2. So we can write the formula as:
${}^n C_r~=~\frac{n!}{r!~ × ~(n-r)!}~~0 \le r \le n$
Result 5:
This can be written in 4 steps:
1. We have the formula: ${}^n C_r~=~\frac{n!}{r!~ × ~(n-r)!}$
Here, r objects are taken.
2. What if we take (n-r) objects?
We get: ${}^n C_{n-r}~=~\frac{n!}{(n-r)!~ × ~[n-(n-r)]!}~=~\frac{n!}{(n-r)!~ × ~[n-n+r]!}~=~\frac{n!}{(n-r)!~ × ~r!}$
$\Rightarrow {}^n C_{n-r}~=~\frac{n!}{(n-r)!~ × ~r!}$
3. Now compare the expressions in (1) and (2)
• We see that, the numerators and denominators are the same.
• Thus we get: ${}^n C_r~=~{}^n C_{n-r}$
4. So we can write:
♦ We may take r objects at a time.
♦ Or we may reject r objects and take the remaining (n-r) objects at a time.
♦ In both cases, the number of combinations will be the same.
Result 6:
This result is based on the previous result 5. It can be written in 3 steps:
1. Suppose that, ${}^n C_a~=~{}^n C_b$
2. Then there are two possibilities:
• Possibility (i): a = b
• Possibility (ii) Based on result 5, we can write: b = n-a
♦ This gives: n = a+b
3. So we can write:
If ${}^n C_a~=~{}^n C_b$, then a = b or n = a+b
Result 7:
${}^n C_r~+~{}^n C_{r-1}~=~{}^{n+1} C_r$
• Proof can be written in 3 steps:
1. The LHS can be simplified as:
$\begin{array}{ll}
{}&{}^n C_r~+~{}^n C_{r-1}&{}={}&\frac{n!}{r!~ × ~(n-r)!}~+~\frac{n!}{(r-1)!~ × ~[n-(r-1)]!}&{} \\
{}&{}&{}={}& \frac{n!}{r!~ × ~(n-r)!}~+~\frac{n!}{(r-1)!~ × ~(n-r+1)!}&{} \\
{}&{}&{}={}& \frac{n!}{r(r-1)!~ × ~(n-r)!}~+~\frac{n!}{(r-1)!~ ×
~(n-r+1)!}&{\color {green}{\because ~r!=r(r-1)!}} \\
{}&{}&{}={}& \frac{n!}{r(r-1)!~ × ~(n-r)!}~+~\frac{n!}{(r-1)!~ ×
~(n-r+1)(n-r)!}&{\color {green}{\because ~(n-r+1)!=(n-r+1)(n-r)!}} \\
{}&{}&{}={}& \frac{n!}{(r-1)!~ × ~(n-r)!}~\left[\frac{1}{r}~+~\frac{1}{(n-r+1)}\right]&{} \\
{}&{}&{}={}& \frac{n!}{(r-1)!~ × ~(n-r)!}~\left[\frac{n-r+1+r}{r(n-r+1)}\right]&{} \\
{}&{}&{}={}& \frac{n!}{(r-1)!~ × ~(n-r)!}~\left[\frac{n+1}{r(n-r+1)}\right]&{} \\
{}&{}&{}={}& \frac{[(n+1)n!]}{[r(r-1)!]~[(n-r+1)(n-r)!]}&{} \\
{}&{}&{}={}& \frac{[(n+1)!]}{[r(r-1)!]~[(n-r+1)(n-r)!]}&{\color {green}{\because ~(n+1)n!=(n+1)!}} \\
{}&{}&{}={}& \frac{[(n+1)!]}{[r!]~[(n-r+1)(n-r)!]}&{\color {green}{\because ~r(r-1)!=r!}} \\
{}&{}&{}={}& \frac{[(n+1)!]}{[r!]~[(n-r+1)!]}&{\color {green}{\because ~(n-r+1)(n-r)!=(n-r+1)!}} \\
{}&{}&{}={}& \frac{(n+1)!}{r!~(n+1-r)!}&{\color {green}{\because ~(n-r+1)(n-r)!=(n-r+1)!}} \\
\end{array}$
2. The RHS can be simplified as:
$\begin{array}{ll}
{}&{}^{n+1} C_r&{}={}&\frac{(n+1)!}{r![(n+1)-r]!}&{} \\
{}&{}&{}={}&\frac{(n+1)!}{r!(n+1-r)!}&{} \\
\end{array}$
3. Thus we get: LHS = RHS
Now we will see some solved examples
Solved example 7.18
If ${}^n C_9~=~{}^n C_8$, then find ${}^n C_17$
Solution:
1. We have result 6:
If ${}^n C_a~=~{}^n C_b$, then a = b or n = a+b
2. In our present case, 9 cannot be equal to 8.
• So the only option is: n = 9+8
• Thus we get: n = 17
3. So ${}^n C_{17}~=~{}^{17} C_{17} ~=~1$ (using result 1)
Solved example 7.19
A committee of 3 persons is to be constituted from a group of 2 men and 3 women. In how many ways can this be done? How many of these committees would consist of 1 man and 2 women?
Solution:
Part (i):
1. Let the two men be denoted as M1 and M2
• Let the three women be denoted as W1, W2 and W3
2. Then one possibility is: M1, W1, W3
• Another possibility is: W2, M2, M1
• There are many possibilities like this.
3. But in this problem, order is not important because all three members will be having equal status. We need not denote them as M1, M2 etc.,
• It is a combination of 5 people taking 3 at a time.
4. So we get:
Number of combinations = ${}^5 C_3~=~\frac{5!}{3! (5-3)!}~=~10$
Part (ii):
1. Out of the 10 possible combinations, some of them will have exactly one man and two women. We want to find the number of such combinations.
2. Assigning units:
• In fig.7.8 below, the first box is considered as one unit. It is for men.
• The remaining two boxes together are considered as one unit. It is for women.
 |
| Fig.7.8 |
• The first unit can be filled in 2C1 = 2 ways
• The second unit can be filled in 3C2 = 3 ways
4. So by applying the multiplication principle, the two units can be filled in (2 × 3)= 6 ways
5. We can write:
Out of the 10 combinations, 6 will have exactly one man and two women.
Solved example 7.20
What is the number of ways of choosing 4 cards from a pack of 52 playing cards? In how many of these
(i) four cards are of the same suit,
(ii) four cards belong to four different suits,
(iii) are face cards,
(iv) two are red cards and two are black cards,
(v) cards are of the same color?
Solution:
• A pack of 52 playing cards will have four suits. Each suit will have 13 cards. Details can be seen here.
• We can write:
4 cards can be chosen in 52C4 = 270725 ways.
Part (i): Four cards are of the same suit
1. Let us assume that, all 4 cards are diamonds.
Four diamond cards can be chosen from 13 diamond cards in 13C4 ways.
2. Let us assume that, all 4 cards are clubs.
Four clubs cards can be chosen from 13 clubs cards in 13C4 ways.
3. Let us assume that, all 4 cards are spades.
Four spades cards can be chosen from 13 spades cards in 13C4 ways.
4. Let us assume that, all 4 cards are hearts.
Four hearts cards can be chosen from 13 hearts cards in 13C4 ways.
5. So the total number of ways = 4 × 13C4 ways = 2860
Part (ii): Four cards belong to four different suits
1. Imagine that there are four boxes.
2. The first box can be filled in = 52 ways
• If the selected one is a diamond, no diamond should be used for filling the remaining 3 boxes.
♦ So there will be only (52-13) = 39 cards available to fill the second box.
• If the selected one is a club, no club should be used for filling the remaining 3 boxes.
♦ So there will be only (52-13) = 39 cards available to fill the second box.
• If the selected one is a spade, no spade should be used for filling the remaining 3 boxes.
♦ So there will be only (52-13) = 39 cards available to fill the second box.
• If the selected one is a heart, no heart should be used for filling the remaining 3 boxes.
♦ So there will be only (52-13) = 39 cards available to fill the second box.
3. The second box can be filled in = 39 ways
• If the selected one is a diamond, no diamond should be used for filling the remaining 2 boxes.
♦ So there will be only (39-13) = 26 cards available to fill the third box.
• If the selected one is a club, no club should be used for filling the remaining 2 boxes.
♦ So there will be only (39-13) = 26 cards available to fill the third box.
• If the selected one is a spade, no club should be used for filling the remaining 2 boxes.
♦ So there will be only (39-13) = 26 cards available to fill the third box.
• If the selected one is a heart, no heart should be used for filling the remaining 2 boxes.
♦ So there will be only (39-13) = 26 cards available to fill the third box.
4. Based on this, we can write:
♦ Box 1 can be filled in 52 ways
♦ Box 2 can be filled in 39 ways
♦ Box 3 can be filled in 26 ways
♦ Box 4 can be filled in 13 ways
5. So the total number of permutations is: (52 × 39 × 26 × 13) = 685464 ways.
• But order is not important. The four cards can be arranged among themselves in 4! ways.
• Thus the number of combinations = $\frac{685464}{4!}$ = 28561 ways.
Alternate method:
1. Imagine that there are four boxes.
2. Let us fill the first box with a diamond card.
• A diamond card can be chosen from 13 diamond cards in 13 ways.
3. Let us fill the second box with a spade cards.
• A spade card can be chosen from 13 spade cards in 13 ways.
4. Let us fill the third box with a club cards.
• A club card can be chosen from 13 club cards in 13 ways.
5. Let us fill the fourth box with a heart cards.
• A heart card can be chosen from 13 heart cards in ways.
6. So by applying the multiplication principle,
the four boxes can be filled in (13 × 13 × 13 × 13) = 28561 ways
• This example helps us to understand the relation between permutation and combination.
Part (iii): four cards are face cards
1. In any one suit, there are 3 face cards. So in the whole pack, there will be (4 × 3) = 12 cards
2. From these 12 cards, four cards can be selected in 12C4 = 495 ways
Part (iv): two are red cards and two are black cards
1. Imagine that there are four boxes.
♦ First two boxes can be considered as one unit.
♦ The remaining two boxes can be considered as another unit.
This is shown in fig.7.9 below:
 |
| Fig.7.9 |
2. Let us fill the first unit with red cards.
♦ There are 26 red cards.
♦ So the two boxes of the first unit can be filled in 26C2 ways
3. Let us fill the second unit with black cards.
♦ There are 26 black cards.
♦ So the two boxes of the second unit can be filled in 26C2 ways
4. So by applying the multiplication principle, the two units can be filled in
(26C2 × 26C2) = 105625 ways
Part (v): cards are of the same color ?
1. Imagine that there are four boxes.
2. First let us fill all the four boxes with red cards.
♦ There are 26 red cards. So 4 cards can be chosen in 26C4 ways.
3. Next let us fill all the four boxes with black cards.
♦ There are 26 black cards. So 4 cards can be chosen in 26C4 ways.
4. So in total, there will be (2 × 26C4) = 29900 ways.
The link below gives some more solved examples:
We have completed a discussion on combinations. In the next section, we will see some miscellaneous examples.
Copyright©2022 Higher secondary mathematics.blogspot.com
No comments:
Post a Comment