Definition 4.3.1.1.
A permutation of a set of distinct objects is an ordered arrangement of these objects.
Subsection 4.3.1 Permutations
Example 4.3.1.2. Permutations of a set with three elements.
Let \(S = \{x, y, z\}\text{.}\) The permutations of \(S\) are
\begin{equation*}
\{xyz,xzy,yxz,yzx,zxy,zyx\}.
\end{equation*}
Definition 4.3.1.3.
An ordered arrangement of \(r\) elements of a set is called an \(r\)-permutation . The number of \(r\)-permutations of a set of size \(n\) is denoted \(P(n,r)\) .
Remark 4.3.1.4.
Example 4.3.1.5. Permutations of \(\{a,b,c,d\}\).
Let \(S = \{a,b,c,d\}\text{.}\)
-
As an exercise, try to list the permutations of \(S\text{.}\) There
Theorem 4.3.1.6.
Let \(n\) and \(r\) be integers such that \(0\leq r\leq n\text{.}\) Then
\begin{equation*}
P(n,r) = \frac{n!}{(n - r)!} = n(n-1)(n - 2) \cdots (n - (r-1)).
\end{equation*}
Proof.
Constructing an \(r\)-permutation, can be broken down into a sequence of \(r\) tasks. First, we select the first term in the arrangement. There are \(n\) ways to do this. Then, we select the second term in the arrangement. There are \(n-1\) ways to do this because one of the ways is no longer valid as it was already used in the previous step. Similarly, there are \(n-2\) ways to select the third term, and so on. The result then follows by the Product Rule.
Remark 4.3.1.7.
Example 4.3.1.8. Gold, Silver, and Bronze finishers.
Suppose there are eight runners in a race. How many different ways can we have Gold, Silver, and Bronze finishers, assuming no ties?
Remark 4.3.1.9.
For \(n\) and \(k\) such that \(0\leq k\leq n\text{,}\) cancellation gives
\begin{equation*}
\frac{n!}{k!} = n(n - 1) \cdots (k + 1).
\end{equation*}
Example 4.3.1.10. Permutations of the alphabet.
Let \(S = \{a,b,c,\dots,x, y, z\}\text{.}\) The number of permutations of \(S\) is
\begin{equation*}
P(26,26) = 26!= {403291461126605635584000000}.
\end{equation*}
Example 4.3.1.11. Permutations of the alphabet with \(abc\).
We can view this as a different problem. We want permutations of
\begin{equation*}
S' = \{abc, d, e, f, \dots, x, y, z\}.
\end{equation*}
Then \(\size{S'} = 24\text{,}\) and
\begin{equation*}
P(24,24) = 24! = {620448401733239439360000}.
\end{equation*}
Example 4.3.1.12. Seven people.
How many ways are there to arrange seven people in from a group of ten (including me) in a row if I need to be one of the seven?
Solution.
We break this into tasks. First select the position for me. There are \(7\) choices. The remaining spots are ordered. We need a \(6\)-permutation of the set of 9 remaining people. There are
\begin{equation*}
P(9,6) = \frac{9!}{(9 - 6)!} = 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5
\cdot 4 = {60480}
\end{equation*}
such permutations. By the Product Rule, there are \(7 \cdot 60480 = {423360}\) arrangements.
