Combinations

Learning Objectives

After completing this section, you should be able to:

1. Distinguish between permutation and combination uses.
2. Compute combinations.
3. Apply combinations to solve applications.

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.

Distinguishing Between Permutations and Combinations

Try it.

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

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

Solution

1. Since there is no distinction among the responsibilities of the 3 committee members, the order isn’t important. So, this is a combination.
2. The order of the characters in a password matter, so this is a permutation.
3. The order of finish matters in a dog show, so this is a permutation.
4. 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}_{3}=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
DCA	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 :

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

Using the Combination Formula

Try it.

Compute the following:

1. \({}_{8}{C}_{3}\)
2. \({}_{12}{C}_{5}\)
3. \({}_{15}{C}_{9}\)

Solution

1. \[{}_{8}{C}_{3}=\frac{8!}{3!(8-3)!}=\frac{8\times 7\times 6\times 5!}{3\times 2\times 1\times 5!}=8\times 7=56\]
2. \[{}_{12}{C}_{5}=\frac{12!}{5!(12-5)!}=\frac{12\times 11\times 10\times 9\times 8\times 7!}{5\times 4\times 3\times 2\times 1\times 7!}=11\times 9\times 8=792\]
3. \[{}_{15}{C}_{9}=\frac{15!}{9!(15-9)!}=\frac{15\times 14\times 13\times 12\times 11\times 10\times 9!}{9!\times 6\times 5\times 4\times 3\times 2\times 1}=\frac{14\times 13\times 11\times 10}{4}=5,005\]

Condensed: the full section is in OpenStax Contemporary Mathematics.

Key Concepts

• Permutations are used to count subsets when order matters; combinations work when order doesn't matter.
• Combinations can also be computed using factorials.

Now you Không máy tính nào có thể tính toán được nó, nhưng các mảnh của nó có thể tính toán được. Thử một trong những cách dưới đây, hoặc gõ theo ý bạn.

⌨ Kiểu ✎ Vẽ đi.

Câu hỏi toán của anh.

π Giải quyết

Luyện tập (4)

Đầu tiên thử mỗi câu trên giấy. Cho thấy câu trả lời để kiểm tra; những câu trả lời đã kiểm tra có thể mở trong trình giải cho mỗi bước.

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

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

   Giải đáp

   1. Since there is no distinction among the responsibilities of the 3 committee members, the order isn’t important. So, this is a combination.
   2. The order of the characters in a password matter, so this is a permutation.
   3. The order of finish matters in a dog show, so this is a permutation.
   4. 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.

2. Compute the following:

   1. \({}_{8}{C}_{3}\)
   2. \({}_{12}{C}_{5}\)
   3. \({}_{15}{C}_{9}\)
   Làm việc đi. Gợi ý

   Giải đáp

   1. \[{}_{8}{C}_{3}=\frac{8!}{3!(8-3)!}=\frac{8\times 7\times 6\times 5!}{3\times 2\times 1\times 5!}=8\times 7=56\]
   2. \[{}_{12}{C}_{5}=\frac{12!}{5!(12-5)!}=\frac{12\times 11\times 10\times 9\times 8\times 7!}{5\times 4\times 3\times 2\times 1\times 7!}=11\times 9\times 8=792\]
   3. \[{}_{15}{C}_{9}=\frac{15!}{9!(15-9)!}=\frac{15\times 14\times 13\times 12\times 11\times 10\times 9!}{9!\times 6\times 5\times 4\times 3\times 2\times 1}=\frac{14\times 13\times 11\times 10}{4}=5,005\]
