3.9 Combinations

XYZ Crunch demonstration: Counting ordered and unordered selections

Synthetic narration with English captions, a transcript, and time to think before checking the answer.

Read the transcript Download the video Narration credits and licences

A person is shown holding 5 playing cards. The hand of another player is shown near a pile of plastic chips. — **Figure 3.10** Combinations help us count things like the number of possible card hands, when the order in which the cards were drawn doesn’t matter.Combinations help us count things like the number of possible card hands, when the order in which the cards were drawn doesn’t matter. (credit: “IMG_3177” by Zanaca/Flickr, CC BY 2.0)

Earlier, we studied permutations, which we use to count the number of ways to generate an ordered list of a given length from a group of objects. An important property of permutations is that the order of the list matters: The results of a race and the selection of club officers are examples of lists where the order is important. In other situations, the order is not important. For example, in most card games where a player receives a hand of cards, the order in which the cards are received is irrelevant; in fact, players often rearrange the cards in a way that helps them keep the cards organized.

Combinations: When Order Doesn’t Matter

In situations in which the order of a list of objects doesn’t matter, the lists are no longer permutations. Instead, we call them combinations.

Example 1 Distinguishing Between Permutations and Combinations

For each of the following situations, decide whether the chosen subset is a permutation or a combination.

A social club selects 3 members to form a committee. Each of the members has an equal share of responsibility.
You are prompted to reset your email password; you select a password consisting of 10 characters without repeats.
At a dog show, the judge must choose first-, second-, and third-place finishers from a group of 16 dogs.
At a restaurant, the special of the day comes with the customer’s choice of 3 sides taken from a list of 6 possibilities.

Show solution

Since there is no distinction among the responsibilities of the 3 committee members, the order isn’t important. So, this is a combination.
The order of the characters in a password matters, so this is a permutation.
The order of finish matters in a dog show, so this is a permutation.
A plate with mashed potatoes, peas, and broccoli is functionally the same as a plate with peas, broccoli, and mashed potatoes, so this is a combination.

Counting Combinations

Permutations and combinations are certainly related, because they both involve choosing a subset of a large group. Let’s explore that connection, so that we can figure out how to use what we know about permutations to help us count combinations. We’ll take a basic example. How many ways can we select 3 letters from the group A, B, C, D, and E? If order matters, that number is $5 P sub 3 equals 60$ . That’s small enough that we can list them all out in the table below.

ABC	ABD	ABE	ACB	ACD	ACE
ADB	ADC	ADE	AEB	AEC	AED
BAC	BAD	BAE	BCA	BCD	BCE
BDA	BDC	BDE	BEA	BEC	BED
CAB	CAD	CAE	CBA	CBD	CBE
CDA	CDB	CDE	CEA	CEB	CED
DAB	DAC	DAE	DBA	DBC	DBE
DCA	DCB	DCE	DEA	DEB	DEC
EAB	EAC	EAD	EBA	EBC	EBD
ECA	ECB	ECD	EDA	EDB	EDC

Now, let’s look back at that list and color-code it so that groupings of the same 3 letters get the same color, as shown in Figure 3.11:

A table of ordered three-letter selections, grouped by their unordered letter sets. The table has 10 rows and 6 columns. The data is as follows: Row 1, ABC, ABD, ABE, ACB, ACD, ACE. Row 2, ADB, ADC, ADE, AEB, AEC, AED. Row 3, BAC, BAD, BAE, BCA, BCD, BCE. Row 4, BDA, BDC, BDE, BEA, BEC, BED. Row 5, CAB, CAD, CAE, CBA, CBD, CBE. Row 6, CDA, CDB, CDE, CEA, CEB, CED. Row 7, DAB, DAC, DAE, DBA, DBC, DBE. Row 8, DCA, DCB, DCE, DEA, DEB, DEC. Row 9, EAB, EAC, EAD, EBA, EBC, EBD. Row 10, ECA, ECB, ECD, EDA, EDB, EDC. Ordered selections with the same unordered letter set are color-coded together as follows: Dark red, ABC, ACB, BAC, BCA, CAB, CBA. Light red, ABD, ADB, BAD, BDA, DAB, DBA. Orange, ABE, AEB, BAE, BEA, EAB, EBA. Yellow, ACD, ADC, CAD, CDA, DAC, DCA. Light green, ACE, AEC, CAE, CEA, EAC, ECA. Dark green, ADE, AED, DAE, DEA, EAD, EDA. Light blue, BCD, BDC, CBD, CDB, DBC, DCB. Dark blue, BCE, BEC, CBE, CEB, EBC, ECB. Dark purple, BDE, BED, DBE, DEB, EBD, EDB. Light purple, CDE, CED, DCE, DEC, ECD, EDC. — **Figure 3.11**

