alternative notation choices for \(\permutation{n}{k}\)
Example21.4.1.Visualizing \(\permutation{4}{2}\).
Consider \(A = \{1,2,3,4\}\text{,}\) so that \(n = \card{A} = 4\text{.}\) There are \(4! = 24 \) permutations of \(A\text{.}\)
\(x\)
\(1\)
\(2\)
\(3\)
\(4\)
\(\id_A(x)\)
\(1\)
\(2\)
\(3\)
\(4\)
\(p_1(x)\)
\(1\)
\(2\)
\(4\)
\(3\)
\(p_2(x)\)
\(1\)
\(3\)
\(2\)
\(4\)
\(p_3(x)\)
\(1\)
\(3\)
\(4\)
\(2\)
\(p_4(x)\)
\(1\)
\(4\)
\(2\)
\(3\)
\(p_5(x)\)
\(1\)
\(4\)
\(3\)
\(2\)
\(p_6(x)\)
\(2\)
\(1\)
\(3\)
\(4\)
\(p_7(x)\)
\(2\)
\(1\)
\(4\)
\(3\)
\(p_8(x)\)
\(2\)
\(3\)
\(1\)
\(4\)
\(p_9(x)\)
\(2\)
\(3\)
\(4\)
\(1\)
\(p_{10}(x)\)
\(2\)
\(4\)
\(1\)
\(3\)
\(p_{11}(x)\)
\(2\)
\(4\)
\(3\)
\(1\)
\(x\)
\(1\)
\(2\)
\(3\)
\(4\)
\(p_{12}(x)\)
\(3\)
\(1\)
\(2\)
\(4\)
\(p_{13}(x)\)
\(3\)
\(1\)
\(4\)
\(2\)
\(p_{14}(x)\)
\(3\)
\(2\)
\(1\)
\(4\)
\(p_{15}(x)\)
\(3\)
\(2\)
\(4\)
\(1\)
\(p_{16}(x)\)
\(3\)
\(4\)
\(1\)
\(2\)
\(p_{17}(x)\)
\(3\)
\(4\)
\(2\)
\(1\)
\(p_{18}(x)\)
\(4\)
\(1\)
\(2\)
\(3\)
\(p_{19}(x)\)
\(4\)
\(1\)
\(3\)
\(2\)
\(p_{20}(x)\)
\(4\)
\(2\)
\(1\)
\(3\)
\(p_{21}(x)\)
\(4\)
\(2\)
\(3\)
\(1\)
\(p_{22}(x)\)
\(4\)
\(3\)
\(1\)
\(2\)
\(p_{23}(x)\)
\(4\)
\(3\)
\(2\)
\(1\)
Figure21.4.2.Permutations of a set of size \(4\text{.}\)
Notice that the permutations above have been grouped into pairs, where the two permutations in a given pair have the same two first elements in the same order. From this, we can conclude that there are only \(24/2 = 12\) permutations of size \(k=2\) from \(A\text{.}\)
One way to construct an ordered list of \(k\) elements from a set \(A\text{,}\) where \(\card{A} = n\text{,}\) is as in Example 21.4.1. Form an ordered list of all the elements of \(A\) (\(n!\) ways), and then take the first \(k\) elements from that list. But we get the same ordered list of length \(k\) no matter how the last \(n-k\) elements are ordered. That is, we consider any two orderings of all \(n\) elements to be equivalent if the first \(k\) elements in the list are the same between the two. As there are \((n-k)!\) different ways the last \(n - k\) elements could be ordered while keeping the first \(k\) elements the same, each equivalence class has size \((n - k)!\text{.}\) Applying the Division Rule, we obtain the desired formula
\begin{equation*}
\permutation{n}{k}
= \frac{\ncardop \{ \text{orderings of all } n \text{ elements} \} }{\ncardop \{ \text{reorderings of the last } n - k \text{ elements} \} }
= \frac{n!}{(n - k)!}\text{.}
\end{equation*}
Remark21.4.4.
The number \(\permutation{n}{n}\) represents the number of ways to construct an ordered list of \(n\) elements chosen from a set of \(n\) elements, so \(P(n,n) = n!\text{.}\) The convention \(0! = 1\) ensures that our formula for \(P(n,k)\) expressed in Theorem 21.4.3 remains valid in the case \(k = n\text{.}\)
Worked Example21.4.5.Elections.
A class of twenty discrete mathematics students decides to elect a class president and vice-president. How many possible outcomes to the election process are there?
An arbitrary way to elect students to these offices would be to line all the students up and choose the first two students in line to be the president and vice-president, respectively. Therefore, there are
You go to the horsetrack to bet on a race. From a field of nine horses, how many ways are there to make a “Trifecta” bet (i.e. specify the first three finishers in order)?
Fix an ordering \(a_1,a_2,\dotsc,a_k\) of the elements of \(A\text{.}\) Then from any ordering \(b_1, b_2, \dotsc, b_k\) of size \(k\) from \(B\text{,}\) we get an injective function \(\ifuncdef{f}{A}{B}\) by the following table of values.
\(x\)
\(a_1\)
\(a_2\)
\(\cdots\)
\(a_k\)
\(f(x)\)
\(b_1\)
\(b_2\)
\(\cdots\)
\(b_k\)
That is, every permutation of \(B\) of size \(k\) corresponds to an injection \(\ifuncdef{f}{A}{B}\text{,}\) and so the number of such injections is \(\permutation{n}{k}\text{.}\)
