Symmetric Groups and Permutations

The symmetric group S_n of all permutations of n objects, with n! elements and composition as its operation. Two-line and cycle notation, the theorem that every permutation is a product of disjoint cycles in essentially one way (proved by sorting the objects into orbits), orders as least common multiples of cycle lengths, cycle types and how many permutations have each, conjugation as relabeling, products of transpositions, the proof that parity is well defined by counting cycles, the alternating group of order n!/2, and parity arguments for the 15 puzzle and the Rubik's cube.

Exchange the tiles 14 and 15 of a solved 15 puzzle, and no sequence of slides will put it right. Swap two edge pieces of a solved Rubik's cube, and no sequence of turns will repair it. Both facts rest on one property. Every rearrangement of a finite set can be built from swaps of two objects in many ways, yet the number of swaps is either always even or always odd. Why should that number have a fixed parity?

A rearrangement of a set is a permutation, a bijection from the set to itself, and the permutations of $\{1, \ldots, n\}$ form the symmetric group $S_n$. It is the most important family of finite groups, for two reasons. Every group met so far in this unit lives inside one: the symmetries of the octagon permute its 8 vertices, and the moves of a Rubik's cube permute its 48 movable stickers. And by Cayley's theorem, every finite group whatsoever is a group of permutations.

First we set up $S_n$, its notation and its rule for products, and count its $n!$ elements. Then we introduce cycle notation and prove that every permutation breaks up into disjoint cycles in essentially one way. That turns orders into least common multiples and conjugation into relabeling. Finally we prove that parity is well defined by counting cycles, meet the alternating group, and return to the 15 puzzle and the cube.

This is the fourth article of Groups. It assumes the definition of a group, of permutations and of the order of an element from Groups: Definition and First Examples. It is the home of cycle notation, of the parity of a permutation and of the alternating group; later articles build on them. It covers the symmetric groups of §7.1 and the cycle notation, transpositions and alternating groups of §7.5 of the course text (Hungerford, 2014), with Judson (2026, §5.1) as a free companion. One permutation $\sigma$ in $S_8$ serves as the running example throughout.

Permutations and the group $S_n$

Before any theorem, we need a way to write permutations down and a rule for multiplying them. By the proposition on groups of transformations, the permutations of a nonempty set $X$ form a group under composition. When $X = \{1, 2, \ldots, n\}$, this group is written $S_n$.

Two-line notation lists the inputs in a top row and each output below its input. The running example is the permutation $\sigma$ of $\{1, \ldots, 8\}$ with

$$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 5 & 8 & 6 & 4 & 2 & 7 & 3 & 1 \end{pmatrix},$$

so that $\sigma(1) = 5$, $\sigma(2) = 8$, and so on. The bottom row lists each of $1, \ldots, 8$ exactly once, which is what makes $\sigma$ a bijection. Its inverse undoes it: reading the columns upward, $\sigma^{-1}$ sends 5 to 1, 8 to 2, and so on, so

$$\sigma^{-1} = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 8 & 5 & 7 & 4 & 1 & 3 & 6 & 2 \end{pmatrix}.$$