After color-coding, we see that the 60 cells can be seen as 10 groups (colors) of 6. That’s no coincidence! We’ve already seen how to compute the number of permutations using the formula To compute the number of combinations, let’s count them another way using the Multiplication Rule for Counting. We’ll do this in two steps:

Step 1: Choose 3 letters (paying no attention to order).

Step 2: Put those letters in order.

The number of ways to choose 3 letters from this group of 5 (A, B, C, D, E) is the number of combinations we’re looking for; let’s call that number $5 C sub 3$ (read “the number of combinations of 5 objects taken 3 at a time”). We can see from our chart that this is ten (the number of colors used). We can generalize our findings this way: remember that the number of permutations of $n$ things taken $r$ at a time is $_{n} P_{r} = \frac{n!}{(n - r)!}$ . That number is also equal to $_{n} C_{r} \times r!$ , and so it must be the case that $\frac{n!}{(n - r)!} =_{n} C_{r} \times r!$ . Dividing both sides of that equation by $r!$ gives us the formula below.

Your Turn

Compute the following:

$_6{C_4}$

Show solution

The number of combinations of n objects taken r at a time is $nCr = \frac{{n!}}{{r!\left( {n - r} \right)!}}$ .

The answer will always be an integer, so check your math if you get a fraction.

$6C4 = \frac{{n!}}{{r!\left( {n - r} \right)!}} = \frac{{6!}}{{4!\left( {6 - 4} \right)!}} = \frac{{6!}}{{4!2!}} = \frac{{6 \times 5 \times \cancel{{4!}}}}{{\cancel{{4!}} \times 2 \times 1}} = \frac{{30}}{2} = 15$

$_{10}{C_8}$

Show solution

The number of combinations of n objects taken r at a time is $nCr = \frac{{n!}}{{r!\left( {n - r} \right)!}}$ .

The answer will always be an integer, so check your math if you get a fraction.

$10C8 = \frac{{n!}}{{r!\left( {n - r} \right)!}} = \frac{{10!}}{{8!\left( {10 - 8} \right)!}} = \frac{{10!}}{{8!2!}} = \frac{{10 \times 9 \times \cancel{{8!}}}}{{\cancel{{8!}} \times 2 \times 1}} = \frac{{90}}{2} = 45$

$_{14}{C_5}$

Show solution

The number of combinations of n objects taken r at a time is $nCr = \frac{{n!}}{{r!\left( {n - r} \right)!}}$ .

The answer will always be an integer, so check your math if you get a fraction.

$14C5 = \frac{{n!}}{{r!\left( {n - r} \right)!}} = \frac{{14!}}{{5!\left( {14 - 5} \right)!}} = \frac{{14!}}{{5!9!}} = \frac{{14 \times 13 \times 12 \times 11 \times 10 \times \cancel{{9!}}}}{{5 \times 4 \times 3 \times 2 \times 1 \times \cancel{{9!}}}} = \frac{{240,240}}{{120}} = 2,002$

Example 3 Applying the Combination Formula

In the card game Texas Hold’em (a variation of poker), players are dealt 2 cards from a standard deck to form their hands. How many different hands are possible?
The board game Clue uses a deck of 21 cards. If 3 people are playing, each person gets 6 cards for their hand. How many different 6-card Clue hands are possible?
For this example, use the earlier Palmetto Cash 5 model in which players choose 5 different numbers from 1 through 38, with order ignored. How many different 5-number sets are possible? This is a historical counting model; current game rules may differ.

Show solution

A standard deck has 52 cards, and a hand has 2 cards. Since the order doesn’t matter, we use the formula for counting combinations:
$_{52} C_{2} = \frac{52!}{2! (52 - 2)!} = \frac{52 \times 51 \times 50!}{2 \times 1 \times 50!} = \frac{52 \times 51}{2} = 1,326 .$
Again, the order doesn’t matter, so the number of combinations is:
$_{21} C_{6} = \frac{21!}{6! (21 - 6)!} = \frac{21 \times 20 \times 19 \times 18 \times 17 \times 16 \times 15!}{6 \times 5 \times 4 \times 3 \times 2 \times 1 \times 15!} = \frac{21 \times 19 \times 17 \times 16}{2} = 54,264 .$
There are 38 numbers to choose from, and we must pick 5. Since order doesn’t matter, the number of combinations is:
$_{38} C_{5} = \frac{38!}{5! (38 - 5)!} = \frac{38 \times 37 \times 36 \times 35 \times 34 \times 33!}{5 \times 4 \times 3 \times 2 \times 1 \times 33!} = 501,942 .$

