Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

11.6 Combinatorics: Combinations

Evaluate combination notation and solve related applied problems.

We now consider counting techniques in which order is not considered.

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. That is,

Each hand contains the same combination of three cards.

Example 1

Find all the combinations of 3 letters taken from the set of 5 letters ${A, B, C, D, E}$ ${A, B, C, D, E}$ .

Solution

The combinations are

\begin{array}{rcl} {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} . \end{array}

$\begin{array}{rcl} {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} . \end{array}$

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} .

${A, C, B} names the same set as {A, B, C} .$

We want to derive a general formula for $_{n} C_{k}$ $_{n} C_{k}$ for any $k \leq n$ $k \leq n$ . First, it is true that $_{n} C_{n} = 1$ $_{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$ $_{n} C_{1} = n$ , because a set with n objects has n subsets with 1 element each. Finally, $_{n} C_{0} = 1$ $_{n} C_{0} = 1$ , because a set with n objects has only one subset with 0 elements, namely, the empty set $\emptyset$ $\emptyset$ . 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! \cdot_{5} C_{3} = 60 =_{5} P_{3} = 5 \cdot 4 \cdot 3,

$3! \cdot_{5} C_{3} = 60 =_{5} P_{3} = 5 \cdot 4 \cdot 3,$

_{5} C_{3} = \frac{_{5} P_{3}}{3!} = \frac{5 \cdot 4 \cdot 3}{3 \cdot 2 \cdot 1} = 10.

$_{5} C_{3} = \frac{_{5} P_{3}}{3!} = \frac{5 \cdot 4 \cdot 3}{3 \cdot 2 \cdot 1} = 10.$

In general, the number of combinations of n objects taken k at a time, $_{n} C_{k}$ $_{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:

\begin{array}{rcl} k! \cdot_{n} C_{k} & = & _{n} P_{k} \\ _{n} C_{k} & = & \frac{n P_{k}}{k!} \\ = & \frac{1}{k!} \cdot_{n} P_{k} \\ = & \frac{1}{k!} \cdot \frac{n!}{(n - k)!} = \frac{n!}{k! (n - k)!} . \end{array}

$\begin{array}{rcl} k! \cdot_{n} C_{k} & = & _{n} P_{k} \\ _{n} C_{k} & = & \frac{n P_{k}}{k!} \\ = & \frac{1}{k!} \cdot_{n} P_{k} \\ = & \frac{1}{k!} \cdot \frac{n!}{(n - k)!} = \frac{n!}{k! (n - k)!} . \end{array}$

Another kind of notation for $_{n} C_{k}$ $_{n} C_{k}$ is binomial coefficient notation. The reason for such terminology will be seen later.

You should be able to use either notation and either form of the formula.

Example 2

Evaluate $(_{5}^{7})$ $(_{5}^{7})$ , using forms (1) and (2).

Solution

By form (1),

$\begin{array}{rcl} (_{5}^{7}) & = & \frac{7!}{5! (7 - 5)!} = \frac{7!}{5! 2!} \\ = & \frac{7 \cdot 6 \cdot 5!}{5! \cdot 2!} = \frac{7 \cdot 6 \cdot 5!}{5! \cdot 2!} = \frac{7 \cdot 6}{2 \cdot 1} = 21. \end{array}$ $\begin{array}{rcl} (_{5}^{7}) & = & \frac{7!}{5! (7 - 5)!} = \frac{7!}{5! 2!} \\ = & \frac{7 \cdot 6 \cdot 5!}{5! \cdot 2!} = \frac{7 \cdot 6 \cdot 5!}{5! \cdot 2!} = \frac{7 \cdot 6}{2 \cdot 1} = 21. \end{array}$
By form (2),

Now Try Exercise 11.

Example 3

Evaluate $(_{0}^{n})$ $(_{0}^{n})$ and $(_{2}^{n})$ $(_{2}^{n})$ .

Solution

We use form (1) for the first expression and form (2) for the second. Then

(_{()}^{n}) = \frac{n!}{0! (n - 0)!} = \frac{n!}{1 \cdot n!} = 1,

$(_{()}^{n}) = \frac{n!}{0! (n - 0)!} = \frac{n!}{1 \cdot n!} = 1,$

using form (1), and

(_{2}^{n}) = \frac{n (n - 1)}{2!} = \frac{n (n - 1)}{2}, or \frac{n^{2} - n}{2},

$(_{2}^{n}) = \frac{n (n - 1)}{2!} = \frac{n (n - 1)}{2}, or \frac{n^{2} - n}{2},$

using form (2).

Now Try Exercise 19.

Note that

(_{2}^{7}) = \frac{7 \cdot 6}{2 \cdot 1} = 21.

$(_{2}^{7}) = \frac{7 \cdot 6}{2 \cdot 1} = 21.$

Using the result of Example 2 gives us

(_{5}^{7}) = (_{2}^{7}) .

$(_{5}^{7}) = (_{2}^{7}) .$

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} :$ ${A, B, C, D, E, F, G} :$

In general, we have the following. This result provides an alternative way to compute combinations.

We now solve problems involving combinations.

Example 4

Indiana Lottery Run by the state of Indiana, Hoosier Lotto is a twice-weekly lottery game with jackpots starting at $1 million. For a wager of $1, a player can choose 6 numbers from 1 through 48. If the numbers match those drawn by the state, the player wins the jackpot. (Source: www.hoosierlottery.com)

How many 6-number combinations are there?
Suppose it takes you 10 min to pick your numbers and buy a game ticket. How many tickets can you buy in 4 days?
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

No order is implied here. You pick any 6 different numbers from 1 through 48. Thus the number of combinations is

$\begin{array}{rcl} _{48} C_{6} & = & (\begin{matrix} 48 \\ 6 \end{matrix}) = \frac{48!}{6! (48 - 6)!} = \frac{48!}{6! 42!} \\ = & \frac{48 \cdot 47 \cdot 46 \cdot 45 \cdot 44 \cdot 43 \cdot 42!}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 \cdot 42!} \\ = & \frac{48 \cdot 47 \cdot 46 \cdot 45 \cdot 44 \cdot 43}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 12, 271, 512. \end{array}$ $\begin{array}{rcl} _{48} C_{6} & = & (\begin{matrix} 48 \\ 6 \end{matrix}) = \frac{48!}{6! (48 - 6)!} = \frac{48!}{6! 42!} \\ = & \frac{48 \cdot 47 \cdot 46 \cdot 45 \cdot 44 \cdot 43 \cdot 42!}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 \cdot 42!} \\ = & \frac{48 \cdot 47 \cdot 46 \cdot 45 \cdot 44 \cdot 43}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 12, 271, 512. \end{array}$
First, we find the number of minutes in 4 days:

