Permutation

Definition 1. A function $ƒ:A\to B$is called
$1$) injective (or one-to-one) if $ƒ\left(x\right)=ƒ\left(y\right)$ for some $x,y\in A$necessarily implies that $x=y$
$2$) surjective (or onto) if for each $b\in B$ there exists $a\in A$ such that $ƒ\left(a\right)=b$
$3$) bijective if $ƒ$ is both injective and surjective.

Definition 2. Let $ƒ:A\to B$ and $g:B\to C$ be functions. Then, the composition of functions, denoted $ƒ\circ g$, is a function from A to C defined as

$(g\circ ƒ)\left(x\right)\stackrel{\scriptscriptstyle\mathrm{def}}{=}g(ƒ\left(x\right))$ for all $x\in A$.

Lemma 1. Let $ƒ:A\to B$, $g:B\to C$ and $h:C\to D$ be functions. Then:
$1$) $h\circ (g\circ ƒ)=(h\circ g)\circ ƒ$, that is, function composition is associative;
$2$)if $ƒ$ and $g$ are injective then $g\circ ƒ$ is injective;
$3$)if $ƒ$ and $g$ are surjective then $g\circ ƒ$ is surjective;
$4$)if $ƒ$ and $g$ are bijective then $g\circ ƒ$ is bijective.
Proof. $1$) By Definition $2$, for any $x\in A$ we have
$\{\begin{array}{c}(h\circ (g\circ ƒ))\left(x\right)=h((g\circ ƒ)\left(x\right))=h(g(ƒ\left(x\right)))\\ ((h\circ g)\circ ƒ)\left(x\right)=(h\circ g)(ƒ\left(x\right))=h(g(ƒ\left(x\right)))\end{array}\Rightarrow (h\circ (g\circ ƒ))\left(x\right)=((h\circ g)\circ ƒ)\left(x\right)$
$2$) If $(g\circ ƒ)\left(x\right)=(g\circ ƒ)\left(y\right)$ for some $x,y\in A$ then (since $g$ is injective) we have $ƒ\left(x\right)=g\left(y\right)$which implies (since f is injective) that $x=y$.
$3$) Let $c$ be an element of $C$. Then (since $g$ is surjective) there exists $b\in B$ such that $g\left(b\right)=c$. Since $ƒ$ is surjective, there exists $a\in A$ such that $ƒ\left(a\right)=b$. Therefore, we have $(g\circ ƒ)\left(a\right)=g(ƒ\left(a\right))=g\left(b\right)=c$.
4) Follows immediately from $2$), $3$) and Item $3$ of Definition 1.

