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 parity.

AM AM 28 Oct 2021 16:26 UTC
Just fyi, as stated the sentence “Therefore $c(\sigma)$ takes even values if there are evenly many transpositions in $\sigma$, and odd values if there are odd-many transpositions in $c(\sigma)$ is false as stated. It depends on the parity of $n$ --- indeed, $c({\rm identity}) = n$.

The sign of a permutation is well-defined

Proof