Every shuffle of a deck can be done by swapping two cards at a time. In the language of cycles: every permutation is a product of transpositions. The surprise is that the number of swaps, though not fixed, is always even or always odd for a given permutation.
Transpositions generate $S_{n}$. A $k$-cycle is a product of $k - 1$ transpositions: $$(a_{1}\;a_{2}\;\dots\;a_{k}) = (a_{1}\;a_{k})(a_{1}\;a_{k-1})\cdots(a_{1}\;a_{3})(a_{1}\;a_{2}),$$ multiplied right to left as usual. For example $(1\;2\;3\;4) = (1\;4)(1\;3)(1\;2)$. Since every permutation is a product of cycles, it is a product of transpositions.
Why it works
Proof. For $\sigma \in S_{n}$, let $c(\sigma)$ be its number of cycles, counting fixed points as 1-cycles, and let $N(\sigma) = n - c(\sigma)$; the identity has $N = 0$. Multiplying by a transposition $(a\;b)$ changes $c$ by exactly one: if $a$ and $b$ lie in the same cycle, that cycle splits in two; if they lie in different cycles, the two merge. So each transposition changes the parity of $N$. A product of $m$ transpositions therefore has $N \equiv m \pmod{2}$, and the parity of $m$ is fixed by $\sigma$ alone. $\square$
So we may define the sign: $\operatorname{sgn}(\sigma) = +1$ if $\sigma$ is even (an even number of transpositions) and $-1$ if odd. From the cycle formula, a $k$-cycle has sign $(-1)^{k-1}$: odd-length cycles are even. Signs multiply: $\operatorname{sgn}(\sigma\tau) = \operatorname{sgn}(\sigma)\operatorname{sgn}(\tau)$, because the transposition counts add.
The alternating group. The even permutations form a subgroup $A_{n}$ (the identity is even, and products and inverses of even permutations are even). For $n \ge 2$, multiplying by $(1\;2)$ swaps the even and odd permutations one for one, so exactly half are even: $|A_{n}| = n!/2$.
Worked example: Signs from cycle types
- $(1\;2\;3)$: $3 - 1 = 2$ transpositions, even.
- $(1\;2\;3\;4)$: $3$ transpositions, odd.
- $(1\;2)(3\;4)$: $1 + 1 = 2$, even.
Answer: Even, odd, even.
Worked example: The elements of $A_{4}$
- Even types in $S_{4}$: the identity; 3-cycles; products of two disjoint transpositions. (Transpositions and 4-cycles are odd.)
- Counts: $1$ identity, $4 \cdot 3 \cdot 2/3 = 8$ three-cycles, and $3$ double transpositions $(1\;2)(3\;4)$, $(1\;3)(2\;4)$, $(1\;4)(2\;3)$.
- $1 + 8 + 3 = 12 = 4!/2$.
Answer: $|A_{4}| = 12$.
Common mistake
Key idea