Theorem 21.3.1.
For \(\card{A} = n\text{,}\) there are \(n!\) permutations on \(A\text{.}\)
Section 21.3 Counting permutations
Informal proof.
We want to count the number of ways of constructing an ordered list of the \(n\) elements of \(A\text{.}\) There are \(n\) ways to choose the first element in the list, \(n-1\) ways to choose the second, \(n-2\) ways to choose the third, and so on, ending at a single way to choose the \(\nth\text{.}\) By the Multiplication Rule, there are
\begin{equation*}
n \cdot (n - 1) \cdot (n - 2) \cdot \dotsb \cdot 1 = n!
\end{equation*}
ways to construct such a list.
Formal proof.
By induction.
Base case \(n=1\).
If \(\card{A} = 1\text{,}\) then \(A\) consists of a single element, say \(A = \{a\}\text{.}\) There is only one possible permutation of \(A\text{,}\) and that is the identity function \(\funcdef{\id_A}{A}{A}\) defined by \(\id_A(a) = a\text{.}\) Thus, we have verified that there is \(1! = 1\) permutation of \(A\text{.}\)
Induction step.
Let \(k \ge 1\) be a fixed integer. Our induction hypothesis is to assume that if \(B\) is any set with \(\card{B} = k\) elements, then there are \(k!\) permutations on \(B\text{.}\) We want to use this hypothesis to prove that if \(A\) is a set with \(\card{A} = k+1\) elements, then there are \((k+1)!\) permutations on \(A\text{.}\)
Write \(A = \{ a_0, a_1, \dotsc, a_k \}\) and \(B = \{ a_1, a_2, \dotsc, a_k \}\text{.}\) Then \(B\) is a subset of \(A\) that contains \(k\) elements, and so by our induction hypothesis there are \(k!\) permutations on \(B\text{.}\) For every such permutation of \(B\text{,}\) we can construct \(k+1\) permutations of \(A\) by “inserting” \(a_0\) at different positions in the output list. For example, consider how the identity permutation on \(B\) can be turned into \(k+1\) different permutations on \(A\) — see Figure 21.3.2.
| \(x\) | \(a_1\) | \(a_2\) | \(a_3\) | … | \(a_{k-1}\) | \(a_k\) |
| \(\id_B(x)\) | \(a_1\) | \(a_2\) | \(a_3\) | … | \(a_{k-1}\) | \(a_k\) |
\begin{equation*}
\downarrow
\end{equation*}
| \(x\) | \(a_0\) | \(a_1\) | \(a_2\) | \(a_3\) | … | \(a_{k-1}\) | \(a_k\) |
| \(\id_B^{(0)}(x) = \id_A(x)\) | \(a_0\) | \(a_1\) | \(a_2\) | \(a_3\) | … | \(a_{k-1}\) | \(a_k\) |
| \(\id_B^{(1)}(x)\) | \(a_1\) | \(a_0\) | \(a_2\) | \(a_3\) | … | \(a_{k-1}\) | \(a_k\) |
| \(\id_B^{(2)}(x)\) | \(a_1\) | \(a_2\) | \(a_0\) | \(a_3\) | … | \(a_{k-1}\) | \(a_k\) |
| \(\id_B^{(3)}(x)\) | \(a_1\) | \(a_2\) | \(a_3\) | \(a_0\) | … | \(a_{k-1}\) | \(a_k\) |
| \(\vdots\) | \(\vdots\) | ||||||
| \(\id_B^{(k-1)}(x)\) | \(a_1\) | \(a_2\) | \(a_3\) | \(a_4\) | … | \(a_0\) | \(a_k\) |
| \(\id_B^{(k)}(x)\) | \(a_1\) | \(a_2\) | \(a_3\) | \(a_4\) | … | \(a_k\) | \(a_0\) |
Each of the \(k!\) permutations of \(B\) can be used to construct \(k+1\) permutations of \(A\text{,}\) in the same fashion as we have above for the identity permutation of \(B\text{.}\) So we have in total \((k+1) \cdot k! = (k+1)!\) permutations of \(A\text{,}\) as required.
Remark 21.3.3.
When applying the method of mathematical induction in the formal proof, we began our base case at \(n = 1\text{.}\) But the formula \(n!\) is still valid for the number of permutations of the empty set. In this case, \(n = 0\) and so \(n! = 0! = 1\) by Convention 21.1.3. And there is indeed exactly one permutation of the empty set — the empty function. (See Statement 2 of Proposition 12.1.6.)
Each of the provided proofs for Theorem 21.3.1 above contains an idea that is of practical use in counting collections.
- In the informal proof, we used the Multiplication Rule to count the number of ways to construct an ordered list, where the tasks in the construction are choosing the elements in the list one at a time. (We used this similar thinking often in Chapter 20, though we didn’t explicitly connect the Multiplication Rule to ordered lists.)
- In the formal proof, we used the idea of “inserting” an object into an existing ordered list to create a new ordered list.
Worked Example 21.3.4. Distributing items.
For a class of twenty students, in how many different orders can a professor hand back marked tests:
- In total?
- If Karishma’s test must be handed back first?
- If Elizabeth’s and Ruijing’s tests cannot immediately follow one another?
Solution.
- A test distribution order is the same thing as a permutation of the students in the class, so there are \(20!\) different handback orders (approximately \(2.4\) quintillion).
- This is just the number of ways of ordering the remaining nineteen students’ papers, which is \(19!\) (approximately \(122\) quadrillion).
- It is easier to count the ways that they do follow each other. One way to do this is as follows. Remove Elizabeth’s test from the pile. There are now \(19!\) ways to order the remaining nineteen papers. There are two ways to insert Elizabeth’s test back into any such ordering — either immediately before or after Ruijing’s paper. So there are \(2 \cdot 19!\) orderings we do not want. Therefore, applying the Subtraction Rule yields answer\begin{equation*} 20! - 2 \cdot 19! = 20 \cdot 19! - 2 \cdot 19! = 18 \cdot 19!\text{.} \end{equation*}
Worked Example 21.3.5. Words using the entire alphabet.
For an alphabet \(\Sigma\) with \(\card{\Sigma} = n\text{,}\) how many words in \(\words{\Sigma}\) contain each element of the alphabet exactly once?
Solution.
Here we just want to order all the elements of \(\Sigma\) into a word, so the answer is \(n!\text{.}\)
Remark 21.3.6.
Worked Example 21.3.5 justifies the convention \(0! = 1\text{,}\) since if \(\card{\Sigma} = 0\text{,}\) then \(\words{\Sigma}\) contains exactly one word: the empty word \(\emptyword\text{.}\) And in this case it is vacuously true that \(\emptyword\) contains each element of \(\Sigma\) exactly once.
Worked Example 21.3.7. Counting total orders.
If \(\card{A} = n\text{,}\) how many different total orders on \(A\) exist?
Solution.
Specifying a total order on \(A\) really just means ordering the elements of \(A\text{:}\)
\begin{equation*}
a_1 \le a_2 \le a_3 \le \dotsb \le a_n.
\end{equation*}
So there are \(n!\) possible total orders.
Worked Example 21.3.8. Counting colour patterns.
How many different colour patterns can we obtain by placing three red bottles and five blue bottles on a shelf? (Assume the bottles are indistinguishable except by colour.)
Solution.
Let’s use the Division Rule, where first we will count a more structured collection. If the bottles of the same colour were distinguishable from each other, we would have \(8!\) ways of lining them up on the shelf. Assuming indistinguishability, we now consider two orderings with the same colour pattern but mixed up red and/or blue bottles to be equivalent. For example, the two orderings
\begin{gather*}
\mathrm{R}_1 \; \mathrm{B}_1 \; \mathrm{B}_2 \; \mathrm{R}_2 \; \mathrm{R}_3 \; \mathrm{B}_3 \; \mathrm{B}_4 \; \mathrm{B}_5, \\
\mathrm{R}_2 \; \mathrm{B}_5 \; \mathrm{B}_3 \; \mathrm{R}_1 \; \mathrm{R}_3 \; \mathrm{B}_1 \; \mathrm{B}_4 \; \mathrm{B}_2,
\end{gather*}
of distinguishable bottles create the same colour pattern, and so are equivalent. Once red and blue bottle positions are determined, we can permute the reds (\(3!\) ways) and blues (\(5!\) ways) independently, so each equivalence class inside the collection of orderings of distinguishable bottles contains \(3! \cdot 5!\) equivalent orderings. Applying the Division Rule, we arrive at
\begin{equation*}
\frac{8!}{3! \cdot 5!} = \frac{8\cdot 7 \cdot 6}{3 \cdot 2} = 56
\end{equation*}
possible colour patterns.
Worked Example 21.3.9. Circular orderings.
How many different seating arrangements of ten people around a round table are possible, if no one is considered to be at the “head” or “foot” of the table?
Solution 1.
Solution 2.
Let’s use the Division Rule, where first we will count a more structured collection. There are \(10!\) ways to line the \(10\) people up. Wrapping the end of the line around to meet the beginning forms a circular seating arrangement. But “rotating” around the line (\(10\) possible rotations) yields an equivalent circular seating arrangement. So the answer is
\begin{equation*}
\frac{10!}{10} = 9! \text{.}
\end{equation*}
Force one particular person to always be the “start” of the seating arrangement, no matter what physical seat they are sitting in, and ignoring the fact that a circular arrangement really has no “start.” Then there are \(9!\) ways to arrange the remaining \(9\) people around the table starting from the seat to the left of the “start” person.