$4 days = 4 days \cdot \frac{24 hr}{1 day} \cdot \frac{60 min}{1 hr} = 5760 min .$ $4 days = 4 days \cdot \frac{24 hr}{1 day} \cdot \frac{60 min}{1 hr} = 5760 min .$

Thus you could buy $5760 / 10$ $5760 / 10$ , or 576 tickets in 4 days.
You would need to hire $12, 271, 512 / 576$ $12, 271, 512 / 576$ , or about 21,305 people, to buy tickets with all the possible combinations and ensure a win. (This presumes lottery tickets can be bought 24 hours a day.)

Now Try Exercise 23.

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

\begin{array}{l} _{5} C_{3} \cdot_{7} C_{4} & = & \frac{5!}{3! 2!} \cdot \frac{7!}{4! 3!} \\ = & \frac{5 \cdot 4 \cdot 3!}{3! \cdot 2 \cdot 1} \cdot \frac{7 \cdot 6 \cdot 5 \cdot 4!}{4! \cdot 3 \cdot 2 \cdot 1} \\ = & \frac{5 \cdot 2 \cdot 2 \cdot 3!}{3! \cdot 2 \cdot 1} \cdot \frac{7 \cdot 3 \cdot 2 \cdot 5 \cdot 4!}{4! \cdot 3 \cdot 2 \cdot 1} \\ = & 10 \cdot 35 \\ = & 350. \end{array}