Definition 3. A function $ƒ:\left[n\right]\to \left[n\right]$ is called a permutation on n elements if $ƒ$ is bijective. The set of all permutations on n elements we denote $S_n$. For example, functions ${ƒ}_1,{ƒ}_2:\left[3\right]\to \left[3\right]$ defined by ${ƒ}_1\left(1\right)=2$, ${ƒ}_1\left(2\right)=3,{ƒ}_1\left(3\right)=1$ and ${ƒ}_2\left(1\right)=3,{ƒ}_2\left(2\right)=2,{ƒ}_2\left(3\right)=1$ are elements of $S_3$. One way to denote a permutation $ƒ\in S_n$ is to use so called two-line notation. In two-line notation (or two-row notation) of a permutation $ƒ\in S_n$, one lists the elements of $\left[n\right]$ in the first row, and for each one its image bellow it in the second row, that is
$\left(1\right)$ $ƒ=\left[\begin{array}{ccccc}{i}_1& i_2& i_3& \dots & i_n\\ ƒ\left(i_1\right)& ƒ\left(i_2\right)& ƒ\left(i_3\right)& \dots & ƒ\left(i_n\right)\end{array}\right]$
where $(i_1,i_2,i_3,\dots ,i_n)$ is an ordered list of elements of $\left[n\right]$ in which each element of $\left[n\right]$ occurs only once. For example, functions ${ƒ}_1,{ƒ}_2\in S_3$ from above can be written in two-line notation in one of the following ways:
${ƒ}_1=\left[\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right]=\left[\begin{array}{ccc}1& 3& 2\\ 2& 1& 3\end{array}\right]=\left[\begin{array}{ccc}3& 2& 1\\ 1& 3& 2\end{array}\right]=\left[\begin{array}{ccc}2& 1& 3\\ 3& 2& 1\end{array}\right]=\left[\begin{array}{ccc}2& 3& 1\\ 3& 1& 2\end{array}\right]=\left[\begin{array}{ccc}3& 1& 2\\ 1& 2& 3\end{array}\right]$
and
${ƒ}_2=\left[\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right]=\left[\begin{array}{ccc}1& 3& 2\\ 3& 1& 2\end{array}\right]=\left[\begin{array}{ccc}3& 2& 1\\ 1& 2& 3\end{array}\right]=\left[\begin{array}{ccc}2& 1& 3\\ 2& 3& 1\end{array}\right]=\left[\begin{array}{ccc}2& 3& 1\\ 2& 1& 3\end{array}\right]=\left[\begin{array}{ccc}3& 1& 2\\ 1& 3& 2\end{array}\right]$
Note that
1. in the first row of two-line notation (1), the elements of $\left[n\right]$ may appear in any order;
2. $n$ distinct objects can be arranged in an ordered line in $n!$ ways.
This immediately implies the following:
Statement 1. There are $n!$ permutation in $S_n$ and each of these permutations can be written in two-line notation $\left(1\right)$ in $n!$ ways.
For example, there are $3!=6$ elements in $S_3$
$\left[\begin{array}{ccc}1& 2& 3\\ 1& 2& 3\end{array}\right],\left[\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right],\left[\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right],{ƒ}_1=\left[\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right],{ƒ}_2=\left[\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right],\left[\begin{array}{ccc}1& 2& 3\\ 3& 1& 2\end{array}\right]$
Let us calculate ${ƒ}_1\circ {ƒ}_2$ and ${ƒ}_2\circ {ƒ}_1$. We have
$({ƒ}_1\circ {ƒ}_2)\left(1\right)={ƒ}_1({ƒ}_2\left(1\right))={ƒ}_1\left(3\right)=1$
$({ƒ}_1\circ {ƒ}_2)\left(2\right)={ƒ}_1({ƒ}_2\left(2\right))={ƒ}_1\left(2\right)=2$
$({ƒ}_1\circ {ƒ}_2)\left(3\right)={ƒ}_1({ƒ}_2\left(3\right))={ƒ}_1\left(1\right)=3$
and
$({ƒ}_2\circ {ƒ}_1)\left(1\right)={ƒ}_2({ƒ}_1\left(1\right))={ƒ}_2\left(2\right)=2$
$({ƒ}_2\circ {ƒ}_1)\left(2\right)={ƒ}_2({ƒ}_1\left(2\right))={ƒ}_2\left(3\right)=1$
$({ƒ}_2\circ {ƒ}_1)\left(3\right)={ƒ}_2({ƒ}_1\left(3\right))={ƒ}_2\left(1\right)=3$
that is
${ƒ}_1\circ {ƒ}_2=\left[\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right]$ and ${ƒ}_2\circ {ƒ}_1=\left[\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right]$.
Theorem 1. Let $S_n$ be the set of all permutation on $n$ elements. Then
1) $ƒ\circ g\in S_n$ for any $ƒ,g\in S_n$;
$2$)$h\circ (g\circ ƒ)=(h\circ g)\circ ƒ$ for any $ƒ,g,h\in S_n$;
$3$)$S_n$ has a special permutation called the identity permutation, denoted id_n, such that
$ƒ\circ$id_n$=$id_n$\circ ƒ=ƒ$ for any $ƒ\in S_n;$
$4$) for each $ƒ\in S_n$ there exists an element in $S_n$, denoted ${ƒ}^{-1}$, called the inverse of $ƒ$, such that
$ƒ\circ {ƒ}^{-1}={ƒ}^{-1}\circ ƒ=$ id_n;
$5$) if $n\ge 3$, the composition of permutations of $S_n$ is not commutative, that is, there are ${ƒ}_1,{ƒ}_2\in S_n$ such that ${ƒ}_1\circ {ƒ}_2\ne {ƒ}_2\circ {ƒ}_1$
Proof. $1$) Since, by Definition 3, $ƒ$ and $g$ are bijections, the statement follows immediately from item 4 of Lemma 1.
2) Since, by Definition 3, $ƒ,g$ and $h$ are functions, the statement follows immediately from item1 of Lemma 1.
3) It is straightforward to check that the identity permutation of $S_n$, id_n, should be defined as id_n$\left(i\right)=i,$ for $i\in \left[n\right]$, that is
id_n$=\left[\begin{array}{ccccc}{i}_1& i_2& i_3& \dots & i_n\\ i_1& i_2& i_3& \dots & i_n\end{array}\right]$
$4$) If $ƒ\in S_n$ is defined by ($1$) then it is straightforward to check that the inverse of $ƒ,{ƒ}^{-1}$, should be defined as
$\left(4\right)$ $\left[\begin{array}{ccccc}ƒ\left(i_1\right)& ƒ\left(i_2\right)& ƒ\left(i_3\right)& \dots & ƒ\left(i_n\right)\\ i_1& i_2& i_3& \dots & i_n\end{array}\right]$
$5$) The statement follows immediately from $\left(2\right)$.
Remark. Theorem 1 means that $S_n$ forms a non-commutative group with respect to composition of functions, $\circ$. This group is called full symmetry group of $n$-element set.

