Your debate team has 5 speakers, and the coach has to pick the speaking order for Friday's round. How many different lineups are possible? That is a question about ordering: putting every member of a group in a line, one after another. Counting orderings is the simplest and most useful skill in combinatorics, and it is the foundation for many probability calculations later in AP Statistics.
Factorials
Orderings are counted with a product that shrinks by one each time, so it has its own name and symbol.
Factorials grow very fast:
$n$
0
1
2
3
4
5
6
7
8
$n!$
1
1
2
6
24
120
720
5,040
40,320
Why $0! = 1$? There is exactly one way to arrange nothing: do nothing. This also keeps the formulas in this chapter working.
Expressions with factorials look scary but simplify nicely, because a bigger factorial contains the smaller one: $9! = 9 \cdot 8 \cdot 7!$. Write out just enough of the larger factorial to reach the smaller one, then cancel.
Practice★☆☆Not started
Calculate the numerical value of the following expressions with factorials: $\frac{8!}{5! \cdot 3!}$ and $\frac{12!}{10!}$.
Calculate the numerical value of the following expressions with factorials: $\frac{8!}{5! \cdot 3!}$ and $\frac{12!}{10!}$.
Fill the positions one at a time. The first position has $n$ choices. Once it is filled, the second position has $n-1$ choices left, then $n-2$, and so on until only $1$ object remains for the last position. By the multiplication principle:
A group of $6$ friends goes to the theater and buys tickets for consecutive seats in the same row. In how many different ways can they sit to enjoy the play?
A group of $6$ friends goes to the theater and buys tickets for consecutive seats in the same row. In how many different ways can they sit to enjoy the play?
During a school athletics competition, $7$ runners reach the finish line without any draws occurring. How many different rankings can occur at the end of the race?
During a school athletics competition, $7$ runners reach the finish line without any draws occurring. How many different rankings can occur at the end of the race?
To set up a secure password, an application requires using exactly the characters $A, B, C, 1, 2$, without repeating any of them. How many different passwords can be…
To set up a secure password, an application requires using exactly the characters $A, B, C, 1, 2$, without repeating any of them. How many different passwords can be created in the system?
Often part of the arrangement is decided in advance: two friends who must sit together, someone who must go first, or someone who can't be next to someone else. Don't plug straight into $n!$. First handle the restriction, then arrange what is left.
Fixed positions. If some positions are already taken, only the remaining objects are arranged in the remaining positions.
Objects that must stay together. Glue them into one block, arrange the block along with the other objects, then arrange the objects inside the block.
Objects that must NOT be together. Use the complement: count all arrangements, then subtract the ones that break the rule.
Alternating patterns. When two kinds of objects must alternate, count each possible pattern, then arrange each kind in its own spots.
Practice★★☆Not started
In the final of an Olympic swimming race, $8$ swimmers participate. If we know for certain which swimmer has won the gold medal and which one has come in last place due…
In the final of an Olympic swimming race, $8$ swimmers participate. If we know for certain which swimmer has won the gold medal and which one has come in last place due to an injury, in how many different ways could the other participants have ranked in the intermediate positions?
Five friends go to the movie theater and sit in adjacent seats. Two of them, Emma and Ethan, want to sit together to share the popcorn. In how many ways can the five…
Five friends go to the movie theater and sit in adjacent seats. Two of them, Emma and Ethan, want to sit together to share the popcorn. In how many ways can the five friends be seated while always fulfilling this condition?
A group consisting of $3$ boys and $3$ girls are going to sit in a row of $6$ seats to watch a concert. In how many ways can they do this if they must sit so that the…
A group consisting of $3$ boys and $3$ girls are going to sit in a row of $6$ seats to watch a concert. In how many ways can they do this if they must sit so that the genders are strictly alternated (boy-girl-boy... or girl-boy-girl...)?
How many different "words" can you make from the letters of ANA? If you pretend the two A's are different ($A_1$ and $A_2$), you get $3! = 6$ arrangements. But $A_1NA_2$ and $A_2NA_1$ both read ANA, so they are really the same word. Each real word gets counted twice.
Practice★★☆Not started
How many different words, whether they make sense or not, can be formed using all the letters of the word "CAMPANA"?
How many different words, whether they make sense or not, can be formed using all the letters of the word "CAMPANA"?
A ship communicates with other vessels using colored flags hoisted vertically on a mast. If it has $3$ red flags, $2$ blue flags, and $1$ yellow flag, all of the same…
A ship communicates with other vessels using colored flags hoisted vertically on a mast. If it has $3$ red flags, $2$ blue flags, and $1$ yellow flag, all of the same size, how many different signals can it send using all the flags at once?
A software engineer wants to form six-digit numerical codes using exactly the following digits in each code: $2, 2, 3, 3, 3, 4$. How many different codes can the system…
A software engineer wants to form six-digit numerical codes using exactly the following digits in each code: $2, 2, 3, 3, 3, 4$. How many different codes can the system program?
In a line, the first and last spots are different. At a round table there is no "first seat": only who sits next to whom matters. If everyone shifts one seat to the right, it is the same arrangement.
For restrictions at a round table, the complement trick still works. Two people are adjacent if they sit next to each other, which you count by gluing them into a block.
Practice★★☆Not started
A family of $6$ members sits down to dinner around a circular table in a restaurant. In how many different ways can they be seated if only the relative position between…
A family of $6$ members sits down to dinner around a circular table in a restaurant. In how many different ways can they be seated if only the relative position between them matters and not the exact chair they occupy in the room?
Eight diplomats meet at an international summit and must sit around a large round table. Two of the representatives are bitter enemies and protocol requires that they do…
Eight diplomats meet at an international summit and must sit around a large round table. Two of the representatives are bitter enemies and protocol requires that they do not sit next to each other. In how many different ways can they be seated at the table fulfilling this restriction?
A delivery cyclist can only move right or up on a street grid. Every shortest route is a sequence of steps R (right) and U (up). Counting routes means counting orderings of a sequence with repeated letters, so the repeated-objects formula applies.
Blocked intersections. If one intersection is closed, count the paths that go through it and subtract them from the total. To count paths through a point C, multiply the number of paths from A to C by the number from C to B.
Practice★★☆Not started
On a city map with streets arranged in a grid, a delivery person on a bicycle must go from point $A$ to point $B$ moving only to the right and upwards. How many…
On a city map with streets arranged in a grid, a delivery person on a bicycle must go from point $A$ to point $B$ moving only to the right and upwards. How many different paths of minimum length can they take to make the delivery?
An autonomous robot moves through a logistics grid from node $A$ to node $B$ advancing exclusively to the right and downwards. Due to floor repairs, node $C$ is blocked…
An autonomous robot moves through a logistics grid from node $A$ to node $B$ advancing exclusively to the right and downwards. Due to floor repairs, node $C$ is blocked and the robot cannot pass through it. How many valid paths exist to complete the route?
Some problems combine the earlier ideas. Take them one step at a time.
Groups that each stay together. Each group is a block. Arrange the blocks first, then arrange the objects inside each block. Multiply all the pieces.
Fixed ends with repeated letters. Place the required letters in the first and last spots, remove them from the list, and use the repeated-objects formula on the letters that remain.
Practice★★★Not started
On a school library shelf, $4$ different Mathematics books, $3$ different Physics books, and $2$ different Chemistry books are going to be placed in a row. If the…
On a school library shelf, $4$ different Mathematics books, $3$ different Physics books, and $2$ different Chemistry books are going to be placed in a row. If the librarian requires that books on the same subject must always remain together forming a block, in how many different ways can they be arranged on the shelf?
How many different words, with or without meaning, can be formed by rearranging all the letters of the word "ESTADISTICA" so that they necessarily start with the letter…
How many different words, with or without meaning, can be formed by rearranging all the letters of the word "ESTADISTICA" so that they necessarily start with the letter $E$ and end with the letter $A$?
Two classic "hard" ideas use only what you already know.
Sum of all numbers made from some digits. Every digit appears in every place (ones, tens, hundreds, …) the same number of times. Add up the contribution of each place.
Position in dictionary (alphabetical) order. Go letter by letter and count how many words must come before yours. For each position, count the smaller available letters, and multiply by the number of ways to arrange the remaining letters.
Practice★★★Not started
Calculate the total sum of all the integers of $4$ different digits that can be formed using exclusively the digits $1, 2, 3$ and $4$.
Calculate the total sum of all the integers of $4$ different digits that can be formed using exclusively the digits $1, 2, 3$ and $4$.
If all possible words, with or without meaning, are generated by permuting the letters of the word "LIBRO" and then strictly ordered alphabetically (as in a dictionary),…
If all possible words, with or without meaning, are generated by permuting the letters of the word "LIBRO" and then strictly ordered alphabetically (as in a dictionary), what exact position will the word "LIBRO" occupy in that list?
To solve an equation with factorials, expand the bigger factorials down to the smallest one, cancel, and you are left with an ordinary polynomial equation. Then check that your answer makes every factorial defined (the numbers inside must be whole numbers $\ge 0$).
Practice★★★Not started
Find the value of the natural number $x$ that satisfies the following equation, justifying your answer mathematically: $P_x = 30 \cdot P_{x-2}$.
Find the value of the natural number $x$ that satisfies the following equation, justifying your answer mathematically: $P_x = 30 \cdot P_{x-2}$.
Simplify the algebraic fractions and solve the following equation containing factorials, finding the value of $x$: $\frac{(x+1)!}{(x-1)!} - \frac{x!}{(x-2)!} = 14$.
Simplify the algebraic fractions and solve the following equation containing factorials, finding the value of $x$: $\frac{(x+1)!}{(x-1)!} - \frac{x!}{(x-2)!} = 14$.