Definition 2.5.1.
A permutation of a finite set \(A\) is a bijection from \(A\) to itself. The set of permutations of \([n]\) is denoted by \(\ss_n\) and is called the symmetric group on \(n\) elements.
Section 2.5 Permutations
Our next object of study is permutations of a finite set. Permutations are important in mathematics, computer science, social sciences, and beyond.
Since a permutation in \(\ss_n\) is a bijection, it is a function from \([n]\) to itself. There are multiple ways to represent a permutation. At first, we will use one-line notation. Given a permutation \(\pi\in \ss_n\text{,}\) which is a bijection
\begin{equation*}
\pi:[n]\to [n] \, ,
\end{equation*}
we define \(\pi_i:=\pi(i)\) and then the one-line notation for \(\pi\) is
\begin{equation*}
\pi = \pi_1\pi_2\pi_3\cdots \pi_n \, .
\end{equation*}
Example 2.5.2.
Suppose \(\pi\in\ss_5\) is defined by
\begin{equation*}
\pi(1)=3, \, \pi(2)=5, \, \pi(3)=2, \, \pi(4)=1 \, ,\pi(5)=4 \, .
\end{equation*}
Then the one-line notation for \(\pi\) is
\begin{equation*}
\pi=35214 \, .
\end{equation*}
We would write \(\pi_3=2\) for this permutation.
Checkpoint 2.5.3.
Write down all of the elements of \(\ss_n\) for \(n=1,2,3,4\text{.}\) How do you know that you did not miss any?
Checkpoint 2.5.4.
What strategy/strategies did you develop to systematically list the elements of the symmetric group?
Recall that \(n!:=n\cdot (n-1)\cdot (n-2)\cdots 3\cdot 2\cdot 1\) is the factorial of \(n\text{.}\)
Theorem 2.5.5.
\(|\ss_n|=n!\)
We will give two proofs, one using combinatorial reasoning, and one using recursion.
Combinatorial Reasoning Proof of Theorem 2.5.5.
For any permutation \(\pi\in\ss_n\text{,}\) \(\pi_1\) can be any of \(\{1,2,3,\ldots,n\}\text{.}\) Thus, there are \(n\) choices for \(\pi_1\text{.}\) Once \(\pi_1\) is known, then \(\pi_2\) can be any of the remaining values, and there are \(n-1\) possible values remaining. Thus, there are \(n\cdot (n-1)\) possibilities for \(\pi_1\pi_2\text{.}\) Continuing in this way, we have \(n-2\) possibilities for \(\pi_3\text{,}\) then \(n-3\) possibilities for \(\pi_4\text{,}\) etc., and so on until there is only one possible value for \(\pi_n\text{.}\) Thus, there are \(n!\) permutations in \(\ss_n\text{.}\)
Checkpoint 2.5.6.
Discuss this proof. Does it make sense? Why or why not? Verify that your understanding is correct by working through one or two small examples.
Recursive Proof of Theorem 2.5.5.
First, we can check that this is true for small values of \(n\text{.}\) So, we will use a strategy we have used before: use that this is true for \(\ss_1\) to deduce that it is true for \(\ss_2\text{,}\) then use that it is true for \(\ss_2\) to deduce that it is true for \(\ss_3\text{,}\) and so on. In this way, we will show it is true for every \(n\text{.}\)
For each \(\pi\in \ss_n\text{,}\) the value \(n\) is at some position in \(\pi\text{.}\) Let \(X_i\) be the set of permutations in \(\pi\in \ss_n\) with \(\pi_i=n\text{,}\) which we can also write as:
\begin{equation*}
X_i:=\{\pi\in \ss_n:\pi_i=n\}
\end{equation*}
Since \(n\) is in only one position in each permutation, we have that
\begin{equation*}
\ss_n = X_1\uplus X_2\uplus \cdots \uplus X_n \, .
\end{equation*}
Therefore,
\begin{equation*}
|\ss_n|=|X_1| + |X_2| + \cdots + |X_n| \, .
\end{equation*}
For any \(i\text{,}\) removing \(n\) from each permutation in \(X_i\) results in a copy of \(\ss_{n-1}\text{.}\) Thus, \(X_i\) is obtained by taking \(\ss_{n-1}\) and inserting an \(n\) in the \(i\)-th position of each permutation. Thus, \(|X_i|=(n-1)!\) for every \(i\text{,}\) and hence
\begin{equation*}
|\ss_n|= n\cdot (n-1)! = n! \, .
\end{equation*}
Checkpoint 2.5.8.
Discuss this proof. Does the proof strategy make sense? Why or why not? Clarify any points of confusion by working through one or two small examples.
