maths.free › Statistics & Probability › 7. Probability › Combinations

Combinations

Distinguish between permutation and combination uses.

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.

ABCABDABEACBACDACE
ADBADCADEAEBAECAED
BACBADBAEBCABCDBCE
BDABDCBDEBEABECBED
CABCADCAECBACBDCBE
CDACDBCDECEACEBCED
DCADACDAEDBADBCDBE
DCADCBDCEDEADEBDEC
EABEACEADEBAEBCEBD
ECAECBECDEDAEDBEDC

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.

Practice (4)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

  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.
    جواب کھوليں
    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}\)
    جواب کھوليں
    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\]
    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?
    جواب کھوليں
    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?
    جواب کھوليں
    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:
      ClassNumber 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.

Symbols used here

n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
\pm
plus or minus
Both signs at once: x = 3 ± 2 means 5 and 1.
\approx
approximately 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_k
summation
Add a_k for k = 1 up to n.
A \cup B,\ A \cap B,\ A \setminus B
union, intersection, difference
In either; in both; in A but not B.
\bar{x},\ \mu
sample mean, population mean
Average of the data; average of the whole population.
\sigma,\ s,\ \sigma^2
standard deviation, sample s.d., variance
Typical distance from the mean; its square.
P(A),\ P(A \mid B)
probability, conditional probability
Chance of A; chance of A given that B happened.
E[X],\ \operatorname{Var}(X)
expected value, variance
Probability-weighted average of X; its spread.
N(\mu, \sigma^2),\ z
normal distribution, z-score
The bell curve with mean μ and variance σ²; (x − μ)/σ.

How to: 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.

Questions people ask

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.

آپ کے اپنے کو کوشش کریں

Parts of this page are adapted from OpenStax Contemporary Mathematics (CC BY-NC-SA 4.0). Condensed and re-explained here; errors are ours.

میں زیادہ 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