# 2.10 Permutations

###### Definition 2.10.1.
• A permutation of a set $X$ is a bijection $X\to X$.

• $S_{n}$, the symmetric group on $n$ letters, is the set of all permutations of $\{1,2,\ldots,n\}$.

###### Example 2.10.1.
• For any set $X$, the identity function $\operatorname{id}_{X}:X\to X$ is a permutation.

• The function $f:\{1,2,3\}\to\{1,2,3\}$ given by $f(1)=3,f(2)=2,f(3)=1$ is a permutation. $f$ is an element of $S_{3}$.

• The function $g:\{1,2,3,4\}\to\{1,2,3,4\}$ given by $g(1)=2,g(2)=3,g(3)=4,g(4)=1$ is a permutation. $g$ is an element of $S_{4}$.

Here are some diagrams illustrating the permutations $f$ and $g$:

## 2.10.1 Two row notation

We need a way of writing down elements of $S_{n}$. The simplest is called two row notation. To represent $f\in S_{n}$, you write two rows of numbers. The top row is 1, 2, …, $n$. Then underneath each number $i$ on the top row you write $f(i)$:

 $\begin{pmatrix}1&2&\cdots&n\\ f(1)&f(2)&\cdots&f(n)\end{pmatrix}$

As an example, here are the two row notations for the two permutations of the previous example.

 $\displaystyle f$ $\displaystyle:\begin{pmatrix}1&2&3\\ 3&2&1\end{pmatrix}$ $\displaystyle g$ $\displaystyle:\begin{pmatrix}1&2&3&4\\ 2&3&4&1\end{pmatrix}$

The two row notation for the identity in $S_{n}$ is particularly simple:

 $\begin{pmatrix}1&2&\cdots&n-1&n\\ 1&2&\cdots&n-1&n\end{pmatrix}.$

This is a simple and not-that-efficient notation (it is not feasible to write down an element of $S_{100}$ this way, even if it is a very simple permutation e.g. swaps 1 and 2, leaves 3-100 alone), but it is at least concrete and simple.

## 2.10.2 How many permutations?

$n!$, pronounced n factorial, means $n\times(n-1)\times\cdots\times 2\times 1$.

###### Theorem 2.10.1.

$|S_{n}|=n!$

###### Proof.

We will count how many possible bottom rows of two row notations for elements of $S_{n}$ there are. Because a permutation is a bijection — one-to-one and onto — this bottom row consists of the numbers $1,2,\ldots,n$ in some order. We just need to show that there are exactly $n!$ different ways to order the numbers $1,2,\ldots,n$.

We prove this by induction on $n$. For the base case $n=1$ we have $1!=1$ and it is clear that there is only one way to order a single 1.

For the inductive step, suppose $|S_{n-1}|=(n-1)!$. An ordering of $1,2,\ldots,n$ arises in exactly one way as an ordering of $1,2,\ldots,(n-1)$ with the number $n$ inserted into one of $n$ places (the first, or second, or …, or $n$th position). So the number of such orderings is $|S_{n-1}|$ (the number of ways to choose an ordering of $1,2,\ldots,(n-1)$) times the number of ways to insert an $n$, giving $|S_{n}|=|S_{n-1}|\times n=(n-1)!\times n=n!$. This completes the inductive step. ∎

For example, there are $2!=2$ elements of $S_{2}$: they are

 $\begin{pmatrix}1&2\\ 1&2\end{pmatrix},\begin{pmatrix}1&2\\ 2&1\end{pmatrix}$

The first one is the identity function on $\{1,2\}$.