Given a permutation $\sigma$ in the symmetric group $S_n$, there is a finite sequence ${\tau }_1,\dots ,{\tau }_k$ of transpositions such that $\sigma ={\tau }_k{\tau }_{k-1}\dots {\tau }_1$. Equivalently, symmetric groups are generated by their transpositions.

Note that the transpositions might "overlap". For example, $\left(123\right)$ is equal to $\left(23\right)\left(13\right)$, where the element $3$ appears in two of the transpositions.

Note also that the sequence of transpositions is by no means uniquely determined by $\sigma$.

Proof

It is enough to show that a cycle is expressible as a sequence of transpositions. Once we have this result, we may simply replace the successive cycles in $\sigma$'s disjoint cycle notation by the corresponding sequences of transpositions, to obtain a longer sequence of transpositions which multiplies out to give $\sigma$.

It is easy to verify that the cycle $(a_1{a}_2\dots a_r)$ is equal to $\left(a_{r-1}{a}_r\right)\left(a_{r-2}{a}_r\right)\dots \left(a_2{a}_r\right)\left(a_1{a}_r\right)$. Indeed, that product of transpositions certainly does not move anything that isn't some $a_i$; while if we ask it to evaluate $a_i$, then the $\left(a_1{a}_r\right)$ does nothing to it, $\left(a_2{a}_r\right)$ does nothing to it, and so on up to $\left(a_{i-1}{a}_r\right)$. Then $\left(a_i{a}_r\right)$ sends it to $a_r$; then $\left(a_{i+1}{a}_r\right)$ sends the resulting $a_r$ to $a_{i+1}$; then all subsequent transpositions $\left(a_{i+2}{a}_r\right),\dots ,\left(a_{r-1}{a}_r\right)$ do nothing to the resulting $a_{i+1}$. So the output when given $a_i$ is $a_{i+1}$.

Why is this useful?

It can make arguments simpler: if we can show that some property holds for transpositions and that it is closed under products, then it must hold for the entire symmetric group.