Your Turn

At a charity event with 58 people in attendance, 3 raffle winners are chosen. All receive the same prize, so order doesn’t matter. How many different groups of 3 winners can be chosen?

Show solution

Since they all receive the same prize, it does not matter what order they call the names. This is a combination, choosing 3 names from 58.

$58C3 = \frac{{n!}}{{r!\left( {n - r} \right)!}} = \frac{{58!}}{{3!\left( {58 - 3} \right)!}} = \frac{{58!}}{{3!55!}} = \frac{{58 \times 57 \times 56 \times \cancel{{55!}}}}{{3 \times 2 \times 1 \times \cancel{{55!}}}} = \frac{{185,136}}{6} = 30,856$

A sorority with 42 members needs to choose a committee with 4 members, each with equal responsibility. How many committees are possible?

Show solution

Since they all have equal responsibility, it does not matter in which order you name the members. This is a combination, choosing 4 members from 42 members.

$42C4 = \frac{{n!}}{{r!\left( {n - r} \right)!}} = \frac{{42!}}{{4!\left( {42 - 4} \right)!}} = \frac{{42!}}{{4!38!}} = \frac{{42 \times 41 \times 40 \times 39 \times \cancel{{38!}}}}{{4 \times 3 \times 2 \times 1 \times \cancel{{38!}}}} = \frac{{2,686,320}}{{24}} = 111,930$

People in Mathematics

Early Eastern Mathematicians

Although combinations weren’t really studied in Europe until around the 13th century, mathematicians of the Middle and Far East had already been working on them for hundreds of years. The Indian mathematician known as Pingala had described them by the second century BCE; Varāhamihira (fl. sixth century) and Halayudha (fl. 10th century) extended Pingala’s work. In the ninth century, a Jain mathematician named Mahāvīra gave the formula for combinations that we use today.

In 10th-century Baghdad, a mathematician named Al-Karaji also knew formulas for combinations; though his work is now lost, it was known to (and repeated by) Persian mathematician Omar Khayyam, whose work survives. Khayyam is probably best remembered as a poet, with his Rubaiyat being his most famous work.

Meanwhile, in 11th-century China, Jia Xian also was working with combinations, as was his 13th-century successor Yang Hui.

It is not known whether the discoveries of any of these men were known in the other regions, or if the Indians, Persians, and Chinese all came to their discoveries independently. We do know that mathematical knowledge and sometimes texts did get passed along trade routes, so it can’t be ruled out.

Example 4 Combining Combinations with the Multiplication Rule for Counting

The student government at a university consists of 10 seniors, 8 juniors, 6 sophomores, and 4 first-years.

How many ways are there to choose a committee of 8 people from this group?
How many ways are there to choose a committee of 8 people if the committee must consist of 2 people from each class?

Show solution

There are 28 people to choose from, and we need 8. So, the number of possible committees is $28 C sub 8 equals 3,108,105$ .
Break the selection of the committee members down into a 4-step process: Choose the seniors, then choose the juniors, then the sophomores, and then the first-years, as shown in the table below:
Class Number of Ways to Choose Committee Representatives
senior $10 C sub 2 equals 45$
junior $8 C sub 2 equals 28$
sophomore $6 C sub 2 equals 15$
first-year $4 C sub 2 equals 6$
The Multiplication Rule for Counting tells us that we can get the total number of ways to complete this task by multiplying together the number of ways to do each of the four subtasks. So, there are $45 \times 28 \times 15 \times 6 = 113,400$ possible committees with these restrictions.

Your Turn

How many ways are there to choose a hand of 6 cards from a standard deck with the constraint that 3 are $\spadesuit$ , 2 are $\heartsuit$ , and 1 is $\clubsuit$ ?

Show solution

It does not matter in which order the cards are dealt to you. For each requirement, it is a combination. There are 13 cards in each suit.

Requirement	3 spades	2 hearts	1 club
Formula	13C3	13C2	13C1

Then, use the Multiplication Rule of Counting. The Multiplication Rule of Counting says that if there are n ways to accomplish one task and m ways to accomplish the second task for each way of accomplishing the first task, then there are $n{\text{ }} \times {\text{ }}m$ ways to accomplish both tasks. For additional tasks, multiply the number of allowed choices at each stage when that number is the same for every earlier choice sequence.

