The symmetric group $S_n$ contains elements which are made up from transpositions (proof). It is a fact that if $\sigma \in S_n$ can be made by multiplying together an even number of transpositions, then it cannot be made by multiplying an odd number of transpositions, and vice versa.

Proof

Let $c\left(\sigma \right)$ be the number of cycles in the disjoint cycle decomposition of $\sigma \in S_n$, including singletons. For example, $c$ applied to the identity yields $n$, while $c\left(\right(12\left)\right)=n-1$ because $\left(12\right)$ is shorthand for $\left(12\right)\left(3\right)\left(4\right)\dots (n-1)\left(n\right)$. We claim that multiplying $\sigma$ by a transposition either increases $c\left(\sigma \right)$ by $1$, or decreases it by $1$.

Indeed, let $\tau =\left(kl\right)$. Either $k,l$ lie in the same cycle in $\sigma$, or they lie in different ones.

• If they lie in the same cycle, then $$\sigma =\alpha (k{a}_1{a}_2\dots a_{r}l{a}_s\dots a_t)\beta$$ where $\alpha ,\beta$ are disjoint from the central cycle (and hence commute with $\left(kl\right)$). Then $\sigma \left(kl\right)=\alpha (k{a}_s\dots a_t)(l{a}_1\dots a_r)\beta$, so we have broken one cycle into two.
• If they lie in different cycles, then $$\sigma =\alpha (k{a}_1{a}_2\dots a_r)(l{b}_1\dots b_s)\beta$$ where again $\alpha ,\beta$ are disjoint from $\left(kl\right)$. Then $\sigma \left(kl\right)=\alpha (k{b}_1{b}_2\dots b_{s}l{a}_1\dots a_r)\beta$, so we have joined two cycles into one.

Therefore $c$ takes even values if there are evenly many transpositions in $\sigma$, and odd values if there are odd-many transpositions in $\sigma$.

More formally, let $\sigma ={\alpha }_1\dots {\alpha }_a={\beta }_1\dots {\beta }_b$, where ${\alpha }_i,{\beta }_j$ are transpositions.

Then $c\left(\sigma \right)$ flips odd-to-even or even-to-odd for each integer $1,2,\dots ,a$; it also flips odd-to-even or even-to-odd for each integer $1,2,\dots ,b$. Therefore $a$ and $b$ must be of the same parity.