PERMUTATIONS AND COMBINATIONS
Topic 24, Section 2 - Combinations
Factorial representation of combinations
If we have 10 letters abcdefgahij, then we have seen that the number of permutations of them taken 4 at a time, is
10·9·8·7
Say, however, that we do not care about the order. We care only that 4 letters—b, e, g, h, say—have been selected. And it does not matter in which order they appear. The 4! permutations of begh—
begh, egbh, gbeh, hebg, . . .
—are the same combination.
How many combinations, then, are there of 10 things taken 4 at a time?
For each combination, there are 4! permutations. In other words, the numbers of permutations is 4! times the number of combinations. Therefore, the number of combinations is equal to the number of permutations divided by 4!.
| Number of combinations | = | The number of permutations 4! |
| = | 10· 9· 8· 7 1· 2· 3· 4 |
|
| = | 210. | |
This is The number of combinations of 10 distinct things taken 4 at a time. We will denote it by the symbol 10C4.
| 10C4 | = | 10· 9· 8· 7 1· 2· 3· 4 |
Notice: The numerator and denominator have the same number of factors, 4, which is indicated by the lower index. The numerator has 4 factors starting with the upper index and going down, while the denominator is 4
.
| In general, nCk = |  k |
. |
| nCk | = | n(n − 1)(n − 2)· · · to k factors k |
The upper index n indicates the number of distinct things. The lower index k indicates how many of those we are selecting.
Example 1. You have 6 pairs of socks, but on your vaction you will take only 3. In how many different ways could you do that?
Solution. The order in which you take them does not matter.
| 6C3 | = | 6·5·4 1·2·3 |
= | 5·4 | = 20. |
Again, both the numerator and denominator have the number of factors indicated by the lower index, which in this case is 3. The numerator has three factors beginning with the upper index 6 and going down. The denominator is 3.
Example 2. Evaluate 8C6.
| Solution. 8C6 = | 8· 7· 6· 5· 4· 3 1· 2· 3· 4· 5· 6 |
= 28. |
The numerator and denominator will always have common factors.
The number of combinations is always a whole number.
Example 3. Evaluate 8C2.
| Solution. 8C2 = | 8· 7 1· 2 |
= 28. |
We see that 8C2 , the number of ways of selecting 2 things from 8, is equal to 8C6 (Example 2), the number of ways of selecting 8 minus 2, or 6. For, the number of ways of selecting 2, is the same as the number of ways of leaving 6 behind.
Always:
nCk = nCn − k
The bottom indices, k on the left and n − k on the right, together add up to n.
Example 4. Evaluate 12C9.
Solution. It is simpler to evaluate 12C3.
| 12C9 = 12C3 = | 12·11·10 1·2·3 |
= 2·11·10 = 220. |
Example 5. Write out nC3.
| Solution. nC3 = | n(n − 1)(n − 2) 1· 2· 3 |
The 3 factors in the numerator begin with n and go down.
Factorial representation
In terms of factorials, the number of combinations of n distinct things taken k at a time, can be represented as follows:
| nCk = | n (n − k) k |
This is nPk divided by k. Compare line (1) of Section 1.
Notice: In the denominator, n − k and k together equal the numerator n.
Note also the convention that the factorial of the lower index, k, is written in the denominator on the right.
| Example 6. 8C3 = | 8 5 3 |
Again: 5 + 3 in the denominator equals 8 in the numerator.
| Show that this is equal to | 8· 7· 6 1· 2· 3 |
. |
Solution. 5 is a factor of 8, so it will cancel.
| 8 5 3 |
= | 8· 7· 6· 5 5 · 1· 2· 3 |
= | 8· 7· 6 1· 2· 3 |
. |
Example 7. Write each of the following with factorials: 8C6 , 8C2 .
| Solution. 8C6 = | 8 2 6 |
. 8C2 = | 8 6 2 |
But 2 6 is equal to 6 2.
We see again that the number of ways of selecting 6 things from 8, is equal to the number of ways of selecting 2.
8C6 = 8C2
(See Problem 8, below.)
Example 8. Write 8C0 with factorials.
| Solution. 8C0 = | 8 8 0 |
Since 0 = 1, that fraction is equal to 1.
There is only 1 way to take 0 things from 8. This is the same as the number of ways of taking all 8.
Example 9. Write nCk + 1 with factorials.
Solution. Let us look at the factorial form:
| mCj = | m (m − j) j |
The lower factorials are the difference of the indices, m − j, times the lower index, j.
Let us apply this to nC k + 1. The difference of the indices is
n − (k + 1) = n − k − 1
Therefore,
| nCk + 1 = | n (n − k − 1) (k + 1) |
a) Write all the combinations of abcd taken 1 at a time.
To see the answer, pass your mouse over the colored area.
To cover the answer again, click "Refresh" ("Reload").
a, b, c, d.
b) Write their combinations taken 2 at a time.
ab, ac, ad, bc, bd, cd.
c) Write their combinations taken 3 at a time.
abc, abd, acd, bcd.
d) Write their combinations taken 4 at a time.
abcd
Problem 2.
| a) | There are 3 permutations of the letters rpt. Those 3 permutations include how many
combinations of rpt ?
One. |
| b) | rpt is one of the combinations of pqrst taken three at a time. By how much must the 5P3 permutations of pqrst be reduced, in order to have only their 5C3 combinations? By 3!. 5C3 = 5P3/3!. |
* * *
| nCk | = | n(n − 1)(n − 2)· · · to k factors k |
Problem 3. From a class of 12 students, 4 will be chosen to do a job. In how many different ways could that happen?
12C4 = 495. The order in which they are chosen does not matter.
Problem 4. Evaluate the following.
| a) 6C4 | = 15 | b) 5C3 | = 10 | c) 10C2 | = 45 | ||||
| d) 10C8 | = 45 | e) 8C5 | = 56 | f) 8C3 | = 56 | ||||
| g) 4C4 | = 1 | h) 4C0 | = 1 | ||||||
Problem 5.
a) Write out nC4 . Notice how the last factor in the numerator is related to the lower index.
| n(n − 1)(n − 2)(n − 3) 1· 2· 3· 4 |
b) In the numerator of nCk , what will be the last factor? (n − k + 1)
In part a) where k = 4, the last factor is (n − 3), and 3 is 4 − 1. In general then, the last factor will be [n − (k − 1)] = (n − k + 1).
We could also see that by imagining that each of the k factors has the form (n − j). In the first factor, j = 0. And in the kth, j = k − 1.
c) In the numerator of 20Cm , what will be the last factor? (21 − m)
* * *
| nCk = | n (n − k) k |
Problem 6. Write the following with factorials.
| a) uCv | u! (u − v)! v! |
b) 9C3 | 9! 6! 3! |
c) 9C6 | 9! 3! 6! |
| d) 12C11 | 12! 1! 11! |
e) 12C12 | 12! 0! 12! |
f) 12C0 | 12! 12! 0! |
||||||||||
Therefore, what number is 12C0 ? 1
Problem 7. Write the following with factorials.
| a) nCn − k | n! k! (n − k)! |
b) n + 1Ck | (n + 1)! (n − k + 1)! k! |
|
| c) nCk − 1 | n! (n − k + 1)! (k − 1)! |
d) n − 1Ck − 1 | (n − 1)! (n − k)! (k − 1)! |
|
a) In how many ways could you select three of these digits: 1, 2, 3, 4, 5 ?
5C3 = 10
b) In how many ways could you not select two of them?
5C2 = 10
c) Prove: nCk = nCn − k
| nCk = | n! (n − k)! k! |
= | n! k! (n − k)! |
= nCn − k |
The sum of all combinations
What is the sum of all possible combinations of n distinct things? That is, what is the sum of
nC0 + nC1 + nC2 + . . . + nCn?
We will see that it is equal to 2n.
Let us consider a specific case, say all the possible combinations of 5 distinct things: a, b, c, d, e.
There will, for example, be combinations taking 2 of them:
ca, bc, ed, . . .
There will be combinations taking 3:
ace, bae, edb, . . .
There will be one combination with all 5:
dbcea
In each combination, a letter will be included or it will not. In the combination ace: a, c, e, were included; b, d were not.
We can therefore construct a combination as follows. For each of the 5 letters, we will include it or not.
For a, there will be 2 possibilities: yes or no. After that has happened, for b there will be 2 possibilities, and similarly for c, d, e. The total number of possible combinations then is:
2· 2· 2· 2· 2 = 25.
They include the combination in which there are no letters, which is because we have said "no" to each one, and they move on to the combination in which we have said "yes" to every one.
That is,
| 5C0 + 5C1 + 5C2 + 5C3 + 5C4 + 5C5 | = | 25 |
| = | 32. | |
The actual values are as follows:
1 + 5 + 10 + 10 + 5 + 1
(See Pascal's triangle, Topic 24)
There is exactly 1 way, 5C0, in which there are no letters at all;
5 ways in which there is 1;
10 ways in which there are 2;
10 ways in which there are 3;
5 ways in which there are 4;
1 way in which there are 5.
As we have seen, the lower index k of each combinatorial number 5Ck indicates the number of letters in that combination.
The sum of those combinatorial numbers is 25.
The sum of all possible combinations of n distinct things is 2n.
nC0 + nC1 + nC2 + . . . + nCn = 2n.
(Compare Problem 5, Topic 26.)
A binomial distribution
We will now consider any case in which there are exactly two possibilities: Heads or Tails. Yes or No. Boy or Girl. And so on. We will see that that leads to what is called a binomial distribution.
What will be the outcomes when one of those two possibilities happens n times? To be specific, let n = 4. And say that we are going to toss a coin 4 times. Then each time we will see either Heads or Tails: H or T.
One outcome of 4 tosses might be
H T H H
Another might be
T T T H
Another:
H T H T
And so on.
Let us ask: In how many of those outcomes will there be, for example, exactly 3 H's?
To answer, consider that there will be 4 positions to fill with either H or T.
In how many different ways, then, could we choose 3 positions to have an H? It will be the combinatorial number 4C3 because the order will not matter. (Compare Problem 3 above, which is choosing students for a job. Here the "job" is to have an H!)
Similarly, the number of outcomes with exactly 1 H will be 4C1; the number with 2 will be 4C2; while the number with no H's—that is, all T's—will be 4C0.
The lower index k of each combinatorial number 4Ck indicates the number of times that H (one of the possibilities) appears in an outcome. The sum of those combinatorial numbers will be the number of possible outcomes.
4C0 + 4C1 + 4C2 + 4C3 + 4C4.
That number is 24.
The value of each of those combinatorial numbers is as follows:
1 + 4 + 6 + 4 + 1
There is exactly 1 way, 4C0, in which there are no H's, that is, all T's;
4 ways in which there is 1 H;
6 in which there are 2;
4 in which there are 3;
1 in which there are 4.
(In the theory of probability, the list of all possible outcomes is called the sample space.)
When there is one of two possibilities, the distribution of outcomes—the number of successes in n tries—is called a binomial distribution. It is called that because, as we will see in the next topic, the combinatorial numbers are the binomial coefficients.
Problem 9. Of all possible outcomes on tossing a coin 6 times, how many of them will have tails 4 times?
6C4 = 6C2 = 15.
Problem 10.
| a) | If 5 children are born to parents over the years, what is the total number of possible boy-girl sequences? |
| For example, one sequence might be bgggb; another, gbbbb; and so on. | |
25 = 32.
| b) | How many of those sequences will have 0 boys, how many 1 boy, how many 2, and so on? |
1 5 10 10 5 1
There will be 1 with no boys, 5 with 1 boy, 10 with 2, 10 with 3, 5 with 4, and 1 with 5.
Those are the combinatorial numbers 5Ck. Their sum is 32.
See Topic 25.
Problem 11. At Joe's Pizza Parlor, in addition to cheese there are 8 different toppings. If you can order any number of those 8 toppings, then how many different toppings could you possibly order?
28 = 256. For, this is the sum of all possible combinations: either no topping, or 1, or 2, and so on, up to 8.
Problem 12.
| a) | A door can be opened only with a security code that consists of five buttons. A code consists of pressing any one button, or any two, or any three, or any four, or all five. |
| How many possible codes are there? | |
| (You are to press all the buttons at once, so the order doesn't matter.) |
There are 5C1 ways to press a code consisting of just one button; 5C2 ways of pressing a code consisting of two buttons; and so on. The number of possible codes, then, is the sum of all the combinations of 5 things—except not taking any, 5C0, which is 1. The sum of all those combinations, then, is 25 − 1 = 32 − 1 = 31.
| b) | If, to open the door you must press three codes consecutively, then how many possible ways are there to open the door? |
| Assume that the same code may be repeated. |
According to part a), there are 31 ways to choose the first code. Again, 31 ways to choose the second, and 31 ways to choose the third. Therefore, the total number of ways to open the door is 313 = 29,791.
Next Topic: The binomial theorem
Please make a donation to keep TheMathPage online.
Even $1 will help.
Copyright © 2021 Lawrence Spector
Questions or comments?
E-mail: teacher@themathpage.com