The number of ways to have the required hand is $13{\text{C}}3{\text{ }} \times {\text{ }}13{\text{C}}2{\text{ }} \times {\text{ }}13{\text{C}}1$ .

Evaluate each combination separately.

$13C3 = \frac{{n!}}{{r!\left( {n - r} \right)!}} = \frac{{13!}}{{3!\left( {13 - 3} \right)!}} = \frac{{13!}}{{3!10!}} = \frac{{13 \times 12 \times 11 \times \cancel{{10!}}}}{{3 \times 2 \times 1 \times \cancel{{10!}}}} = \frac{{1,716}}{6} = 286$

$13C2 = \frac{{n!}}{{r!\left( {n - r} \right)!}} = \frac{{13!}}{{2!\left( {13 - 2} \right)!}} = \frac{{13!}}{{2!11!}} = \frac{{13 \times 12\cancel{{11!}}}}{{2 \times 1 \times \cancel{{11!}}}} = \frac{{156}}{2} = 78$

$13C1 = \frac{{n!}}{{r!\left( {n - r} \right)!}} = \frac{{13!}}{{1!\left( {13 - 1} \right)!}} = \frac{{13!}}{{1!12!}} = \frac{{13\cancel{{12!}}}}{{1 \times \cancel{{12!}}}} = 13$

Now you can evaluate $13{\text{C}}3{\text{ }} \times {\text{ }}13{\text{C}}2{\text{ }} \times {\text{ }}13{\text{C}}1{\text{ }} = {\text{ }}286{\text{ }} \times {\text{ }}78{\text{ }} \times {\text{ }}13{\text{ }} = {\text{ }}290,004$ .

For the following exercises, decide whether the situation describes a permutation or a combination.

You’re packing for vacation, and you need to pick 5 shirts.

You and your friends are about to play a game, and you need to decide who will have the first turn, second turn, and so on.

You are watching your favorite reality show, and you want to know how many possibilities there are for the order of finish for the top three.

You are going to be working in groups of 4 with your classmates, and you want to know how many possibilities there are for the composition of your group.

For the following exercises, express your answers as whole numbers.

$_5{C_3}$

$_8{C_2}$

$_8{C_6}$

$_{12}{C_3}$

$_{12}{C_5}$

$_{14}{C_3}$

$_{14}{C_{10}}$

$_{15}{C_5}$

$_{15}{C_{13}}$

$_{18}{C_3}$

$_{18}{C_6}$

$_{20}{C_4}$

In most variations of the card game poker, a hand consists of 5 cards, where the order doesn’t matter. How many different poker hands are there?

A professor starts each class by choosing 3 students to present solutions to homework problems to the class. If there are 41 students in the class, in how many different ways can the professor make those selections?

An election for at-large members of a school board has 7 candidates; 3 will be elected. How many different ways can those 3 seats be filled?

There are 20 contestants on a reality TV show; at the end of the first episode, 10 are eliminated. How many different groups of eliminated contestants are possible?

At a horse race, bettors can place a bet called an exacta box. For this bet, the player chooses 2 horses; if those horses finish first and second (in either order), the player wins. In a race with 12 horses in the field, how many possible exacta box bets are there?

The following exercises are about the card game euchre, which uses a partial standard deck of cards: it only has the cards with ranks 9, 10, J, Q, K, and A (for a total of 24 cards). Some variations of the game use the 8s or the 7s and 8s, but we’ll stick with the 24-card version.

A euchre hand contains 5 cards. How many ways are there to receive a 5-card hand (where the order in which the cards are received doesn’t matter, i.e., 9 $\heartsuit$ , J $\heartsuit$ , ${\text{K}}\clubsuit$ , $9\spadesuit$ , $10\spadesuit$ is the same as $9\spadesuit$ , J $\heartsuit$ , 9 $\heartsuit$ , ${\text{K}}\clubsuit$ , $10\spadesuit$ )?

After all 4 players get their hands, the remaining 4 cards are placed face down in the center of the table. Across all possible deals, how many different unordered groups of 4 cards can remain from the 24-card deck? Do not fix one particular deal.

Euchre is played with partners. How many ways are there for 2 partners to receive 5-card hands (where, as above, the order doesn’t matter)? Hint: After the first person gets their cards, there are $24 - 5 = 19$ cards left for the second person.

You and 5 of your friends are at an amusement park, and are about to ride a roller coaster. The cars have room for 6 people arranged in 3 rows of 2, so you and your friends will perfectly fill one car.

