2 Sets and functions 2.10 Conditions for invertibility 2.12 Inverses and composition

2.11 Permutations

Definition 2.11.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.11.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$ :

Figure 2.12: Diagram of the permutation

f

from the example above.

Figure 2.13: Diagram of the permutation

g

from the example above.

2.11.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.11.2 How many permutations?

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

Theorem 2.11.1.

$|S_{n}|=n!$

Proof.

Instead of counting permutations we will count possible bottom rows of two row notations for elements of $S_{n}$ . 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\}$ .