Definition 4. Let $(k_1,k_2,\dots ,k_n)$ be an ordered list of the elements of $\left[n\right]$ such that each element of $\left[n\right]$ occurs (in the list) only once. The ordered pair of elements $(k_{i_1},k_{i_2})$ is called an inversionof the list if $i_1<i_2$ and $k_{i_1}>k_{i_2}$. For example, the pairs $(4,3)=(k_1,k_2)$, $(3,1)=(k_2,k_3),(3,2)=(k_2,k_4),(4,1)=(k_1,k_3)$ and $(4,2)=(k_1,k_4)$ are all the inversions of the ordered list $(4,3,1,2,5)=(k_1,k_2,k_3,k_4,k_5)$.

Definition 5. Suppose that a permutation $ƒ\in S_n$ is written in the form ($1$). The sign (or signature or signum) of $ƒ$, denoted sgn$\left(ƒ\right)$, is defined to be
sgn$\left(ƒ\right)\stackrel{\scriptscriptstyle\mathrm{def}}{=}{(-1)}^{p\left(ƒ\right)+q\left(ƒ\right)},$
where $p\left(ƒ\right)$ and $q\left(ƒ\right)$ is the number of inversions in the ordered list $(i_1,i_2,i_3,\dots ,i_n)$ and $ƒ\left(i_1\right),ƒ\left(i_2\right),ƒ\left(i_3\right),\dots ,ƒ\left(i_n\right)$, respectively.

Lemma 2. The value of ${(-1)}^{p\left(ƒ\right)+q\left(ƒ\right)}$ does not depend on the choice of representation of f in the form ($1$) (that is, Definition 5 is correct).