$\begin{array}{l} _{5} C_{3} \cdot_{7} C_{4} & = & \frac{5!}{3! 2!} \cdot \frac{7!}{4! 3!} \\ = & \frac{5 \cdot 4 \cdot 3!}{3! \cdot 2 \cdot 1} \cdot \frac{7 \cdot 6 \cdot 5 \cdot 4!}{4! \cdot 3 \cdot 2 \cdot 1} \\ = & \frac{5 \cdot 2 \cdot 2 \cdot 3!}{3! \cdot 2 \cdot 1} \cdot \frac{7 \cdot 3 \cdot 2 \cdot 5 \cdot 4!}{4! \cdot 3 \cdot 2 \cdot 1} \\ = & 10 \cdot 35 \\ = & 350. \end{array}$

Now Try Exercise 27.

Connecting the Concepts Permutations and Combinations

Permutations	Combinations
Permutations involve order and arrangements of objects.	Combinations do not involve order or arrangements of objects.
Given 5 books, we can arrange 3 of them on a shelf in $_{5} P_{3}$ $_{5} P_{3}$ , or 60 ways.	Given 5 books, we can select 3 of them in $_{5} C_{3}$ $_{5} C_{3}$ , or 10 ways.
Placing the books in different orders produces different arrangements.	The order in which the books are chosen does not matter.

11.6 Exercise Set

Evaluate.

1. $_{13} C_{2}$ $_{13} C_{2}$
2. $_{9} C_{6}$ $_{9} C_{6}$
3. $(_{11}^{13})$ $(_{11}^{13})$
4. $(_{3}^{9})$ $(_{3}^{9})$
5. $(_{1}^{7})$ $(_{1}^{7})$
6. $(_{8}^{8})$ $(_{8}^{8})$
7. $\frac{5 P_{3}}{3!}$ $\frac{5 P_{3}}{3!}$
11. $\frac{10 P_{5}}{5!}$ $\frac{10 P_{5}}{5!}$
9. $(_{0}^{6})$ $(_{0}^{6})$
10. $(_{1}^{6})$ $(_{1}^{6})$
11. $(_{2}^{6})$ $(_{2}^{6})$
12. $(_{3}^{6})$ $(_{3}^{6})$
13. $(_{0}^{7}) + (_{1}^{7}) + (_{2}^{7}) + (_{3}^{7}) + (_{4}^{7}) + (_{5}^{7}) + (_{6}^{7}) + (_{7}^{7})$ $(_{0}^{7}) + (_{1}^{7}) + (_{2}^{7}) + (_{3}^{7}) + (_{4}^{7}) + (_{5}^{7}) + (_{6}^{7}) + (_{7}^{7})$
14. $(_{0}^{6}) + (_{1}^{6}) + (_{2}^{6}) + (_{3}^{6}) + (_{4}^{6}) + (_{5}^{6}) + (_{6}^{6})$ $(_{0}^{6}) + (_{1}^{6}) + (_{2}^{6}) + (_{3}^{6}) + (_{4}^{6}) + (_{5}^{6}) + (_{6}^{6})$
15. $_{52} C_{4}$ $_{52} C_{4}$
16. $_{52} C_{5}$ $_{52} C_{5}$
17. $(_{11}^{27})$ $(_{11}^{27})$
18. $(_{8}^{37})$ $(_{8}^{37})$
19. $(_{1}^{n})$ $(_{1}^{n})$
20. $(_{3}^{n})$ $(_{3}^{n})$
21. $(_{m}^{m})$ $(_{m}^{m})$
22. $(_{4}^{t})$ $(_{4}^{t})$

In each of the following exercises, give an expression for the answer using permutation notation, combination notation, factorial notation, or other operations. Then evaluate.

