The symmetric group contains elements which are made up from transpositions (proof). It is a fact that if $σ \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.

Equivalently, there is a group homomorphism from $S_{n}$ to the cyclic group $C_{2} = {0, 1}$ , taking the value $0$ on those permutations which are made from an even number of permutations and $1$ on those which are made from an odd number.

Proof

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

Indeed, let $τ = (k l)$ . Either $k, l$ lie in the same cycle in $σ$ , or they lie in different ones.

If they lie in the same cycle, then $σ = α (k a_{1} a_{2} \dots a_{r} l a_{s} \dots a_{t}) β$ where $α, β$ are disjoint from the central cycle (and hence commute with $(k l)$ ). Then $σ (k l) = α (k a_{s} \dots a_{t}) (l a_{1} \dots a_{r}) β$ , so we have broken one cycle into two.

If they lie in different cycles, then $σ = α (k a_{1} a_{2} \dots a_{r}) (l b_{1} \dots b_{s}) β$ where again $α, β$ are disjoint from $(k l)$ . Then $σ (k l) = α (k b_{1} b_{2} \dots b_{s} l a_{1} \dots a_{r}) β$ , so we have joined two cycles into one.

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

More formally, let $σ = α_{1} \dots α_{a} = β_{1} \dots β_{b}$ , where $α_{i}, β_{j}$ are transpositions.

(The following paragraph is more succinctly expressed as: " $c (σ) \equiv n + a (mod 2)$ and also $\equiv n + b (mod 2)$ , so $a \equiv b (mod 2)$ .")

Then $c (σ)$ 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.