How many ways are there to choose the 2 people in the front row?

Assuming the front row has been selected, how many ways are there to choose the 2 people in the middle row?

Assuming the first 2 rows have been selected, how many ways are there to choose the 2 people in the back row?

Using the Multiplication Rule for Counting and your answers to the earlier parts of this exercise, how many ways are there for your friends to sort yourselves into rows to board the roller coaster?

The University Combinatorics Club has 18 members. Four of them will be selected to form a committee.

How many different committees of 4 are possible, assuming all of the duties are shared equally?

Instead of sharing responsibility equally, one person will be chosen to be the committee chair. How many different committees are possible? Count these by selecting a chair first, then selecting the remaining 3 members of the committee from the remaining club members and use the Multiplication Rule for Counting. Show your work.

Let’s count the number of committees with chairs a different way: First, choose 4 people for the committee (as in the first question), then choose 1 of the 4 to be chair. Show your work. Do you get the same number?

For the following Powerball^® exercises, use a counting model in which a ticket contains 5 distinct white-ball numbers from 1 to 69 and one red Powerball number from 1 to 26. The white-ball numbers form an unordered group; the red number is a separate choice.

How many different ways are there to choose the 5 white-ball numbers in this model?

How many ways are there to choose the red Powerball number in this model?

How many different tickets can be formed by combining a white-ball group with a separate red Powerball choice?

You are in charge of programming for a music festival. The festival has a main stage, a secondary stage, and several smaller stages. There are 40 bands confirmed for the festival. Five of those will play the main stage, and 8 will play the secondary stage. How many ways are there for you to allocate bands to these 2 stages?

Corequisite Skills for Introductory Statistics is a custom course edition compiled for Introductory Statistics corequisite courses from OpenStax Contemporary Mathematics, Elementary Algebra 2e, Intermediate Algebra 2e, Prealgebra 2e. Content by OpenStax is reproduced as published, apart from any corrections recorded for this edition. Sections are renumbered to follow the course outline. The course outline is adapted from Larry Green's Support Course for Elementary Statistics (LibreTexts, https://stats.libretexts.org/Bookshelves/Introductory_Statistics/Support_Course_for_Elementary_Statistics), used under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). Lessons 2.4 and 6.7 are written for this edition by XYZ Homework. Every OpenStax lesson is abridged to the subsections and practice exercises this course uses. Lessons are headed with their course titles, not the source section titles. Access the complete originals free at openstax.org. License: CC-BY-NC-SA-4.0.

ABC	ABD	ABE	ACB	ACD	ACE
ADB	ADC	ADE	AEB	AEC	AED
BAC	BAD	BAE	BCA	BCD	BCE
BDA	BDC	BDE	BEA	BEC	BED
CAB	CAD	CAE	CBA	CBD	CBE
CDA	CDB	CDE	CEA	CEB	CED
DAB	DAC	DAE	DBA	DBC	DBE
DCA	DCB	DCE	DEA	DEB	DEC
EAB	EAC	EAD	EBA	EBC	EBD
ECA	ECB	ECD	EDA	EDB	EDC

Class	Number of Ways to Choose Committee Representatives
senior	$10 C sub 2 equals 45$
junior	$8 C sub 2 equals 28$
sophomore	$6 C sub 2 equals 15$
first-year	$4 C sub 2 equals 6$

ABC	ABD	ABE	ACB	ACD	ACE
ADB	ADC	ADE	AEB	AEC	AED
BAC	BAD	BAE	BCA	BCD	BCE
BDA	BDC	BDE	BEA	BEC	BED
CAB	CAD	CAE	CBA	CBD	CBE
CDA	CDB	CDE	CEA	CEB	CED
DAB	DAC	DAE	DBA	DBC	DBE
DCA	DCB	DCE	DEA	DEB	DEC
EAB	EAC	EAD	EBA	EBC	EBD
ECA	ECB	ECD	EDA	EDB	EDC

ABC	ABD	ABE	ACB	ACD	ACE
ADB	ADC	ADE	AEB	AEC	AED
BAC	BAD	BAE	BCA	BCD	BCE
BDA	BDC	BDE	BEA	BEC	BED
CAB	CAD	CAE	CBA	CBD	CBE
CDA	CDB	CDE	CEA	CEB	CED
DAB	DAC	DAE	DBA	DBC	DBE
DCA	DCB	DCE	DEA	DEB	DEC
EAB	EAC	EAD	EBA	EBC	EBD
ECA	ECB	ECD	EDA	EDB	EDC