# Combinations

We sometimes make a selection from a set*without regard to order*. Such a selection is called a

*. If you play cards, for example, you know that in most situations the order in which you hold cards is not important.*

**combination****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 _{n}C_{k}.

We call _{n}C_{k} * combination notation*. We want to derive a general formula for

_{n}C

_{k}for any k ≤ n. First, it is true that

_{n}C

_{n}= 1, because a set with n objects has only 1 subset with n objects, the set itself. Second,

_{n}C

_{1}= n, because a set with n objects has n subsets with 1 element each. Finally,

_{n}C

_{0}= 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! • _{5}C_{3} = 60 = _{5}P_{3} = 5 • 4 • 3,

so

.

In general, the number of combinations of n objects taken k at a time, _{n}C_{k}, times the number of permutations of these objects, k!, must equal the number of permutations of n objects taken k at a time:

k!._{n}C_{k} = _{n}P_{k}_{n}C_{k} = _{n}P_{k}/k!_{n}C_{k} = (1/k!)._{n}P_{k}_{n}C_{k} =

**Combinations of n Objects Taken k at a Time**

The total number of combinations of n objects taken k at a time, denoted _{n}C_{k}, is given by

(1) _{n}C_{k} = ,

or

(2) _{n}C_{k} =

Another kind of notation for _{n}C_{k} 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 _{n}C_{k} = _{n}C_{n-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 _{5}C_{3} ways and the 4 senators can be selected in _{7}C_{4} ways. If we use the fundamental counting principle, it follows that the number of possible committees is