Products are composites, right factor first. As in the course text and in Judson, the product $\alpha\beta$ of two permutations is the composite $\alpha \circ \beta$, so $(\alpha\beta)(x) = \alpha(\beta(x))$: apply $\beta$ first, then $\alpha$. (The Rubik's cube group follows the opposite convention, since cube notation is read left to right.)

How many permutations are there? The idea of the count: choose where $n$ goes, and what remains is a permutation of $n - 1$ objects under new names.

Proposition. $S_n$ has $n!$ elements.

Proof. By induction on $n$. $S_1$ has one element, the identity. Let $n \ge 2$ and suppose $\lvert S_{n-1} \rvert = (n - 1)!$. For each $k$ in $\{1, \ldots, n\}$, the permutations $\pi$ of $\{1, \ldots, n\}$ with $\pi(n) = k$ are exactly the bijections from $\{1, \ldots, n - 1\}$ onto the $n - 1$ elements of $\{1, \ldots, n\} \setminus \{k\}$, extended by $n \mapsto k$. List the elements of $\{1, \ldots, n\} \setminus \{k\}$ in increasing order and rename them $1, \ldots, n - 1$. This matches these bijections one to one with the elements of $S_{n-1}$, so there are $(n - 1)!$ of them for each of the $n$ values of $k$. Hence $\lvert S_n \rvert = n \cdot (n - 1)! = n!$. $\blacksquare$

The script lists every permutation for $n = 1$ to 7 and finds $n!$ each time. The numbers grow fast: $S_8$ has $40{,}320$ elements and $S_{12}$ has $479{,}001{,}600$. The same matching shows that $7! = 5040$ elements of $S_8$ fix 4, as $\sigma$ does, and the script counts 5040 directly.

Cycle notation

Two-line notation hides the structure of a permutation. Following $\sigma$ from 1 gives

$$1 \to 5 \to 2 \to 8 \to 1,$$

a closed loop of four elements. Starting from 3, the next unused element, gives $3 \to 6 \to 7 \to 3$, and 4 is sent to itself. These loops are the cycles of $\sigma$.

Definition. Let $a_1, a_2, \ldots, a_k$ be distinct elements of $\{1, \ldots, n\}$. The cycle $(a_1 \; a_2 \; \cdots \; a_k)$ is the permutation that sends $a_1 \mapsto a_2$, $a_2 \mapsto a_3$, ..., $a_{k-1} \mapsto a_k$, $a_k \mapsto a_1$, and fixes every other element. Its length is $k$, and it is called a $k$-cycle. A 2-cycle $(a \; b)$, which swaps $a$ and $b$, is a transposition. Two cycles are disjoint if they have no element in common.

The same cycle can be written starting at any of its elements, $(1 \; 5 \; 2 \; 8) = (5 \; 2 \; 8 \; 1) = (2 \; 8 \; 1 \; 5) = (8 \; 1 \; 5 \; 2)$, but not in another order: $(1 \; 2 \; 5 \; 8)$ is a different permutation. A 1-cycle $(a)$ is the identity, which is also written $1$. In this notation

$$\sigma = (1 \; 5 \; 2 \; 8)(3 \; 6 \; 7), \qquad \sigma^{-1} = (1 \; 8 \; 2 \; 5)(3 \; 7 \; 6),$$

with the fixed point 4 left out. Cycle notation for permutations was introduced by Augustin-Louis Cauchy (Judson, 2026, §5.1.4).

The permutation sigma in S8 drawn with an arrow from each i to sigma(i). Notice that the arrows fall into two closed loops, the 4-cycle (1 5 2 8) and the 3-cycle (3 6 7), and a loop at 4, which sigma fixes. Reading the loops off the picture gives the cycle notation sigma = (1 5 2 8)(3 6 7).
The permutation sigma in S_8 drawn with an arrow from each i to sigma(i). Notice that the arrows fall into two closed loops, the 4-cycle (1 5 2 8) and the 3-cycle (3 6 7), and a loop at 4, which sigma fixes. Reading the loops off the picture gives the cycle notation sigma = (1 5 2 8)(3 6 7).

Does the order of the two cycles in $(1 \; 5 \; 2 \; 8)(3 \; 6 \; 7)$ matter? It does not, and the reason is that the two loops never touch: each cycle moves only its own elements.

Proposition. Disjoint cycles commute.

Proof. Let $\alpha$ and $\beta$ be disjoint cycles, and call the sets of elements they move $A$ and $B$; these are disjoint. Write $B^c$ for the set of elements outside $B$, which are exactly the elements that $\beta$ fixes. First, $\alpha$ carries $B^c$ into itself. An element of $A$ goes to an element of $A$, because a cycle sends each of its elements to another of its elements, and $A$ lies inside $B^c$. An element outside $A$ is fixed by $\alpha$. In the same way $\beta$ carries $A^c$, the set of elements that $\alpha$ fixes, into itself.

Now take any $x$. Since $A$ and $B$ do not overlap, $x$ lies outside $B$ or outside $A$. If $x \in B^c$, then $\beta$ fixes $x$, and it also fixes $\alpha(x)$, which lies in $B^c$ by the first step. So $\alpha\beta(x) = \alpha(x) = \beta(\alpha(x))$. If $x \in A^c$, the same argument with the roles of $\alpha$ and $\beta$ exchanged gives $\beta\alpha(x) = \beta(x) = \alpha\beta(x)$. So $\alpha\beta$ and $\beta\alpha$ agree everywhere. $\blacksquare$

The script confirms that $(1 \; 5 \; 2 \; 8)(3 \; 6 \; 7)$ and $(3 \; 6 \; 7)(1 \; 5 \; 2 \; 8)$ are equal, and both are $\sigma$. Cycles that share an element usually do not commute: $(1 \; 2)(2 \; 3) = (1 \; 2 \; 3)$, while $(2 \; 3)(1 \; 2) = (1 \; 3 \; 2)$. For the first, the right factor acts first:

  • $1 \mapsto 1 \mapsto 2$;
  • $2 \mapsto 3 \mapsto 3$;
  • $3 \mapsto 2 \mapsto 1$.

Every $S_n$ with $n \ge 3$ contains these two transpositions, and they do not commute:

Corollary. $S_n$ is nonabelian for every $n \ge 3$. ($S_1$ and $S_2$, of orders 1 and 2, are abelian.)

Every permutation is a product of disjoint cycles

Does the procedure used on $\sigma$, following each element until it returns, always work? It does. Here is the plan of the proof. Call two elements related when some power of $\pi$ carries one to the other; this is an equivalence relation, so it sorts the elements into classes. On each class $\pi$ goes around a single loop, and the loops are the cycles.

Theorem. Every permutation $\pi$ in $S_n$ is a product of disjoint cycles. The expression is unique except for the order of the factors and the inclusion of 1-cycles.

Proof. Define $x \sim y$ to mean $y = \pi^k(x)$ for some integer $k$, positive, negative or zero. This is an equivalence relation on $\{1, \ldots, n\}$: $x = \pi^0(x)$; if $y = \pi^k(x)$ then $x = \pi^{-k}(y)$; and if $y = \pi^k(x)$ and $z = \pi^j(y)$ then $z = \pi^{j + k}(x)$. Its classes are called the orbits of $\pi$, and they partition $\{1, \ldots, n\}$.

Fix an orbit $O$ and an element $x$ in it. The elements $x, \pi(x), \pi^2(x), \ldots$ all lie in the finite set $\{1, \ldots, n\}$, so two of them coincide, say $\pi^i(x) = \pi^j(x)$ with $i < j$. Applying $\pi^{-i}$ gives $\pi^{j - i}(x) = x$. So there is a least positive integer $L$ with $\pi^L(x) = x$. The elements $x, \pi(x), \ldots, \pi^{L-1}(x)$ are distinct, since $\pi^i(x) = \pi^j(x)$ with $0 \le i < j < L$ would give $\pi^{j - i}(x) = x$ with $0 < j - i < L$. And they make up all of $O$. For any integer $k$, division by $L$ gives $k = qL + r$ with $0 \le r < L$. Then $\pi^k(x) = \pi^r(\pi^{qL}(x)) = \pi^r(x)$, because $\pi^L$ fixes $x$ and hence so does $\pi^{qL}$ for every integer $q$. On $O$, therefore, $\pi$ acts as the cycle

$$\gamma_O = (x \;\; \pi(x) \;\; \pi^2(x) \;\; \cdots \;\; \pi^{L-1}(x)).$$

Let $\gamma_1, \ldots, \gamma_m$ be these cycles for the orbits with more than one element. They are disjoint because the orbits are. Their product agrees with $\pi$ at every $y$. The element $y$ lies in exactly one orbit. The cycle for that orbit sends $y$ to $\pi(y)$, and every other cycle fixes both $y$ and $\pi(y)$, which lie outside its orbit. (If $y$ is in a one-element orbit, $\pi(y) = y$ and all the cycles fix $y$.) So $\pi = \gamma_1 \cdots \gamma_m$.

For uniqueness, suppose $\pi = \delta_1 \cdots \delta_p$ with the $\delta_i$ disjoint cycles of length at least 2. If $\delta_i$ moves $x$, the other factors fix $x$ and everything $\delta_i$ moves, so $\pi$ acts on the elements of $\delta_i$ as $\delta_i$ does. Then $\delta_i$ sends $x$ to $\pi(x)$, $\pi(x)$ to $\pi^2(x)$, and so on, so $\delta_i$ is the cycle $\gamma_O$ of the orbit of $x$. Every factor is therefore one of the cycles $\gamma_O$. And every $\gamma_O$ must occur, since otherwise the elements it moves would be fixed by $\pi$. $\blacksquare$

Back to $\sigma$: its orbits are $\{1, 5, 2, 8\}$, $\{3, 6, 7\}$ and $\{4\}$. For the first, $L = 4$ and the cycle is $(1 \; \sigma(1) \; \sigma^2(1) \; \sigma^3(1)) = (1 \; 5 \; 2 \; 8)$, the loop of the figure.

The lengths of the cycles of $\pi$, including 1 for each fixed point, add up to $n$ and are called its cycle type. The running example has cycle type $(4, 3, 1)$.

Orders and powers

The first payoff of the decomposition is the order of a permutation. The idea: each cycle runs on its own clock, so the permutation returns home exactly when every clock does.

Proposition. A $k$-cycle has order $k$. The order of a product of disjoint cycles is the least common multiple of their lengths.

Proof. Let $\gamma = (a_1 \; a_2 \; \cdots \; a_k)$, with subscripts read modulo $k$, so that $\gamma(a_i) = a_{i + 1}$. Then $\gamma^j(a_i) = a_{i + j}$, which equals $a_i$ exactly when $k \mid j$; and $\gamma^j$ fixes every element outside the cycle. So $\gamma^j = 1$ exactly when $k$ divides $j$, and the order of $\gamma$ is $k$.

Now let $\pi = \gamma_1 \cdots \gamma_m$ with disjoint cycles of lengths $k_1, \ldots, k_m$. Because disjoint cycles commute, the factors can be regrouped, and $\pi^j = \gamma_1^j \cdots \gamma_m^j$. Each $\gamma_i^j$ moves only elements of the cycle $\gamma_i$. So the factors $\gamma_i^j$ move disjoint sets of elements, and their product is the identity exactly when each factor is. So $\pi^j = 1$ exactly when $k_i \mid j$ for every $i$, that is, when $j$ is a common multiple of $k_1, \ldots, k_m$. The least positive such $j$ is $\operatorname{lcm}(k_1, \ldots, k_m)$. $\blacksquare$

So $\sigma = (1 \; 5 \; 2 \; 8)(3 \; 6 \; 7)$ has order $\operatorname{lcm}(4, 3) = 12$, although neither of its cycles has order 12. The script computes all twelve powers. Some of them show the two cycles running on separate clocks:

Power Permutation
$\sigma^2$ $(1 \; 2)(5 \; 8)(3 \; 7 \; 6)$
$\sigma^3$ $(1 \; 8 \; 2 \; 5)$
$\sigma^4$ $(3 \; 6 \; 7)$
$\sigma^6$ $(1 \; 2)(5 \; 8)$
$\sigma^8$ $(3 \; 7 \; 6)$
$\sigma^9$ $(1 \; 5 \; 2 \; 8)$
$\sigma^{12}$ $1$

The 3-cycle disappears at every multiple of 3 and the 4-cycle at every multiple of 4. The square of the 4-cycle splits into two transpositions, $(1 \; 5 \; 2 \; 8)^2 = (1 \; 2)(5 \; 8)$. A step of two around a loop of four visits only every other element.

Inverses of cycles are read backwards: $(a_1 \; a_2 \; \cdots \; a_k)^{-1} = (a_k \; a_{k-1} \; \cdots \; a_1)$. The reversed cycle takes each element one step back around the same loop. For example $(2 \; 9 \; 4 \; 7 \; 5)^{-1} = (5 \; 7 \; 4 \; 9 \; 2) = (2 \; 5 \; 7 \; 4 \; 9)$ in $S_9$. A product of disjoint cycles is inverted cycle by cycle, which is how $\sigma^{-1}$ was written above.

Multiplying in cycle notation

To compute a product, follow each element through the factors from right to left. Let $\tau = (1 \; 2 \; 3)(6 \; 8)$. In $\sigma\tau$, the element 1 goes to $\tau(1) = 2$ and then to $\sigma(2) = 8$. Then 8 goes to $\tau(8) = 6$ and $\sigma(6) = 7$. Continuing,

$$\sigma\tau = (1 \; 8 \; 7 \; 3 \; 5 \; 2 \; 6), \qquad \tau\sigma = (1 \; 5 \; 3 \; 8 \; 2 \; 6 \; 7).$$

Both are 7-cycles fixing 4, but they are different, another instance of noncommutativity. The inverse of the product reverses the factors, $(\sigma\tau)^{-1} = \tau^{-1}\sigma^{-1}$, which the script confirms is different from $\sigma^{-1}\tau^{-1}$.

Check your understanding. $\sigma$ has order 12 and $\tau$ has order 6. Must the order of $\sigma\tau$ divide $\operatorname{lcm}(12, 6) = 12$?

It need not, and here it does not: $\sigma\tau$ is a 7-cycle, of order 7. The least-common-multiple rule is about the disjoint cycles of one permutation, which act on separate elements. The cycles of $\sigma$ and of $\tau$ overlap, and their product mixes them into a new loop.

Cycle types and their sizes

How many permutations have a given cycle type? Suppose the type has $m_k$ cycles of length $k$ for each $k$, so that $\sum_k k \, m_k = n$. Write down the pattern of parentheses for that type and fill the $n$ slots with $1, \ldots, n$ in any of the $n!$ orders. Every permutation of the type arises, and each arises the same number of times:

  • each cycle of length $k$ can be started at any of its $k$ elements;
  • the $m_k$ cycles of the same length can be listed in any of $m_k!$ orders.

So the number of permutations of the type is

$$\frac{n!}{\prod_k k^{m_k} \, m_k!}.$$

For $S_6$ the eleven cycle types are:

Cycle type Number Order Parity
$(1,1,1,1,1,1)$ 1 1 even
$(2,1,1,1,1)$ 15 2 odd
$(2,2,1,1)$ 45 2 even
$(2,2,2)$ 15 2 odd
$(3,1,1,1)$ 40 3 even
$(3,2,1)$ 120 6 odd
$(3,3)$ 40 3 even
$(4,1,1)$ 90 4 odd
$(4,2)$ 90 4 even
$(5,1)$ 144 5 even
$(6)$ 120 6 odd

The numbers add up to 720, and the script confirms each one by listing all of $S_6$. The parity column is explained below. The largest order is 6, reached by 240 elements: the 120 six-cycles and the 120 of type $(3, 2, 1)$. Type $(3, 3)$ has order only $\operatorname{lcm}(3, 3) = 3$. In general the largest order in $S_n$ is the largest least common multiple of a list of positive integers adding up to $n$. For $n = 8$ it is 15, from a 5-cycle and a 3-cycle, and for $n = 12$ it is 60, from cycles of lengths 5, 4 and 3. These are the largest orders of the corner and the edge permutations of the Rubik's cube, whose eight corners and twelve edges are permuted by every move.

Conjugation relabels

Cycle types sort the permutations of $S_6$ into eleven families, and conjugation moves a permutation around inside its family. The idea: $\rho \gamma \rho^{-1}$ undoes $\rho$, applies $\gamma$ and redoes $\rho$, so it performs $\gamma$ on objects renamed by $\rho$.

Proposition. Let $\rho$ be any permutation in $S_n$. Then

$$\rho \, (a_1 \; a_2 \; \cdots \; a_k) \, \rho^{-1} = (\rho(a_1) \;\; \rho(a_2) \;\; \cdots \;\; \rho(a_k)).$$

Proof. Let $\gamma = (a_1 \; \cdots \; a_k)$. At the element $\rho(a_i)$, the left side gives $\rho(\gamma(\rho^{-1}(\rho(a_i)))) = \rho(\gamma(a_i)) = \rho(a_{i+1})$, which is what the right side does. Any other element $y$ is not of the form $\rho(a_i)$, so $\rho^{-1}(y)$ is not among the $a_i$, $\gamma$ fixes it, and the left side sends $y$ to $\rho(\rho^{-1}(y)) = y$, as the right side does. $\blacksquare$

In words, conjugating by $\rho$ renames every object $x$ as $\rho(x)$ and leaves the shape of the cycle alone. Since $\rho\alpha\beta\rho^{-1} = (\rho\alpha\rho^{-1})(\rho\beta\rho^{-1})$, the rule applies to each cycle of a product separately. So conjugate permutations have the same cycle type. Check it with $\sigma$ as the renaming: $\sigma$ sends $1, 2, 3, 6, 8$ to $5, 8, 6, 7, 1$, and the script confirms

$$\sigma \, (1 \; 2 \; 3)(6 \; 8) \, \sigma^{-1} = (5 \; 8 \; 6)(7 \; 1).$$

Conversely, two permutations of the same cycle type are conjugate. Line up their cycles of equal length one under the other. The permutation that sends each entry of the first to the entry below it does the renaming. This is the algebra behind the setup moves of the Rubik's cube, where a conjugate $X M X^{-1}$ does the work of $M$ on other pieces.

Check your understanding. Could some conjugate $\rho\sigma\rho^{-1}$ of the running example be a 7-cycle, such as $\sigma\tau$?

No. Every conjugate of $\sigma$ has the cycle type $(4, 3, 1)$ of $\sigma$: a 4-cycle, a disjoint 3-cycle and a fixed point. A 7-cycle has type $(7, 1)$, so it lies in a different family.

Transpositions and parity

Now to the question of the opening: swaps. A cycle can be built from transpositions. Checking each element shows that, with the right factor acting first,

$$(a_1 \; a_2 \; \cdots \; a_k) = (a_1 \; a_k)(a_1 \; a_{k-1}) \cdots (a_1 \; a_3)(a_1 \; a_2).$$

Follow the elements through the factors from the right:

  • $a_1$ is sent to $a_2$ by the first factor and then left alone;
  • each $a_i$ with $2 \le i < k$ is sent to $a_1$ by the factor $(a_1 \; a_i)$ and then to $a_{i+1}$ by the next one;
  • $a_k$ is untouched until the last factor sends it to $a_1$.

With the disjoint cycle theorem this proves:

Proposition. Every permutation in $S_n$, $n \ge 2$, is a product of transpositions.

For the running example, $\sigma = (1 \; 8)(1 \; 2)(1 \; 5)(3 \; 7)(3 \; 6)$, which the script confirms. The expression is far from unique. Since a transposition is its own inverse, $(1 \; 2)(1 \; 2)$ can be inserted anywhere. Sorting the bottom row of $\sigma$ by swapping neighboring entries, as the bubble sort algorithm does, writes $\sigma$ as a product of 21 transpositions of the form $(i \;\; i{+}1)$. There is one for each pair of entries that appear in the wrong order.

What does not change is whether the number of transpositions is even or odd: $\sigma$ can be written with 5 and with 21, and never with an even number. Here is the plan of the proof. Multiplying by one transposition changes the number of cycles by exactly one. So after $m$ transpositions the count has changed parity $m$ times, and the count at the end is fixed by the permutation.

For a permutation $\pi$ in $S_n$, let $c(\pi)$ be the number of its cycles, counting each fixed point as a cycle of length 1. The identity has $c = n$, and $c(\sigma) = 3$.

Lemma. Let $\pi \in S_n$ and let $(a \; b)$ be a transposition. If $a$ and $b$ lie in the same cycle of $\pi$, then $c((a \; b)\pi) = c(\pi) + 1$. If they lie in different cycles, $c((a \; b)\pi) = c(\pi) - 1$.

Proof. The product $(a \; b)\pi$ agrees with $\pi$ except at the two elements that $\pi$ sends to $a$ and to $b$, which it sends to $b$ and to $a$ instead. Cycles of $\pi$ containing neither $a$ nor $b$ are therefore cycles of $(a \; b)\pi$ as well.

Suppose $a$ and $b$ are in the same cycle, written $(a \; u_1 \; \cdots \; u_p \; b \; v_1 \; \cdots \; v_q)$ with $p, q \ge 0$, so that $\pi(u_p) = b$ and $\pi(v_q) = a$ (with $u_p$ read as $a$ if $p = 0$, and $v_q$ as $b$ if $q = 0$). In $(a \; b)\pi$, $u_p$ goes to $a$ instead of $b$, and $v_q$ goes to $b$ instead of $a$, so the cycle splits into the two cycles $(a \; u_1 \; \cdots \; u_p)$ and $(b \; v_1 \; \cdots \; v_q)$. Suppose instead $a$ and $b$ are in different cycles $(a \; u_1 \; \cdots \; u_p)$ and $(b \; v_1 \; \cdots \; v_q)$, so that $\pi(u_p) = a$ and $\pi(v_q) = b$. In $(a \; b)\pi$, $u_p$ goes to $b$ and $v_q$ to $a$, and the two cycles merge into $(a \; u_1 \; \cdots \; u_p \; b \; v_1 \; \cdots \; v_q)$. In the first case the number of cycles rises by one and in the second it falls by one. $\blacksquare$

Multiplying the running example sigma = (1 5 2 8)(3 6 7) on the left by a transposition. Since 1 and 2 lie in the same cycle of sigma, (1 2)sigma = (1 5)(2 8)(3 6 7) splits that cycle in two, raising the number of cycles (fixed point 4 included) from 3 to 4. Since 1 and 3 lie in different cycles, (1 3)sigma = (1 5 2 8 3 6 7) merges them, lowering the number to 2. Notice that either way the number of cycles changes by exactly one.
Multiplying the running example sigma = (1 5 2 8)(3 6 7) on the left by a transposition. Since 1 and 2 lie in the same cycle of sigma, (1 2)sigma = (1 5)(2 8)(3 6 7) splits that cycle in two, raising the number of cycles (fixed point 4 included) from 3 to 4. Since 1 and 3 lie in different cycles, (1 3)sigma = (1 5 2 8 3 6 7) merges them, lowering the number to 2. Notice that either way the number of cycles changes by exactly one.

The script checks the lemma for every permutation of $S_6$ and every transposition, and finds a split exactly when the two elements share a cycle.

Theorem. If a permutation $\pi$ in $S_n$ is a product of $m$ transpositions, then

$$m \equiv n - c(\pi) \pmod 2.$$

In particular, no permutation is a product of both an even and an odd number of transpositions.

Proof. Write $\pi = t_1 t_2 \cdots t_m$ and build it from the right, starting from the identity, which has $n$ cycles: $t_m$, then $t_{m-1}t_m$, and so on up to $\pi$. Each step multiplies on the left by a transposition, which by the lemma changes the number of cycles by $\pm 1$ and so changes its parity. After $m$ steps, $c(\pi) \equiv n + m \pmod 2$, which is the same as $m \equiv n - c(\pi)$, since $-m \equiv m$. The right side depends only on $\pi$, so every expression of $\pi$ as a product of transpositions has a number of factors of the same parity. $\blacksquare$

A permutation is even if it is a product of an even number of transpositions and odd otherwise. Its sign is $\operatorname{sgn}(\pi) = (-1)^{n - c(\pi)}$, which is $+1$ for even and $-1$ for odd permutations. Since $n - c(\pi) = \sum (k_i - 1)$ over the cycle lengths $k_i$, the parity can be read from the cycle type. The parity column of the $S_6$ table was found this way.

  • A $k$-cycle has sign $(-1)^{k-1}$. Cycles of odd length are even, and cycles of even length, transpositions and 4-cycles among them, are odd.
  • The running example has $n - c(\sigma) = 8 - 3 = 5$, so $\sigma$ is odd, in agreement with its expressions by 5 and by 21 transpositions.

Check your understanding. The running example $\sigma$ is a product of 5 transpositions. Can it be written as a product of 4? Of 7?

Not of 4, since 4 is even and $\sigma$ is odd; the script also tries every product of four transpositions in $S_8$ and finds none equal to $\sigma$. Seven is possible: insert $(1 \; 2)(1 \; 2)$, which is the identity, into the expression with 5. The theorem forbids a change of parity, not a change of length.

The sign of a product is easy to predict, because the counts of transpositions add.

Corollary. $\operatorname{sgn}(\alpha\beta) = \operatorname{sgn}(\alpha) \operatorname{sgn}(\beta)$ for all $\alpha$, $\beta$ in $S_n$.

Proof. Writing $\alpha$ as a product of $i$ transpositions and $\beta$ as a product of $j$ writes $\alpha\beta$ as a product of $i + j$, and $(-1)^{i + j} = (-1)^i(-1)^j$. $\blacksquare$

The script checks the corollary on all pairs of permutations in $S_5$. The approach through counting cycles is one of several. The course text and Judson (2026, Lemma 5.1.14 and Theorem 5.1.15) prove first that the identity is never a product of an odd number of transpositions, by moving and canceling transpositions in a product. Others count inversions, the pairs of entries out of order in the bottom row, whose parity also equals the sign (for $\sigma$ there are 21).

The alternating group

Do the even permutations form a group of their own, and how many are there? The idea: evenness survives products and inverses because signs multiply. For the count, sort the permutations by where they send $n$, as in the count of $S_n$, and follow how the numbers of even and odd ones grow with $n$.

Proposition. For $n \ge 2$ the even permutations in $S_n$ form a group $A_n$ under composition, the alternating group, of order $n!/2$.

Proof. The identity is even, being the product of no transpositions. By the corollary, a product of even permutations is even. Since $\operatorname{sgn}(\pi)\operatorname{sgn}(\pi^{-1}) = \operatorname{sgn}(1) = 1$, the inverse of an even permutation is even. Associativity is inherited from $S_n$.

For the count, let $e_n$ and $o_n$ be the numbers of even and odd permutations in $S_n$, so $e_1 = 1$ and $o_1 = 0$. Let $n \ge 2$. The permutations of $S_n$ with $\pi(n) = n$ are the permutations of $\{1, \ldots, n - 1\}$ with $n$ added as a fixed point. Adding the fixed point raises both $n$ and the number of cycles $c(\pi)$ by one, so it leaves the sign $(-1)^{n - c(\pi)}$ unchanged; these permutations contribute $e_{n-1}$ even and $o_{n-1}$ odd ones. For each $k \neq n$, the map $\pi \mapsto (k \; n)\pi$ sends the permutations with $\pi(n) = k$ to those with $\pi(n) = n$, since $(k \; n)$ sends $k$ to $n$. The same formula maps back, because $(k \; n)(k \; n) = 1$, so it is a bijection between the two sets. It reverses the sign, by the corollary, since a transposition is odd. So each of the $n - 1$ values $k \neq n$ contributes $o_{n-1}$ even and $e_{n-1}$ odd permutations, and

$$e_n = e_{n-1} + (n - 1)\,o_{n-1}, \qquad o_n = o_{n-1} + (n - 1)\,e_{n-1}.$$

Subtracting, $e_n - o_n = (2 - n)(e_{n-1} - o_{n-1})$. For $n = 2$ the factor $2 - n$ is 0, so $e_2 = o_2$, and then $e_n - o_n = 0$ for every $n \ge 2$ by induction. Since $e_n + o_n = n!$, there are $n!/2$ even permutations. $\blacksquare$

The script counts the even permutations for $n = 2$ to 7 and finds $n!/2$ each time, in agreement with the two recursions: from $e_1 = 1$ and $o_1 = 0$ they give $e_2 = o_2 = 1$, $e_3 = o_3 = 3$ and $e_4 = o_4 = 12$. The alternating groups are the first family of subgroups met in this unit; subgroups in general are the subject of Subgroups and Cyclic Groups.

Parity in puzzles

Back to the two puzzles of the opening. Parity is an invariant: a quantity that every allowed move changes in a predictable way, so that some configurations can be ruled out without any search.

The 15 puzzle. Fifteen numbered tiles and one blank square sit in a $4 \times 4$ frame, and a move slides a tile into the adjacent blank. Number the squares 1 to 16, and regard the blank as tile 16. Each move swaps tile 16 with a neighbor, so it is a transposition of the 16 squares' contents. Color the squares like a chessboard. Each move carries the blank to a square of the other color. So if the blank starts and ends in the same corner, it has made an even number of moves, and the resulting permutation of the 16 contents is even.

The position with every tile in order except 14 and 15 exchanged, and the blank in its starting corner, is a single transposition, which is odd. So it cannot be reached. Of the $15!$ arrangements of the tiles with the blank in its starting corner, exactly half, $15!/2 = 653{,}837{,}184{,}000$, are even. Joyner (1997, §6.3, Theorem 120) shows that every one of these can be reached, by producing enough 3-cycles of tiles; the other half cannot. The $3 \times 3$ version, the 8-puzzle, behaves the same way: a breadth-first search in a hill-climbing experiment reaches exactly half of the $9!$ arrangements.

The Rubik's cube. Every quarter turn moves four corner pieces in a 4-cycle and four edge pieces in a 4-cycle, and a 4-cycle is odd. So after any sequence of turns, the permutation of the corners and the permutation of the edges have the same sign. A cube with exactly two edge pieces swapped has an odd edge permutation and an even corner permutation, so it cannot be solved. This is the first of the three invariants in The Rubik's Cube Group.

Check your understanding. A sequence of 7 quarter turns is applied to a solved cube. What is the sign of the permutation of the eight corners?

It is $(-1)^7 = -1$, since each quarter turn moves the corners by a 4-cycle and signs multiply. So seven turns can never leave every corner in its starting place.

Permutation groups everywhere

How far does this toolkit reach beyond $S_n$ itself? A permutation group is a group of permutations of a set: a collection of permutations that contains the identity and is closed under composition and inverses. Every group in this unit is one:

  • The dihedral group $D_n$ permutes the $n$ vertices of a regular polygon, as 16 of the $8!$ permutations of the octagon's vertices (Dihedral Groups).
  • The rotations of a solid cube permute its four long diagonals, and every one of the $4! = 24$ permutations of the diagonals arises from exactly one rotation, so the rotation group of the cube is a copy of $S_4$ (Judson, 2026, Theorem 5.2.9).
  • The Rubik's cube group permutes 48 facets, and maps each move to a permutation of the 8 corners in $S_8$ and of the 12 edges in $S_{12}$ (The Rubik's Cube Group).
  • The group of units $U(9)$ permutes its own six elements: multiplying every element by 2 rearranges them, as the rows of its Cayley table show. Cayley's theorem turns this observation into a proof that every group is isomorphic to a group of permutations.

