Permutations of n Items Taken r at a Time
Eight sprinters line up for the 100-meter dash at the state track meet. Gold, silver, and bronze go to the top three finishers, with no ties. How many different podiums are possible? You are not lining up all 8 runners, just choosing 3 of them and putting them in order. That kind of counting shows up all the time: passwords, PINs, license plates, class officers. It is also the backbone of probability, because the denominator of many probabilities is "how many outcomes are there?"
Filling slots: ordered choices without repetition
Draw one slot for each position you need to fill. Then count how many choices you have for each slot and multiply. This is the Fundamental Counting Principle: if one task can be done in $a$ ways and, after that, a second task can be done in $b$ ways, then both tasks can be done in $a \times b$ ways.
For the podium, gold can go to any of the 8 runners. Once gold is taken, silver has 7 choices left. Bronze has 6.
That is the answer to the opening question: 336 different podiums. Order matters here, because "gold, silver, bronze" is a different result from "bronze, silver, gold" with the same three runners.
Why the factorial form? Multiplying $n(n-1)\cdots(n-r+1)$ by $(n-r)!$ gives $n!$, so dividing by $(n-r)!$ cuts off the extra factors you do not need. On a TI-84, use MATH → PRB → nPr.
If $r = n$ you are arranging everything, and ${}_nP_n = n!$ (that is the previous section on permutations).
In a $100\text{ m}$ sprint race, $8$ athletes participate. In how many different ways can the gold, silver, and bronze medals be distributed knowing that there can be no…
In a $100\text{ m}$ sprint race, $8$ athletes participate. In how many different ways can the gold, silver, and bronze medals be distributed knowing that there can be no draws?
Five friends go to the movie theater and find a row with $4$ consecutive free seats. In how many different ways can they sit to watch the movie?
Five friends go to the movie theater and find a row with $4$ consecutive free seats. In how many different ways can they sit to watch the movie?
In an art gallery, $2$ paintings selected from a private collection of $7$ artworks are going to be exhibited. One will be placed on the left wall of the room and the…
In an art gallery, $2$ paintings selected from a private collection of $7$ artworks are going to be exhibited. One will be placed on the left wall of the room and the other on the right wall. In how many different ways can this exhibition be organized?
Repetition allowed: $n^r$
Now suppose an item can be used again. When you roll a die 4 times, a 6 can come up every time. Nothing is "used up," so every slot has the same number of choices. Some problems call this counting permutations with repetition.
We toss a coin $6$ consecutive times and record the exact sequence of heads and tails obtained. How many different sequences can be formed?
We toss a coin $6$ consecutive times and record the exact sequence of heads and tails obtained. How many different sequences can be formed?
We want to paint $3$ letterboxes aligned on a street. We have $4$ different colors available (red, green, blue, and yellow). If we can repeat colors on different…
We want to paint $3$ letterboxes aligned on a street. We have $4$ different colors available (red, green, blue, and yellow). If we can repeat colors on different letterboxes, in how many different ways can we paint them?
A multiple-choice exam consists of $5$ questions. Each question has $3$ answer options (A, B, and C) of which only one can be marked. If a student answers all the…
A multiple-choice exam consists of $5$ questions. Each question has $3$ answer options (A, B, and C) of which only one can be marked. If a student answers all the questions, in how many different ways can the exam be filled in?
Which formula? Repeat or not, and does order matter?
Before you calculate, ask two questions.
-
Can the same item be used more than once?
-
Does swapping two items give a different result?
If order does not matter (a committee, a hand of cards), you use a different tool, which comes in the next sections. On this page, order always matters.
A reading club has $9$ members. They must elect a board of directors consisting of a president, a vice president, and a secretary. Since the roles are different and each…
A reading club has $9$ members. They must elect a board of directors consisting of a president, a vice president, and a secretary. Since the roles are different and each person can only hold one, in how many ways can the board be formed?
In a basketball league, $14$ teams participate. Each team must play against all the others twice throughout the year (one home game and one away game). How many games…
In a basketball league, $14$ teams participate. Each team must play against all the others twice throughout the year (one home game and one away game). How many games will be played in total during the whole season?
A bicycle security padlock has $3$ independent wheels, each numbered from $0$ to $9$. Calculate the difference between the total number of possible combinations…
A bicycle security padlock has $3$ independent wheels, each numbered from $0$ to $9$. Calculate the difference between the total number of possible combinations (allowing repetition) and the number of combinations where the three digits must be strictly different.
Several stages and "or" cases
Many real problems combine blocks. A license plate might have digits followed by letters. Just multiply the counts of the blocks, since each block is another group of slots.
Sometimes the options split into separate cases that cannot happen together, like signals of length 1, length 2, or length 3. Count each case separately and add.
The license plate system of a country is formed by a block of $4$ digits (from $0$ to $9$) followed by a block of $2$ letters chosen from an alphabet of $20$ consonants.…
The license plate system of a country is formed by a block of $4$ digits (from $0$ to $9$) followed by a block of $2$ letters chosen from an alphabet of $20$ consonants. Repetition of characters is allowed in both blocks. How many different license plates can be issued in total with this format?
In Morse code, letters are represented by sequences of dots and dashes. How many different signals can be formed using a maximum of $3$ symbols per signal?
In Morse code, letters are represented by sequences of dots and dashes. How many different signals can be formed using a maximum of $3$ symbols per signal?
To access a secure database, a password of $5$ characters is required. For security, the system requires the first two characters to be vowels (repetition is allowed)…
To access a secure database, a password of $5$ characters is required. For security, the system requires the first two characters to be vowels (repetition is allowed) and the last three characters must be numbers from $0$ to $9$ (with no repetition). How many different passwords meet this format?
Restrictions: fill the pickiest slot first
When a slot has a special requirement (even number, nonzero first digit, must be a girl), fill that slot first. Otherwise the choices for the other slots get tangled up with it.
Using the digits $\{1, 2, 3, 4, 5, 6, 7\}$, how many even numbers of $3$ digits can be formed if it is not allowed to repeat any digit in the same number?
Using the digits $\{1, 2, 3, 4, 5, 6, 7\}$, how many even numbers of $3$ digits can be formed if it is not allowed to repeat any digit in the same number?
How many numbers of $4$ different digits can be formed using only the digits $\{0, 1, 2, 3, 4, 5\}$? Keep in mind that, by definition, a valid number cannot start with…
How many numbers of $4$ different digits can be formed using only the digits $\{0, 1, 2, 3, 4, 5\}$? Keep in mind that, by definition, a valid number cannot start with the digit $0$.
A class consists of $6$ boys and $5$ girls. A committee consisting of a president, vice president, and secretary is to be chosen. The presidency must be held by a girl,…
A class consists of $6$ boys and $5$ girls. A committee consisting of a president, vice president, and secretary is to be chosen. The presidency must be held by a girl, the vice presidency by a boy, and the secretary can be any of the remaining students. In how many ways can the committee be chosen?
Fixed positions and linked slots
Sometimes one or more slots are already decided. A slot with only one choice contributes a factor of 1, so you simply count the rest. Be careful to ask whether the fixed items can still swap places among themselves.
In computing, a byte is a sequence of $8$ bits (where each bit can be a $0$ or a $1$). How many different bytes exist that start exactly with the sequence $10$?
In computing, a byte is a sequence of $8$ bits (where each bit can be a $0$ or a $1$). How many different bytes exist that start exactly with the sequence $10$?
A company has $8$ employees and must assign $5$ different tasks to $5$ different employees (one task per person). If it is known that the first task must necessarily be…
A company has $8$ employees and must assign $5$ different tasks to $5$ different employees (one task per person). If it is known that the first task must necessarily be performed by the most senior employee, in how many ways can the tasks be distributed?
Five people board a train car in which there are $8$ free seats. Two of these people are a couple and insist on sitting in a specific pair of adjacent seats next to the…
Five people board a train car in which there are $8$ free seats. Two of these people are a couple and insist on sitting in a specific pair of adjacent seats next to the window. Knowing that the couple cares about who sits by the window and who sits by the aisle, in how many different ways can the five people occupy the seats?
Linked slots: patterns and neighbors
In some problems one slot determines another, or its choices depend on the slot next to it. Look for the slots that are free, and count only those.
-
A palindrome reads the same forward and backward. In a 5-digit palindrome, digit 5 must equal digit 1 and digit 4 must equal digit 2, so only the first three digits are free.
-
A "no two adjacent the same" rule means each slot after the first has one fewer choice, namely every color except the one just used.
How many numbers of $4$ digits can be formed with the digits $\{1, 2, 3, 4, 5\}$ (allowing repeated digits) that are strictly greater than $3000$?
How many numbers of $4$ digits can be formed with the digits $\{1, 2, 3, 4, 5\}$ (allowing repeated digits) that are strictly greater than $3000$?
A palindromic number is one that reads the same from left to right as from right to left (for example, $35853$). How many palindromic numbers of $5$ digits can be formed…
A palindromic number is one that reads the same from left to right as from right to left (for example, $35853$). How many palindromic numbers of $5$ digits can be formed using only the digits from $1$ to $9$?
A flag with $4$ vertical stripes is to be designed. There are $5$ different colors available. In how many ways can the flag be colored if the only condition is that two…
A flag with $4$ vertical stripes is to be designed. There are $5$ different colors available. In how many ways can the flag be colored if the only condition is that two adjacent stripes (next to each other) cannot have the same color?
Working backward: equations with ${}_nP_r$
Sometimes you know the total count and need $n$. Write ${}_nP_2 = n(n-1)$, set it equal to the total, and solve the quadratic equation. You can solve by factoring or the quadratic formula, as in Math 8 and Algebra 1.
The same idea works when the equation compares two counts. For example, if $n^2$ (repetition allowed) exceeds $n(n-1)$ (no repetition) by 12, then
$$n^2 - n(n-1) = 12 \quad\Rightarrow\quad n^2 - n^2 + n = 12 \quad\Rightarrow\quad n = 12.$$The $n^2$ terms cancel, so you get a linear equation and no factoring is needed.
A chess tournament is played as a double round-robin (each player faces everyone else twice, alternating the color of the pieces). If it is known that a total of $90$…
A chess tournament is played as a double round-robin (each player faces everyone else twice, alternating the color of the pieces). If it is known that a total of $90$ games have been played, set up the corresponding equation using the formula for permutations and find how many players took part in the tournament.
Knowing that the number of permutations with repetition of $x$ elements taken $2$ at a time exceeds by $12$ the number of permutations without repetition of the same $x$…
Knowing that the number of permutations with repetition of $x$ elements taken $2$ at a time exceeds by $12$ the number of permutations without repetition of the same $x$ elements taken $2$ at a time, set up the corresponding mathematical equation and find the value of $x$.
Summary
Back to the start: the 8 sprinters can finish gold, silver, bronze in ${}_8P_3 = 8 \cdot 7 \cdot 6 = 336$ ways.