23. Key Club Officers. There are 36 students in a high school Key Club, a service organization for teens. How many sets of 4 officers can be selected?
24. League Games. How many games can be played in a 9-team sports league if each team plays all other teams once? twice?
25. Test Options. On a test, a student is to select 10 out of 13 questions. In how many ways can this be done?
26. Senate Committees. Suppose that the Senate of the United States consists of 58 Democrats and 42 Republicans. How many committees can be formed consisting of 6 Democrats and 4 Republicans?
27. Test Options. Of the first 10 questions on a test, a student must answer 7. Of the second 5 questions, the student must answer 3. In how many ways can this be done?
28. Lines and Triangles from Points. How many lines are determined by 8 points, no 3 of which are collinear? How many triangles are determined by the same points?
29. Poker Hands. How many 5-card poker hands are possible with a 52-card deck?
30. Bridge Hands. How many 13-card bridge hands are possible with a 52-card deck?
31. Baskin-Robbins Ice Cream. Burt Baskin and Irv Robbins began making ice cream in 1945. Initially they developed 31 flavors—one for each day of the month. (Source: Baskin-Robbins)
1. How many 2-dip cones are possible using the 31 original flavors if order of flavors is to be considered and no flavor is repeated?
2. How many 2-dip cones are possible if order is to be considered and a flavor can be repeated?
3. How many 2-dip cones are possible if order is not considered and no flavor is repeated?
32. Powerball^®. Powerball® is a biweekly lottery game in which 5 white balls are drawn from a drum of 59 balls numbered 1–59 and 1 red ball is drawn from a drum of 35 balls numbered 1–35. To win the jackpot, a player must select numbers to match in any order the 5 white balls and the 1 red ball. (Source: www.powerball.com) How many 6-number combinations are there?

Skill Maintenance

Solve.

33. $3 x - 7 = 5 x + 10$ $3 x - 7 = 5 x + 10$ [1.5]
34. $2 x^{2} - x = 3$ $2 x^{2} - x = 3$ [3.2]
35. $x^{2} + 5 x + 1 = 0$ $x^{2} + 5 x + 1 = 0$ [3.2]
36. $x^{3} + 3 x^{2} - 10 x = 24$ $x^{3} + 3 x^{2} - 10 x = 24$ [4.4]

Synthesis

37. Flush. A flush in poker consists of a 5-card hand with all cards of the same suit. How many 5-card hands (flushes) are there that consist of all diamonds?
38. Full House. A full house in poker consists of three of a kind and a pair (two of a kind). How many full houses are there that consist of 3 aces and 2 queens? (See Section 11.8 for a description of a 52-card deck.)
39. League Games. How many games are played in a league with n teams if each team plays each other team once? twice?
40. There are n points on a circle. How many quadrilaterals can be inscribed with these points as vertices?

Solve for n.

41. $(\begin{matrix} n \\ n - 2 \end{matrix}) = 6$ $(\begin{matrix} n \\ n - 2 \end{matrix}) = 6$
42. $(\begin{matrix} n + 1 \\ 3 \end{matrix}) = 2 \cdot (\begin{matrix} n \\ 2 \end{matrix})$ $(\begin{matrix} n + 1 \\ 3 \end{matrix}) = 2 \cdot (\begin{matrix} n \\ 2 \end{matrix})$
43. $(\begin{array}{l} n + 2 \\ 4 \end{array}) = 6 \cdot (\begin{array}{l} n \\ 2 \end{array})$ $(\begin{array}{l} n + 2 \\ 4 \end{array}) = 6 \cdot (\begin{array}{l} n \\ 2 \end{array})$
44. $(\begin{array}{c} n \\ 3 \end{array}) = 2 \cdot (\begin{array}{c} n - 1 \\ 2 \end{array})$ $(\begin{array}{c} n \\ 3 \end{array}) = 2 \cdot (\begin{array}{c} n - 1 \\ 2 \end{array})$
45. How many line segments are determined by the n vertices of an n-gon? Of these, how many are diagonals? Use mathematical induction to prove the result for the diagonals.
46. Prove that

$(\begin{array}{c} n \\ k - 1 \end{array}) + (\begin{array}{c} n \\ k \end{array}) = (\begin{array}{c} n + 1 \\ k \end{array})$ $(\begin{array}{c} n \\ k - 1 \end{array}) + (\begin{array}{c} n \\ k \end{array}) = (\begin{array}{c} n + 1 \\ k \end{array})$

for any natural numbers n and k, $k \leq n$ $k \leq n$ .

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 11.6 Combinatorics: Combinations

Create new playlist

Sign In

Sign Up

Table of Contents for
11.6 Combinatorics: Combinations