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.

%%%knows-requisite(Cyclic group): 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(\sigma)$~$ 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((12)) = n-1$~$ because $~$(12)$~$ is shorthand for $~$(12)(3)(4)\dots(n-1)(n)$~$. We claim that multiplying $~$\sigma$~$ by a transposition either increases $~$c(\sigma)$~$ by $~$1$~$, or decreases it by $~$1$~$.

Indeed, let $~$\tau = (kl)$~$. 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 $~$(kl)$~$). Then $~$\sigma (kl) = \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 $~$(kl)$~$. Then $~$\sigma (kl) = \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. %%%knows-requisite(Modular arithmetic): (The following paragraph is more succinctly expressed as: "$~$c(\sigma) \equiv n+a \pmod{2}$~$ and also $~$\equiv n+b \pmod{2}$~$, so $~$a \equiv b \pmod{2}$~$.") %%% Then $~$c(\sigma)$~$ 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 [even_odd_parity parity].