Where it leads

  • The first theorems about all groups, including the reversed order of $(\alpha\beta)^{-1}$ used above, are in Basic Properties of Groups.
  • $A_n$, the rotations of $D_n$ and the powers of a single permutation are subgroups (Subgroups and Cyclic Groups).
  • The sign is a homomorphism from $S_n$ to the group $\{1, -1\}$, and $A_n$ is the set of elements it sends to 1, its kernel.
  • Cayley's theorem embeds every finite group in some $S_n$.
  • $A_n$ fills exactly half of $S_n$, the simplest case of the cosets of Lagrange's theorem, and it is the leading example of a normal subgroup.

What we have learned

Every permutation is a product of disjoint cycles in essentially one way. The cycles turn orders into least common multiples and make conjugation a relabeling. Every permutation is also a product of transpositions, and since each transposition changes the number of cycles by exactly one, the parity of their number is fixed. That is why the 15 puzzle with 14 and 15 exchanged cannot be solved.

We used rules such as $(\sigma\tau)^{-1} = \tau^{-1}\sigma^{-1}$ freely. Do they hold in every group? The next article, Basic Properties of Groups, proves them from the four axioms alone.

References

  • Hungerford, T. W. (2014). Abstract Algebra: An Introduction (3rd ed.), §7.1 and §7.5. Brooks/Cole, Cengage Learning. The course text: the symmetric group $S_n$ of permutations under composition, with the right-hand factor applied first; cycle notation; disjoint cycles and the decomposition of a permutation into disjoint cycles; the order of a permutation as the least common multiple of its cycle lengths; transpositions, even and odd permutations, and the alternating group $A_n$ of order $n!/2$. record · 44 pages
  • Joyner, W. D. (1997). Mathematics of the Rubik's Cube. Lecture notes, United States Naval Academy, Spring semester 1996 to 1997. §4.1 (the 15 puzzle as a permutation puzzle); §6.3 (the checkerboard argument showing that the position with 14 and 15 exchanged cannot be reached; Theorem 120, the reachable positions with the blank in its corner correspond to the even permutations of the 15 tiles). record · 3 pages
  • Judson, T. W. (2026). Abstract Algebra: Theory and Applications (annual edition, August 2026). Free online at judsonbooks.org. §5.1 (Theorem 5.1.1, $S_n$ is a group with $n!$ elements; cycle notation; Proposition 5.1.8, disjoint cycles commute; Theorem 5.1.9, decomposition into disjoint cycles; Proposition 5.1.12, products of transpositions; Lemma 5.1.14 and Theorem 5.1.15, parity is well defined; Theorem 5.1.16 and Proposition 5.1.17, the alternating group and its order; §5.1.4, historical note crediting Cauchy with cycle notation); §5.2 (Theorem 5.2.9, the rotations of a cube form a copy of $S_4$). record · 44 pages