3. 1. 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?
   2. 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?
   3. Palmetto Cash 5 is a game offered by the South Carolina Education Lottery. Players choose 5 numbers from the whole numbers between 1 and 38 (inclusive); the player wins the jackpot of $100,000 if the randomizer selects those numbers in any order. How many different sets of winning numbers are possible?
   Làm việc đi. Gợi ý

   Giải đáp

   1. 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\text{.}\]
   2. 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\text{.}\]
   3. 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,492\text{.}\]

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

   1. How many ways are there to choose a committee of 8 people from this group?
   2. How many ways are to choose a committee of 8 people if the committee must consist of 2 people from each class?
   Làm việc đi. Gợi ý

   Giải đáp

   1. There are 28 people to choose from, and we need 8. So, the number of possible committees is \({}_{28}{C}_{8}=3,108,105\).
   2. 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}_{2}=45\)
      junior	\({}_{8}{C}_{2}=28\)
      sophomore	\({}_{6}{C}_{2}=15\)
      first-year	\({}_{4}{C}_{2}=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.

Để cho anh làm việc

Một tài khoản miễn phí thêm ghi chú vào mỗi bài học, ghi chép những gì bạn đã hoàn thành, các bài toán bạn giải quyết ở một nơi, và một giáo viên bạn có thể hỏi về trang này. Toán học là mở cho mọi người, dù có đăng nhập hay không.

Đăng ký Đăng nhập

Ký hiệu được dùng ở đây

Nhấn vào bất kỳ ký hiệu nào để xem định nghĩa đầy đủ, một bức ảnh, và ý nghĩa của từng chữ cái trong nó.

n!factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.\pmplus or minus
Both signs at once: x = 3 ± 2 means 5 and 1.\approxapproximately equal
Equal to the precision shown, not exactly.\binom{n}{k}binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).\sum_{k=1}^{n} a_ksummation
Add a_k for k = 1 up to n.A \cup Bunion, intersection, difference
In either; in both; in A but not B.\bar{x}sample mean, population mean
Average of the data; average of the whole population.\sigmastandard deviation, sample s.d., variance
Typical distance from the mean; its square.P(A)probability, conditional probability
Chance of A; chance of A given that B happened.E[X]expected value, variance
Probability-weighted average of X; its spread.N(\munormal distribution, z-score
The bell curve with mean μ and variance σ²; (x − μ)/σ.

Làm thế nào: Combinations

1. Distinguish between permutation and combination uses.
2. Compute combinations.
3. Apply combinations to solve applications.
4. A social club selects 3 members to form a committee. Each of the members has an equal share of responsibility.
5. You are prompted to reset your email password; you select a password consisting of 10 characters without repeats.
6. At a dog show, the judge must choose first-, second-, and third-place finishers from a group of 16 dogs.
7. At a restaurant, the special of the day comes with the customer’s choice of 3 sides taken from a list of 6 possibilities.
8. Since there is no distinction among the responsibilities of the 3 committee members, the order isn’t important. So, this is a combination.

Câu hỏi người ta hỏi

Mean or median, which should I use?

Median when the data have outliers or a long tail (incomes, house prices); mean when the data are roughly symmetric and you want every value to count. Report both if they disagree. The gap is itself information.

What does a p-value actually say?

The probability of seeing data at least this extreme if the null hypothesis were true. It is not the probability that the null hypothesis is true.

Why divide by n − 1 for the sample variance?

The sample mean sits closer to the sample than the true mean does, so squared deviations from it are slightly too small on average; dividing by n − 1 instead of n corrects the bias.

Một số phần của trang này được chuyển từ OpenStax Contemporary Mathematics (CC BY-NC-SA 4.0). Được nén lại và giải thích lại ở đây; lỗi là của chúng tôi. Bởi vì nguồn của nó được cấp phép cho sử dụng không thương mại, bài học này là miễn phí, không bán gì, và được chia sẻ dưới cùng một giấy phép.

More in Statistics & Probability

Sampling and dataDescribing data with graphsMean, median and modeProbabilityCounting: permutations and combinationsDiscrete random variablesContinuous random variablesThe normal distributionThe central limit theoremConfidence intervalsHypothesis testingComparing two samplesChi-square testsLinear regression and correlation