Permutations

Learning Objectives

After completing this section, you should be able to:

1. Use the Multiplication Rule for Counting to determine the number of permutations.
2. Compute expressions containing factorials.
3. Compute permutations.
4. Apply permutations to solve problems.

Applying the Multiplication Rule for Counting to Permutations

In the case of the swimming finals, one possible permutation of length 3 would be the list of medal winners (first, second, and third place finishers). A permutation of length 8 would be the full order of finish (first place through eighth place). Let’s use the Multiplication Rule for Counting to figure out how many of each of these permutations there are.

Using the Multiplication Rule for Counting to Find the Number of Permutations

Try it.

The final heat of Olympic swimming events features 8 swimmers (or teams of swimmers).

1. How many different podium placements (first place, second place, and third place) are possible?
2. How many different complete orders of finish (first place through eighth place) are possible?

Solution

1. Let’s start with the first place finisher. How many options are there? Since 8 swimmers are competing, there are 8 possibilities. Once that first swimmer completes the race, there are 7 swimmers left competing for second place. After the second finisher is decided, there are 6 swimmers remaining who could possibly finish in third place. Thus, there are 8 possibilities for first place, 7 for second place, and 6 for third place. The Multiplication Rule for Counting then tells us there are \(8\times 7\times 6=336\) different ways the winners’ podium can be filled out.
2. To look at the complete order of finish, we can continue the pattern we can see in part 1 of this example: There are 5 possibilities for fourth place, 4 for fifth place, 3 for sixth place, 2 for seventh place, and then just 1 swimmer is left to finish in eighth place. Using the Multiplication Rule for Counting, we see that there are \(8\times 7\times 6\times 5\times 4\times 3\times 2\times 1=40,320\) possible orders of finish.

Factorials

The pattern we see in occurs commonly enough that we have a name for it: factorial.
For any positive whole number \(n\), we define the factorial of \(n\) (denoted \(n!\) and read "\(n\) factorial") to be the product of every whole number less than or equal to \(n\). We also define 0! to be equal to one. We will use factorials in a couple of different contexts, so let's get some practice doing computations with them.

Computing Factorials

Try it.

Compute the following:

1. \(4!\)
2. \(\frac{8!}{6!}\)
3. \(\frac{9!}{3!4!}\)

Solution

1. \(4!=4\times \text{3}\times \text{2}\times 1=24\)
2. There are two ways to approach this calculation. The first way is to compute the factorials first, then divide: \[\frac{8!}{6!}=\frac{8\times 7\times 6\times 5\times 4\times 3\times 2\times 1}{6\times 5\times 4\times 3\times 2\times 1}=\frac{40,320}{720}=56\]

   However, there is an easier way! You may notice in the second step that there are several terms that can be canceled; that’s always the case whenever we divide factorials. In this case, notice that we can rewrite the numerator like this:

   \[8!=8\times 7\times (6\times 5\times 4\times 3\times 2\times 1)=8\times 7\times 6!\]

   With that in mind, we can proceed this way by canceling out the 6!:

   \[\frac{8!}{6!}=\frac{8\times 7\times 6!}{6!}=8\times 7=56\] That’s much easier!

3. Let’s approach this one using our canceling technique. When we see two factorials in either the numerator or denominator, we should focus on the larger one first. So:

   \[\frac{9!}{3!4!}=\frac{9\times 8\times 7\times 6\times 5\times 4!}{3!4!}=\frac{9\times 8\times 7\times 6\times 5}{3\times 2\times 1}=9\times 8\times 7\times 5=2,520\]

Permutations

As we’ve seen, factorials can pop up when we’re computing permutations. In fact, there is a formula that we can use to make that connection explicit. Let’s define some notation first. If we have a collection of \(n\) objects and we wish to create an ordered list of \(r\) of the objects (where \(1\le r\le n\)), we’ll call the number of those permutations \({}_{n}{P}_{r}\) (read “the number of permutations of \(n\) objects taken \(r\) at a time”). We formalize the formula we'll use to compute permutations below.

If you wondered why we defined \(0!=1\) earlier, it was to make formulas like this one work; if we have \(n\) objects and want to order all of them (so, we want the number of permutations of \(n\) objects taken \(n\) at a time), we get \({}_{n}{P}_{n}=\frac{n!}{(n-n)!}=\frac{n!}{0!}=\frac{n!}{1}=n!\). Next, we’ll get some practice computing these permutations.

Computing Permutations

Try it.

Find the following numbers:

1. The number of permutations of 12 objects taken 3 at a time
2. The number of permutations of 8 objects taken 5 at a time
3. The number of permutations of 32 objects taken 2 at a time

Solution

1. \[{}_{12}{P}_{3}=\frac{12!}{(12-3)!}=\frac{12!}{9!}=\frac{12\times 11\times 10\times 9!}{9!}=12\times 11\times 10=1,320\]
2. \[{}_{8}{P}_{5}=\frac{8!}{(8-5)!}=\frac{8\times 7\times 6\times 5\times 4\times 3!}{3!}=8\times 7\times 6\times 5\times 4=6,720\]
3. \[{}_{32}{P}_{2}=\frac{32!}{(32-2)!}=\frac{32\times 31\times 30!}{30!}=32\times 31=992\]

Applying Permutations

Try it.

1. A high school graduating class has 312 students. The top student is declared valedictorian, and the second-best is named salutatorian. How many possible outcomes are there for the valedictorian and salutatorian?
2. In the card game blackjack, the dealer’s hand of 2 cards is dealt with 1 card faceup and 1 card facedown. If the game is being played with a single deck of (52) cards, how many possible hands could the dealer get?
3. The University Combinatorics Club has 3 officers: president, vice president, and treasurer. If there are 18 members of the club, how many ways are there to fill the officer positions?

Solution

1. This is the number of permutations of 312 students taken 2 at a time, and \({}_{312}{P}_{2}=97,032\).
2. We want the number of permutations of 52 cards taken 2 at a time, and \({}_{52}{P}_{2}=2,652\).
3. Here we’re looking for the number of permutations of 18 members taken 3 at a time, and \({}_{18}{P}_{3}=4,896\).

Condensed: the full section is in OpenStax Contemporary Mathematics.

Key Concepts

• Using the Multiplication Rule for Counting to enumerate permutations.
• Simplifying and computing expressions involving factorials.
• Using factorials to count permutations.

Dabar tu Joks skaičiuotuvas nenusistato, bet jo dalys yra skaičiuojamos. Pabandykite vieną žemiau arba įveskite savo.

⌨ Tipas ✎ Piešti

Jūsų matematikos problema

π Išspręsti

Praktika (4)

Išbandykite kiekvieną ant popieriaus pirmą. Atskleisti atsakymą patikrinti; patikrintas tie gali būti atidarytas sprendėjas už kiekvieną žingsnį.

1. The final heat of Olympic swimming events features 8 swimmers (or teams of swimmers).

   1. How many different podium placements (first place, second place, and third place) are possible?
   2. How many different complete orders of finish (first place through eighth place) are possible?
   Dirbkite per ją Patarimas

   Atskleisti atsakymą

   1. Let’s start with the first place finisher. How many options are there? Since 8 swimmers are competing, there are 8 possibilities. Once that first swimmer completes the race, there are 7 swimmers left competing for second place. After the second finisher is decided, there are 6 swimmers remaining who could possibly finish in third place. Thus, there are 8 possibilities for first place, 7 for second place, and 6 for third place. The Multiplication Rule for Counting then tells us there are \(8\times 7\times 6=336\) different ways the winners’ podium can be filled out.
   2. To look at the complete order of finish, we can continue the pattern we can see in part 1 of this example: There are 5 possibilities for fourth place, 4 for fifth place, 3 for sixth place, 2 for seventh place, and then just 1 swimmer is left to finish in eighth place. Using the Multiplication Rule for Counting, we see that there are \(8\times 7\times 6\times 5\times 4\times 3\times 2\times 1=40,320\) possible orders of finish.

2. Compute the following:

   1. \(4!\)
   2. \(\frac{8!}{6!}\)
   3. \(\frac{9!}{3!4!}\)
   Dirbkite per ją Patarimas

   Atskleisti atsakymą

   1. \(4!=4\times \text{3}\times \text{2}\times 1=24\)
   2. There are two ways to approach this calculation. The first way is to compute the factorials first, then divide: \[\frac{8!}{6!}=\frac{8\times 7\times 6\times 5\times 4\times 3\times 2\times 1}{6\times 5\times 4\times 3\times 2\times 1}=\frac{40,320}{720}=56\]

      However, there is an easier way! You may notice in the second step that there are several terms that can be canceled; that’s always the case whenever we divide factorials. In this case, notice that we can rewrite the numerator like this:

      \[8!=8\times 7\times (6\times 5\times 4\times 3\times 2\times 1)=8\times 7\times 6!\]

      With that in mind, we can proceed this way by canceling out the 6!:

      \[\frac{8!}{6!}=\frac{8\times 7\times 6!}{6!}=8\times 7=56\] That’s much easier!

   3. Let’s approach this one using our canceling technique. When we see two factorials in either the numerator or denominator, we should focus on the larger one first. So:

      \[\frac{9!}{3!4!}=\frac{9\times 8\times 7\times 6\times 5\times 4!}{3!4!}=\frac{9\times 8\times 7\times 6\times 5}{3\times 2\times 1}=9\times 8\times 7\times 5=2,520\]

