next up previous contents
Next: Stirling numbers of the Up: Special Sequences of Integers Previous: Stirling numbers of the   Contents

Transpositions and shuffles

A transposition is a permutation which swaps two points and fixes the rest.

Theorem 8.6.4   Every permutation is the product of transpositions.

Proof. Since every permutations is the product of cycles we only need to check for cycles. This is easy: $ (i_1\ i_2\ \dots\ i_k) = (i_1\ i_2)
(i_2\ i_3) \dots (i_{k-1}\ i_k)$. $ \qedsymbol$

Theorem 8.6.5   For a given permutation $ \pi$, the number of transpositions used to write $ \pi$ as their product is either always even or always odd.

We write $ \sign \pi = \begin{cases}
+1 & \text{if always even}\\
-1 & \text{if always odd}
\end{cases}$. We say that $ \pi$ is an
even
odd
permutation. Let $ c(\pi)$ be the number of cycles in the disjoint cycle representation of $ \pi$ (including fixed points).

Lemma 8.6.6   If $ \sigma = (a\ b)$ is a transposition that $ c(\pi \sigma) = c(\pi) \pm 1$.

Proof. If $ a$ and $ b$ are in the same cycle of $ \pi$ then $ \pi \sigma$ has two cycles, so $ c(\pi \sigma) = c(\pi) + 1$. If $ a$ and $ b$ are in different cycles then they contract them together and $ c(\pi \sigma) = c(\pi) - 1$. $ \qedsymbol$

Proof. [Proof of theorem 6.5] Assume $ \pi = \sigma_1 \dots \sigma_k \iota = \tau_1 \dots \tau_l \iota$. Then $ c(\pi) = c(\iota) + k \equiv c(\iota) + l \pmod{2}$. Hence $ k \equiv
l \pmod{2}$ as required. $ \qedsymbol$

We note that $ \sign \pi = (-1)^{n - c(\pi)}$, thus $ \sign (\pi_1 \pi_2)
= \sign \pi_1 \sign \pi_2$ and thus $ \sign$ is a homomorphism from $ S_n$ to $ \{ \pm 1 \}$.

Definition 8.6.7   A $ k$-cycle is an even permutation iff $ k$ is odd. A permutation is an
even
odd
permutation iff the number of even length cycles in the disjoint cycle representation is
even
odd
.


next up previous contents
Next: Stirling numbers of the Up: Special Sequences of Integers Previous: Stirling numbers of the   Contents
root 2002-06-10