Proposition 9

Let n be an integer $\geq 0$. The group $\mathfrak{S}_n$ is generated by the transpositions $(\tau_{i, i+1})_{1 \leq i \leq n-1}$.

By virtue of Proposition 8, it suffices to show that every transposition $\tau_{p,q}$, $1 \leq p < q \leq n$, belongs to the subgroup H generated by the $\tau_{i, i+1}$, $1 \leq i \leq n-1$. We show this by induction on $q-p$. For $q-p = 1$, it is obvious. If $q-p > 1$, then (formula (4)) $\tau_{p,q} = \tau_{q-1,q} \tau_{p,q-1} \tau_{q-1,q}$. By the induction hypothesis $\tau_{p,q-1} \in H$ and therefore $\tau_{p,q} \in H$.

If $\sigma \in \mathfrak{S}_n$, every ordered pair $(i, j)$ of elements of $\{1, n\}$ such that $i < j$ and $\sigma(i) > \sigma(j)$ is called an inversion of $\sigma$. Let $\nu(\sigma)$ denote the number of inversions of $\sigma$.

Let P be the additive group of mappings from $\mathbf{Z}^n$ to $\mathbf{Z}$. For $f \in P$ and $\sigma \in \mathfrak{S}_n$, let $\sigma f$ be the element of P defined by

(5)

The action of $\mathfrak{S}_n$ on P thus defined is an operation; for all $\sigma, \tau \in \mathfrak{S}_n$ and $f \in P$, $\sigma f = f$ and

Formula (5) shows that $\sigma(-f) = -\sigma f$ for $\sigma \in \mathfrak{S}_n$ and $f \in P$.

Let $p$ be the element of P defined by