3. Find the following numbers:

   1. The number of permutations of 12 objects taken 3 at a time
   2. The number of permutations of 8 objects taken 5 at a time
   3. The number of permutations of 32 objects taken 2 at a time
   Dirbkite per ją Patarimas

   Atskleisti atsakymą

   1. \[{}_{12}{P}_{3}=\frac{12!}{(12-3)!}=\frac{12!}{9!}=\frac{12\times 11\times 10\times 9!}{9!}=12\times 11\times 10=1,320\]
   2. \[{}_{8}{P}_{5}=\frac{8!}{(8-5)!}=\frac{8\times 7\times 6\times 5\times 4\times 3!}{3!}=8\times 7\times 6\times 5\times 4=6,720\]
   3. \[{}_{32}{P}_{2}=\frac{32!}{(32-2)!}=\frac{32\times 31\times 30!}{30!}=32\times 31=992\]
4. 1. A high school graduating class has 312 students. The top student is declared valedictorian, and the second-best is named salutatorian. How many possible outcomes are there for the valedictorian and salutatorian?
   2. In the card game blackjack, the dealer’s hand of 2 cards is dealt with 1 card faceup and 1 card facedown. If the game is being played with a single deck of (52) cards, how many possible hands could the dealer get?
   3. The University Combinatorics Club has 3 officers: president, vice president, and treasurer. If there are 18 members of the club, how many ways are there to fill the officer positions?
   Dirbkite per ją Patarimas

   Atskleisti atsakymą

   1. This is the number of permutations of 312 students taken 2 at a time, and \({}_{312}{P}_{2}=97,032\).
   2. We want the number of permutations of 52 cards taken 2 at a time, and \({}_{52}{P}_{2}=2,652\).
   3. Here we’re looking for the number of permutations of 18 members taken 3 at a time, and \({}_{18}{P}_{3}=4,896\).

Išlaikyti savo darbą

Nemokama paskyra prideda pastabas apie kiekvieną pamoką, įrašą apie tai, ką baigėte, savo išspręstas problemas vienoje vietoje ir mokytoją, kurį galite paklausti apie šį puslapį. Pati matematika yra atvira visiems, kurie yra ar nėra užsiregistravę.

Prisijungti Prisijungti

Čia naudojami simboliai

Bakstelėkite visus simbolius, kad būtų galima apibrėžti visą apibrėžimą, paveikslėlį ir ką reiškia kiekviena raidė.

n!factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.\leqless/greater than or equal
Inequalities that allow equality; < and > exclude it.\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 − μ)/σ.

Kaip vartoti: Permutations

1. Use the Multiplication Rule for Counting to determine the number of permutations.
2. Compute expressions containing factorials.
3. Compute permutations.
4. Apply permutations to solve problems.
5. How many different podium placements (first place, second place, and third place) are possible?
6. How many different complete orders of finish (first place through eighth place) are possible?
7. Let’s start with the first place finisher. How many options are there? Since 8 swimmers are competing, there are 8 possibilities. Once that first swimmer completes the race, there are 7 swimmers left competing for second place. After the second finisher is decided, there are 6 swimmers remaining who could possibly finish in third place. Thus, there are 8 possibilities for first place, 7 for second place, and 6 for third place. The Multiplication Rule for Counting then tells us there are
8. To look at the complete order of finish, we can continue the pattern we can see in part 1 of this example: There are 5 possibilities for fourth place, 4 for fifth place, 3 for sixth place, 2 for seventh place, and then just 1 swimmer is left to finish in eighth place. Using the Multiplication Rule for Counting, we see that there are

Klausimai, kuriuos klausia žmonės

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.

Šio puslapio dalys pritaikytos nuo OpenStax Contemporary Mathematics (CC BY-NC-SA 4.0). Čia yra įtikinamų ir iš naujo paaiškintų klaidų. Kadangi jo šaltinis yra licencijuotas nekomerciniam naudojimui, ši pamoka yra nemokama, nieko neparduoda ir dalijasi pagal tą pačią licenciją.

Daugiau informacijos 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