Theorem 2. For any $ƒ,g\in S_n$ we have sgn$(ƒ\circ g)=$sgn$\left(ƒ\right)\cdot$sgn$\left(g\right)$.
Proof. Let us choose the representations of $ƒ$ and $g$ in the form ($1$) such that the first row of $ƒ$ is equal to the second row of $g$, that is $ƒ=\left[\begin{array}{ccccc}{j}_1& j_2& j_3& \dots & j_n\\ k_1& k_2& k_3& \dots & k_n\end{array}\right]$ and $g=\left[\begin{array}{ccccc}{i}_1& i_2& i_3& \dots & i_n\\ j_1& j_2& j_3& \dots & j_n\end{array}\right]$.
Then we have $ƒ\circ g=\left[\begin{array}{ccccc}{i}_1& i_2& i_3& \dots & i_n\\ k_1& k_2& k_3& \dots & k_n\end{array}\right]$. Due to our choice of the representations of $ƒ$ and $g$, we have $p\left(ƒ\right)=q\left(g\right),p(ƒ\circ g)=p\left(g\right)$ and $q(ƒ\circ g)=q\left(ƒ\right)$, therefore sgn$(ƒ\circ g)={(-1)}^{p(ƒ\circ g)+q(ƒ\circ g)}={(-1)}^{p\left(g\right)+q\left(ƒ\right)}$
and
sgn$\left(ƒ\right)\cdot$sgn$\left(g\right)={(-1)}^{p\left(ƒ\right)+q\left(ƒ\right)}\cdot {(-1)}^{p\left(g\right)+q\left(g\right)}={(-1)}^{p\left(ƒ\right)+q\left(ƒ\right)}\cdot {(-1)}^{p\left(g\right)+p\left(ƒ\right)}={(-1)}^{p\left(g\right)+q\left(ƒ\right)+2p\left(ƒ\right)}={(-1)}^{p\left(g\right)+q\left(ƒ\right)}$.
Thus, sgn$(ƒ\circ g)={(-1)}^{p\left(g\right)+q\left(ƒ\right)}=$sgn$\left(ƒ\right)\cdot$sgn$\left(g\right)$.

Definition 6. A permutation $ƒ\in S_n$ is called the transposition of elements $k,l\in \left[n\right]$ if $ƒ\left(k\right)=l,ƒ\left(l\right)=$k and $ƒ\left(i\right)=i$, for $i\in \left[n\right]$, $i\ne k,i\ne l$
Proposition 1.
1) sgn(id_n)$=1$
2) sgn$\left(ƒ\right)=$sgn$\left({ƒ}^{-1}\right)$ for any $ƒ\in S_n$;
3) if $ƒ\in S_n$ is a transposition then sgn$\left(ƒ\right)=-1$
Proof. 1) Since id_n can be written in the form $\left(3\right)$, we have $p$(id_n)$=q$(id_n). Therefore, by Definition $5,$ sgn(id_n)$=1.$
2) Since if $ƒ$ is written in the form $\left(1\right)$ then ${ƒ}^{-1}$ can be written as $\left(4\right)$, we have $p\left({ƒ}^{-1}\right)=q\left(ƒ\right)$ and $q\left({ƒ}^{-1}\right)=\dot{p}\left(ƒ\right)$ Therefore, by Definition $5,$ sgn$\left({ƒ}^{-1}\right)=-1.$
3) Suppose that $ƒ\in S_n$ is the transposition of elements $k,l\in \left[n\right]$. Then $ƒ$ can be written as $ƒ=\left[\begin{array}{cccccc}l& k& i_1& i_2& \dots & i_{n-2}\\ k& l& i_1& i_2& \dots & i_{n-2}\end{array}\right]$.
It should be clear that in this case we have either $p\left(ƒ\right)=p\left(ƒ\right)-1$ (if l < k) or $p\left(ƒ\right)=q\left(ƒ\right)+1$ (ifl > k). In both cases, by Definition 5, sgn$\left(ƒ\right)=-1.$

Definition 7. A permutation $ƒ\in S_n$ is called
1) an even permutation if sgn$\left(ƒ\right)=1$
2) an odd permutation if sgn$\left(ƒ\right)=-1$