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,\mathrm{\dots},n\}$.
For any set $X$, the identity function ${\mathrm{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$:
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)$:
$$\left(\begin{array}{cccc}1& 2& \mathrm{\cdots}& n\\ f(1)& f(2)& \mathrm{\cdots}& f(n)\end{array}\right)$$ |
As an example, here are the two row notations for the two permutations of the previous example.
$f$ | $:\left(\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right)$ | ||
$g$ | $:\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 3& 4& 1\end{array}\right)$ |
The two row notation for the identity in ${S}_{n}$ is particularly simple:
$$\left(\begin{array}{ccccc}1& 2& \mathrm{\cdots}& n-1& n\\ 1& 2& \mathrm{\cdots}& n-1& n\end{array}\right).$$ |
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.
$n!$, pronounced n factorial, means $n\times (n-1)\times \mathrm{\cdots}\times 2\times 1$.
$|{S}_{n}|=n!$
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,\mathrm{\dots},n$ in some order. We just need to show that there are exactly $n!$ different ways to order the numbers $1,2,\mathrm{\dots},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,\mathrm{\dots},n$ arises in exactly one way as an ordering of $1,2,\mathrm{\dots},(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,\mathrm{\dots},(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
$$\left(\begin{array}{cc}1& 2\\ 1& 2\end{array}\right),\left(\begin{array}{cc}1& 2\\ 2& 1\end{array}\right)$$ |
The first one is the identity function on $\{1,2\}$.