Combinations
We sometimes make a selection from a set without regard to order. Such a selection is called a combination. If you play cards, for example, you know that in most situations the order in which you hold cards is not important.Example 1 Find all the combinations of 3 letters taken from the set of 5 letters {A, B, C, D, E}.
Solution The combinations are
{A, B, C}, {A, B, D},
{A, B, E}, {A, C, D},
{A, C, E}, {A, D, E},
{B, C, D}, {B, C, E},
{B, D, E}, {C, D, E}.
There are 10 combinations of the 5 letters taken 3 at a time.
When we find all the combinations from a set of 5 objects taken 3 at a time, we are finding all the 3-element subsets. When a set is named, the order of the elements is not considered. Thus,
{A, C, B} names the same set as {A, B, C}.
Subset
Set A is a subset of set B, denoted A is subset and/or coicides with B,if every element of A is an element of B.
The elements of a subset are not ordered. When thinking of combinations, do not think about order!
Combination
A combination containing k objects is a subset containing k objects.
We want to develop a formula for computing the number of combinations of n objects taken k at a time without actually listing the combinations or subsets.
Combination Notation
The number of combinations of n objects taken k at a time is denoted nCk.
We call nCk combination notation. We want to derive a general formula for nCk for any k ≤ n. First, it is true that nCn = 1, because a set with n objects has only 1 subset with n objects, the set itself. Second, nC1 = n, because a set with n objects has n subsets with 1 element each. Finally, nC0 = 1, because a set with n objects has only one subset with 0 elements, namely, the empty set ∅. To consider other possibilities, let’s return to Example 1 and compare the number of combinations with the number of permutations.
Note that each combination of 3 objects yields 6, or 3!, permutations.
3! • 5C3 = 60 = 5P3 = 5 • 4 • 3,
so
.
In general, the number of combinations of n objects taken k at a time, nCk, times the number of permutations of these objects, k!, must equal the number of permutations of n objects taken k at a time:
k!.nCk = nPk
nCk = nPk/k!
nCk = (1/k!).nPk
nCk =
Combinations of n Objects Taken k at a Time
The total number of combinations of n objects taken k at a time, denoted nCk, is given by
(1) nCk = ,
or
(2) nCk =
Another kind of notation for nCk is binomial coefficient notation.The reason for such terminology will be seen later.
Binomial Coefficient Notation
You should be able to use either notation and either form of theformula.
Example 2 Evaluate , using forms (1) and (2).
Solution
a) By form (1),
.
b) By form (2),
Be sure to keep in mind that does not mean n/k.
Example 3 Evaluate and .
Solution We use form (1) for the first expression and form (2) for the second. Then
,
using form (1), and
,
using form (2).
Note that
,
so that using the result of Example 2 gives us
.
This says that the number of 5-element subsets of a set of 7 objects is the same as the number of 2-element subsets of a set of 7 objects.When 5 elements are chosen from a set, one also chooses not to include 2 elements. To see this, consider the set {A, B, C, D, E, F, G}:
In general, we have the following. This result provides an alternative way to compute combinations.
Subsets of Size k and of Size
and nCk = nCn-k
The number of subsets of size k of a set with n objects is the same as the number of subsets of size n - k. The number of combinations of n objects taken k at a time is the same as the number of combinations of n objects taken at a time.
We now solve problems involving combinations.
Example 4 Michigan Lottery. Run by the state of Michigan, WINFALL is a twice-weekly lottery game with a jackpot of at least \$2 million. For a purchase price of \$1, a player can pick any 6 numbers from 1 through 49. If the numbers match those drawn by the state, the player wins. (Source: Michigan Lottery)
a) How many 6-number combinations are there?
b) Suppose that it takes 10 min to pick your numbers and buy a game ticket. How many tickets can you buy in 4 days?
c) How many people would you have to hire for 4 days to buy tickets with all the possible combinations and ensure that you win?
Solution
a) No order is implied here. You pick any 6 numbers from 1 to 49. Thus the number of combinations is
b) First we find the number of minutes in 4 days:
4days • (24hr/1day).(60min/1hr) = 5760 min.
Thus you could buy 576 tickets in 4 days.
c) You would need to hire 13,983,816/576, or about 24,278 people to buy tickets with all the possible combinations and ensure a win.(This presumes lottery tickets can be bought 24 hours a day.)
Example 5 How many committees can be formed from a group of 5 governors and 7 senators if each committee consists of 3 governors and 4 senators?
Solution The 3 governors can be selected in 5C3 ways and the 4 senators can be selected in 7C4 ways. If we use the fundamental counting principle, it follows that the number of possible committees is