Take a set and shuffle it. Every possible shuffle, all together, forms a group. That's the symmetric group, and it's the most hands-on group there is: its elements are things you can actually do to a row of objects. This page builds the notation for writing shuffles down (two of them, one much better than the other), works out the order of any shuffle at a glance, finds tiny sets of shuffles that generate everything, and splits every shuffle into "even" and "odd" in a way that can never be ambiguous.
A shuffle of a set $A$ is a function from $A$ to itself that doesn't lose anything (injective) and doesn't miss anything (surjective). In other words, a bijection.
Bijections, composition, and inverse functions all come from Functions. That page read $g \circ f$ right to left ($f$ first, then $g$), and so does this one.
Let $A$ be a nonempty set. The symmetric group on $A$ is
$$S_A = \{\text{bijections } \sigma : A \rightarrow A\}$$
with the binary operation of composition of maps.
Composing two bijections gives another bijection, so composition really is a binary operation on $S_A$. The name says "group," so let's earn it.
$S_A$ is a group.
Proof. We check the three axioms.
The elements get their own name, and one choice of $A$ is so common that it gets its own notation.
Elements $\sigma \in S_A$ are also called permutations of $A$.
Nothing about a permutation depends on what the elements of $A$ are called, only on how many there are. So we may as well call them $1, 2, \dots, n$.
If $A = \{1, 2, \dots, n\}$ for some $n \in \mathbb{N}$ then $S_A$ is called the symmetric group of degree $n$, and we write $S_n = S_A$.
As usual, when working with elements of $S_A$, we often suppress the group operation and write $\sigma_1 \sigma_2 = \sigma_1 \circ \sigma_2$. That shorthand hides a direction, and it's the single most common source of wrong answers on this page.
English reads left to right, Hebrew reads right to left, and permutations read whichever way the textbook felt like that day. Some books really do flip it.
To understand what a product of permutations in $S_A$ does to elements of $A$, work from right to left. If $\sigma_1, \sigma_2 \in S_A$ and $a \in A$, then
$$(\sigma_1 \sigma_2)(a) = \sigma_1(\sigma_2(a)).$$
The permutation written closest to $a$ goes first. Other books (and other professors) sometimes compose left to right, so check the convention before you compare answers.
The most direct way to write down $\sigma \in S_n$ is to list every input with its output underneath.
Cauchy's notation: Denote $\sigma \in S_n$ by
$$\begin{pmatrix} 1 & 2 & 3 & \dots & n-1 & n \\ \sigma(1) & \sigma(2) & \sigma(3) & \dots & \sigma(n-1) & \sigma(n) \end{pmatrix}$$
The bottom row is the top row, rearranged. Each number appears in it exactly once, which is just "bijection" in disguise.
Example. $n = 12$, and $\sigma \in S_{12}$ is the permutation
$$\begin{align*} 1 &\mapsto 3 & 4 &\mapsto 11 & 7 &\mapsto 4 & 10 &\mapsto 10 \\ 2 &\mapsto 9 & 5 &\mapsto 2 & 8 &\mapsto 12 & 11 &\mapsto 1 \\ 3 &\mapsto 7 & 6 &\mapsto 6 & 9 &\mapsto 5 & 12 &\mapsto 8 \end{align*}$$
Write $\sigma$ in Cauchy's notation.
Read off the outputs in order:
$$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 3 & 9 & 7 & 11 & 2 & 6 & 4 & 12 & 5 & 10 & 1 & 8 \end{pmatrix}$$
Keep this one in mind. It comes back twice.
How many permutations are there? Build one by choosing the bottom row from left to right.
For the count: there are $n$ choices for $\sigma(1)$, then $n - 1$ choices for $\sigma(2)$ (anything except $\sigma(1)$), and so on, down to $1$ choice for $\sigma(n)$.
A $52$-card deck has $52! \approx 8 \times 10^{67}$ orderings. A well-shuffled deck is almost certainly in an order no one has ever held before.
On Groups of Order 1–3 we showed there's only one group of each of those sizes, and it's cyclic. That's all the isomorphisms $S_1 \cong C_1$ and $S_2 \cong C_2$ need.
For $S_2$ we can even name the generator. Let $\sigma = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix} \in S_2$. Then $S_2 = \langle \sigma \rangle$, because
$$\sigma^2 = \sigma \cdot \sigma = \begin{pmatrix} 1 & 2 \\ 1 & 2 \end{pmatrix} = e.$$
From $n = 3$ on, the order of the shuffles starts to matter.
For $n \ge 3$, $S_n$ is non-Abelian.
Proof. Let
$$\sigma = \begin{pmatrix} 1 & 2 & 3 & \dots & n \\ 2 & 1 & 3 & \dots & n \end{pmatrix} \quad (\sigma(1) = 2, \ \sigma(2) = 1, \ \sigma(i) = i \text{ for } i \neq 1 \text{ or } 2)$$
and
$$\tau = \begin{pmatrix} 1 & 2 & 3 & 4 & \dots & n \\ 3 & 2 & 1 & 4 & \dots & n \end{pmatrix} \quad (\tau(1) = 3, \ \tau(3) = 1, \ \tau(i) = i \text{ for } i \neq 1 \text{ or } 3).$$
Then $(\sigma \tau)(1) = \sigma(\tau(1)) = \sigma(3) = 3$, but $(\tau \sigma)(1) = \tau(\sigma(1)) = \tau(2) = 2$, so $\sigma \tau \neq \tau \sigma$. $\blacksquare$
So $S_3$ is a non-Abelian group of order $6$. We've seen one of those before.
Groups of Order 4–8 showed that every group of order $6$ is $C_6$ or $D_6$, and promised that $S_3 \cong D_6$. The last Exercise on this page collects on that promise.
Let $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \end{pmatrix}$ and $\tau = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{pmatrix}$ in $S_4$. Compute $\sigma \tau$ and $\tau \sigma$ in Cauchy's notation.
Right to left: for $\sigma \tau$, apply $\tau$ first.
$$\begin{align*} (\sigma\tau)(1) &= \sigma(2) = 4, & (\sigma\tau)(2) &= \sigma(1) = 2, & (\sigma\tau)(3) &= \sigma(4) = 3, & (\sigma\tau)(4) &= \sigma(3) = 1, \\ (\tau\sigma)(1) &= \tau(2) = 1, & (\tau\sigma)(2) &= \tau(4) = 3, & (\tau\sigma)(3) &= \tau(1) = 2, & (\tau\sigma)(4) &= \tau(3) = 4. \end{align*}$$
$$\sigma \tau = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 2 & 3 & 1 \end{pmatrix}, \qquad \tau \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 3 & 2 & 4 \end{pmatrix}.$$
Different answers, as the Proposition warned.
Cauchy's notation is honest but wasteful: it writes down every number, even the ones that don't move, and it hides the shape of the permutation. Follow the arrows instead. In the $n = 12$ example, $1 \mapsto 3 \mapsto 7 \mapsto 4 \mapsto 11 \mapsto 1$, a loop. Permutations are made of loops, and cycle notation writes down the loops.
Suppose $k, n \in \mathbb{N}$, $1 \le k \le n$, and that $a_1, \dots, a_k \in \{1, 2, \dots, n\}$ satisfy $a_i \neq a_j$ for $i \neq j$. The $k$-cycle $(a_1 a_2 \dots a_k)$ is the permutation $\sigma \in S_n$ defined by
$$\sigma(a_1) = a_2, \ \sigma(a_2) = a_3, \ \dots, \ \sigma(a_{k-1}) = a_k, \ \sigma(a_k) = a_1,$$
and $\sigma(i) = i$ for $i \notin \{a_1, \dots, a_k\}$.
Each entry goes to the next one, the last one wraps around to the first, and everything not listed stays put. The shortest cycles are a little silly.
Writing $(7)$ for the identity is technically correct and deeply unhelpful, like answering "where are you?" with "here."
A $1$-cycle $(a_1)$ sends $a_1$ to itself and fixes everything else, so $1$-cycles represent the identity element. The $2$-cycles, which just swap two things, are the stars of the second half of this page.
$2$-cycles are also called transpositions.
Since a cycle is a loop, it doesn't matter where you start reading it.
For $k \ge 2$, there are $k$ different ways of representing the same $k$-cycle:
$$(a_1 a_2 \dots a_k) = (a_2 a_3 \dots a_k a_1) = (a_3 a_4 \dots a_k a_1 a_2) = \dots = (a_k a_1 a_2 \dots a_{k-1}).$$
So $(1 2 3) = (2 3 1) = (3 1 2)$, but $(1 2 3) \neq (1 3 2)$: rotating a cycle is harmless, reordering it is not. Here are some translations, all in $S_5$.
Examples ($n = 5$). Convert each of these five permutations from Cauchy's notation to cycle notation.
$$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 1 & 4 & 3 \end{pmatrix}, \quad \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 3 & 2 & 5 \end{pmatrix}, \quad \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 4 & 5 \end{pmatrix},$$
$$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 5 & 2 & 4 & 3 \end{pmatrix}, \quad \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 3 & 4 & 1 \end{pmatrix}$$
Start at any number that moves and follow it until you get back.
$$\begin{align*} \text{Cauchy notation} &\quad \quad \text{Cycle notation} \\ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 1 & 4 & 3 \end{pmatrix} &\rightarrow \quad \quad (1 2 5 3) \\ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 3 & 2 & 5 \end{pmatrix} &\rightarrow \quad \quad (2 4) \\ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 4 & 5 \end{pmatrix} &\rightarrow \quad \quad e \\ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 5 & 2 & 4 & 3 \end{pmatrix} &\rightarrow \quad \quad (2 5 3) \\ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 3 & 4 & 1 \end{pmatrix} &\rightarrow \quad \quad (1 2)(2 5) \end{align*}$$
The last answer is a product of two cycles. To check it, compute $\sigma\tau$ with $\sigma = (1 2)$ and $\tau = (2 5)$, right to left:
$$\begin{align*} (\sigma \tau)(1) &= \sigma(\tau(1)) = \sigma(1) = 2 \\ (\sigma \tau)(2) &= \sigma(\tau(2)) = \sigma(5) = 5 \\ (\sigma \tau)(3) &= \sigma(\tau(3)) = \sigma(3) = 3 \\ (\sigma \tau)(4) &= \sigma(\tau(4)) = \sigma(4) = 4 \\ (\sigma \tau)(5) &= \sigma(\tau(5)) = \sigma(2) = 1 \end{align*}$$
So it matches. Notice that $(1 2)(2 5) = (1 2 5)$: following $1 \mapsto 2 \mapsto 5 \mapsto 1$ would have written the same permutation as a single cycle.
Multiplying cycles by hand is where the right-to-left rule bites. Feed each number in on the right, let it ride through each cycle in turn, and see where it comes out.
Pick a pair of cycles, then tap a number to send it through the right-hand cycle first, then the left. Flip the order and compare.
That last example gave a product of two cycles that overlap (both move $2$). Here's another product, this time in $S_5$ with the cycles kept apart:
$$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 1 & 2 \end{pmatrix} \rightarrow \quad (1 3 4)(2 5).$$
The cycles $(1 3 4)$ and $(2 5)$ don't share any numbers, and that turns out to be the nice case.
Two cycles $(a_1 \dots a_k)$ and $(b_1 \dots b_l)$ are disjoint if $a_i \neq b_j$, $\forall 1 \le i \le k$, $1 \le j \le l$.
In other words, no number appears in both.
Examples. Are the cycles in each product disjoint?
The first product is non-disjoint ($2$ appears in both cycles). The second is disjoint.
Disjoint cycles stay out of each other's way, so it doesn't matter which one goes first.
If $\sigma, \tau \in S_n$ are disjoint cycles then $\sigma \tau = \tau \sigma$. (Disjoint cycles commute.)
Why: take any $a \in \{1, \dots, n\}$. If $\tau$ moves $a$, then $\tau(a)$ is also in $\tau$'s cycle, so $\sigma$ fixes both $a$ and $\tau(a)$, and $\sigma\tau(a) = \tau(a) = \tau\sigma(a)$. The same argument works if $\sigma$ moves $a$, and if neither moves $a$, both sides give $a$. $\blacksquare$
This is not true in general if $\sigma$ and $\tau$ overlap. We just saw $(1 2)(2 5) = (1 2 5)$, but
$$(2 5)(1 2) = (1 5 2) \neq (1 2 5).$$
Only swap the order of cycles when you've checked they're disjoint.
Every example so far broke into loops that don't overlap. That always works.
Every element $\sigma \in S_n$ can be written as a product of disjoint cycles (i.e. every pair of cycles in the product is disjoint). This product is called the cycle decomposition of $\sigma$, and it is unique up to the order in which the cycles appear.
We omit $1$-cycles in the cycle decomposition, and we write the identity in $S_n$ as $e$.
The algorithm below proves that a decomposition exists. It's also unique, because nothing in it was a choice: whichever cycle contains $i$ has to read $(i \ \sigma(i) \ \sigma^2(i) \dots)$, and the order of disjoint cycles doesn't matter because they commute.
The cycles of $\sigma$ are the equivalence classes of the relation "$i \sim j$ if $j = \sigma^m(i)$ for some $m \in \mathbb{Z}$." So by Logic & Equivalence Classes, the cycles (including the $1$-cycles we leave out) form a partition of $\{1, 2, \dots, n\}$.
Algorithm to find the cycle decomposition of $\sigma \in S_n$. Running example: $n = 12$,
$$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 3 & 9 & 7 & 11 & 2 & 6 & 4 & 12 & 5 & 10 & 1 & 8 \end{pmatrix}$$
Now run the algorithm yourself. The widget won't let you skip a step: you choose where each number goes next, and it only accepts $\sigma$'s answer.
Read the table, then tap the dot where the current number goes. When a loop closes, start the next one at the smallest number not used yet.
The cycle decomposition is the best way to find the order of a permutation. Computing $\sigma, \sigma^2, \sigma^3, \dots$ in Cauchy's notation until you hit $e$ works too, if you have all afternoon.
The order $|g|$ is the smallest $k \in \mathbb{N}$ with $g^k = e$ (Subgroups & Lagrange's Theorem), and on Cyclic Groups we proved that $g^m = e \iff |g| \mid m$. Both get used below.
If $\sigma \in S_n$ is a $k$-cycle then $|\sigma| = k$.
Proof. Write $\sigma = (a_1 \dots a_k)$. Each power of $\sigma$ moves every $a_i$ one more step around the loop, so $\forall 1 \le i \le k$, $\sigma^k(a_i) = a_i$. Since $\sigma$ also fixes everything outside the cycle, it follows that $\sigma^k = e$, so $|\sigma| \le k$. On the other hand, $\forall 1 \le j \lt k$, $\sigma^j(a_1) = a_{1+j} \neq a_1$, so $\sigma^j \neq e$. Therefore $|\sigma| = k$. $\blacksquare$
For a product of disjoint cycles, each cycle spins on its own, and the whole thing is back to $e$ only when every cycle is home at the same time.
If $\sigma_1, \dots, \sigma_l \in S_n$ are disjoint cycles then
$$|\sigma_1 \sigma_2 \dots \sigma_l| = \text{lcm}(|\sigma_1|, |\sigma_2|, \dots, |\sigma_l|).$$
The lcm on Properties of Integers was defined by divisibility: it divides every common multiple. That's exactly the property the last step of the proof uses.
Proof. Let $\sigma = \sigma_1 \sigma_2 \dots \sigma_l$, write $k_i = |\sigma_i|$, and let $M_i \subseteq \{1, \dots, n\}$ be the set of numbers that appear in the cycle $\sigma_i$. The sets $M_1, \dots, M_l$ are pairwise disjoint.
Step 1. Disjoint cycles commute, so we can rearrange the factors of $\sigma^m$ freely. For every $m \in \mathbb{N}$,
$$\sigma^m = (\sigma_1 \sigma_2 \cdots \sigma_l)(\sigma_1 \sigma_2 \cdots \sigma_l) \cdots (\sigma_1 \sigma_2 \cdots \sigma_l) = \sigma_1^m \sigma_2^m \cdots \sigma_l^m.$$
Step 2. Each $\sigma_j^m$ fixes everything outside $M_j$, and sends $M_j$ into $M_j$. So if $a \in M_i$, every factor other than $\sigma_i^m$ fixes both $a$ and $\sigma_i^m(a)$, and
$$\sigma^m(a) = \sigma_i^m(a).$$
If $a$ is in none of the $M_i$, then $\sigma^m(a) = a$.
Step 3. By Step 2, $\sigma^m = e$ if and only if $\sigma_i^m(a) = a$ for every $i$ and every $a \in M_i$. Since $\sigma_i^m$ fixes everything outside $M_i$ anyway, that says
$$\sigma^m = e \iff \sigma_i^m = e \text{ for all } i \iff k_i \mid m \text{ for all } i \iff \text{lcm}(k_1, \dots, k_l) \mid m,$$
using $g^m = e \iff |g| \mid m$ and the defining property of lcm. The smallest $m \in \mathbb{N}$ divisible by $\text{lcm}(k_1, \dots, k_l)$ is the lcm itself, so $|\sigma| = \text{lcm}(k_1, \dots, k_l)$. $\blacksquare$
Back to the running example, one last time.
Example. Find the order of
$$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 3 & 9 & 7 & 11 & 2 & 6 & 4 & 12 & 5 & 10 & 1 & 8 \end{pmatrix}.$$
$$\begin{align*} \sigma &= (1 \ 3 \ 7 \ 4 \ 11)(2 \ 9 \ 5)(8 \ 12) \quad \text{(orders } 5, 3, 2\text{)} \\ \text{So } |\sigma| &= \text{lcm}(5, 3, 2) = 30. \end{align*}$$
Watch it happen. Each cycle is a ring of beads, and every press of the button applies $\sigma$ once, turning each ring one notch. A ring is home when its beads are back where they started. $\sigma^m = e$ exactly when all of them are home together.
Choose a permutation and predict its order. Then apply $\sigma$ until every ring is home at once.
Find the cycle decomposition and the order of
$$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 5 & 1 & 8 & 4 & 9 & 3 & 7 & 6 & 2 \end{pmatrix} \in S_9.$$
Start at $1$: $1 \mapsto 5 \mapsto 9 \mapsto 2 \mapsto 1$, giving $(1 5 9 2)$. The smallest unused number is $3$: $3 \mapsto 8 \mapsto 6 \mapsto 3$, giving $(3 8 6)$. Then $4$ and $7$ are fixed. So
$$\sigma = (1 5 9 2)(3 8 6), \qquad |\sigma| = \text{lcm}(4, 3) = 12.$$
What is the largest possible order of an element of $S_7$?
The order only depends on the lengths of the disjoint cycles, and those lengths (counting $1$-cycles) add up to $7$. So list the ways to write $7$ as a sum, and take the lcm of each:
$$\begin{array}{llll} 7: 7 & 6+1: 6 & 5+2: 10 & 5+1+1: 5 \\ 4+3: 12 & 4+2+1: 4 & 4+1+1+1: 4 & 3+3+1: 3 \\ 3+2+2: 6 & 3+2+1+1: 6 & 3+1+1+1+1: 3 & 2+2+2+1: 2 \end{array}$$
(and the remaining sums, made of $2$s and $1$s, give $1$ or $2$). The largest is $12$, from a $4$-cycle times a disjoint $3$-cycle, e.g. $(1 2 3 4)(5 6 7)$. Notice that the biggest cycle, the $7$-cycle, is not the winner: lcm rewards cycle lengths with no common factors.
$S_n$ has $n!$ elements, but you only need a handful of them to build all the rest. All three facts below say "these few permutations generate $S_n$," each with a smaller set than the last.
$\langle S \rangle$ is the smallest subgroup containing $S$ (Subgroups & Lagrange's Theorem): if $H$ is a subgroup and $S \subseteq H$, then $\langle S \rangle \le H$. The proofs of 1b and 2 run on that sentence.
$S_n = \langle \{(i \ j) : 1 \le i \lt j \le n\} \rangle$. ($S_n$ is generated by transpositions.)
Proof. Every element of $S_n$ is a product of cycles (Cycle Decomposition Algorithm). Therefore it is enough to show that every cycle can be written as a product of transpositions.
Check the $3$-cycle formula right to left before trusting it: $a_1 \mapsto a_2$ (the first factor), and then $(a_1 \ a_3)$ leaves $a_2$ alone. Read left to right, the same product would be $(a_1 \ a_2 \ a_3)^{-1}$, which is the classic wrong answer.
We can do with far fewer transpositions. Only the ones that swap neighbors are needed.
$S_n = \langle \{(i \ i+1) : 1 \le i \lt n\} \rangle$
Proof. Write $H = \langle \{(i \ i+1) : 1 \le i \lt n\} \rangle$. Then, after playing around with products,
$$\begin{align*} (2 \ 3)(1 \ 2)(2 \ 3) &= (1 \ 3) \in H \\ (3 \ 4)(1 \ 3)(3 \ 4) &= (1 \ 4) \in H \\ (4 \ 5)(1 \ 4)(4 \ 5) &= (1 \ 5) \in H \\ &\ \ \vdots \\ (n-1 \ n)(1 \ n-1)(n-1 \ n) &= (1 \ n) \in H. \end{align*}$$
Similarly, $\forall 1 \le i \le n-2$:
$$\begin{align*} (i+1 \ i+2)(i \ i+1)(i+1 \ i+2) &= (i \ i+2) \in H \\ (i+2 \ i+3)(i \ i+2)(i+2 \ i+3) &= (i \ i+3) \in H \\ &\ \ \vdots \\ (n-1 \ n)(i \ n-1)(n-1 \ n) &= (i \ n) \in H. \end{align*}$$
Therefore, $\forall 1 \le i \lt j \le n$, $(i \ j) \in H$, which implies that $S_n = \langle \{(i \ j) : 1 \le i \lt j \le n\} \rangle \le H$ (from 1a). Conclusion: $H = S_n$. $\blacksquare$
Each line of that proof is the same trick: sandwiching $(a \ b)$ between two copies of $(b \ c)$ renames $b$ to $c$, giving $(a \ c)$. And we can go smaller still. Two permutations are enough.
For $n \ge 2$, $S_n = \langle (1 \ 2), (1 \ 2 \dots n) \rangle$.
Proof. Let $H = \langle (1 \ 2), (1 \ 2 \dots n) \rangle$. Then:
$$\begin{align*} (1 \ 2 \dots n)^{-1} &= (n \ n-1 \dots 2 \ 1) \in H \\ (1 \ 2 \dots n)(1 \ 2)(n \ n-1 \dots 3 \ 2 \ 1) &= (2 \ 3) \in H \\ (1 \ 2 \dots n)(2 \ 3)(n \ n-1 \dots 3 \ 2 \ 1) &= (3 \ 4) \in H \\ &\ \ \vdots \\ (1 \ 2 \dots n)(n-2 \ n-1)(n \ n-1 \dots 3 \ 2 \ 1) &= (n-1 \ n) \in H. \end{align*}$$
So $\{(i \ i+1) : 1 \le i \lt n\} \subseteq H \implies S_n = \langle \{(i \ i+1) : 1 \le i \lt n\} \rangle \le H \implies H = S_n$ (from 1b). $\blacksquare$
Here the sandwich is $(1 \ 2 \dots n)$ and its inverse, and it shifts both numbers in a transposition up by one. Two buttons, then: one that swaps the front two and one that rotates everything. That's enough to reach any arrangement at all.
You can only swap the first two tiles or rotate the whole row. Rebuild the target row.
Write $(1 2 3 4 5)$ as a product of transpositions. Then write it as a product of transpositions of the form $(i \ i+1)$.
By the $k$-cycle formula in Fact 1a,
$$(1 2 3 4 5) = (1 5)(1 4)(1 3)(1 2).$$
For neighbors only, there's a shortcut:
$$(1 2 3 4 5) = (1 2)(2 3)(3 4)(4 5).$$
Check it right to left: $1$ is fixed by $(4 5)$, $(3 4)$, $(2 3)$, then $(1 2)$ sends it to $2$. $2$ is fixed until $(2 3)$ sends it to $3$, which $(1 2)$ leaves alone. Likewise $3 \mapsto 4$ and $4 \mapsto 5$. Finally $5 \mapsto 4 \mapsto 3 \mapsto 2 \mapsto 1$. So the product is $(1 2 3 4 5)$. (Expanding $(1 5)$, $(1 4)$, $(1 3)$ with the sandwiches from 1b also works, just with many more factors.)
Every permutation is a product of transpositions, so we can sort them by how many transpositions it takes.
A permutation $\sigma \in S_n$ is odd if it can be written as a product of an odd number of transpositions, and it is even if it can be written as a product of an even number of transpositions.
Here's how a few elements sort out.
Examples. Decide whether each permutation is even or odd: $e$, $(1 \ 3)$, $(1 \ 2 \ 3)$, $(4 \ 1 \ 3)(3 \ 2 \ 1 \ 4)$.
$$\begin{align*} e &= \text{(empty product)} \quad &&\text{(even)} \\ (1 \ 3) & &&\text{(odd)} \\ (1 \ 2 \ 3) &= (1 \ 3)(1 \ 2) &&\text{(even)} \\ (4 \ 1 \ 3)(3 \ 2 \ 1 \ 4) &= (4 \ 3)(4 \ 1)(3 \ 4)(3 \ 1)(3 \ 2) &&\text{(odd)} \end{align*}$$
The last one uses the $3$-cycle and $4$-cycle formulas from Fact 1a on each factor.
Two things are worth noticing.
That second note is worrying. If there are so many ways to write $\sigma$, couldn't one of them use an even number of transpositions and another an odd number? The definition doesn't rule it out.
The 15-puzzle with the $14$ and $15$ tiles swapped can't be solved by sliding. The urge to pop the tiles out with a butter knife is strong. That's a single transposition: legal in real life, illegal in $A_n$.
Every element of $S_n$ is either even or odd, but not both.
The proof tracks one number. For $\sigma \in S_n$, let
$$K(\sigma) = \#\{\text{cycles in cycle decomp. of } \sigma\} + \#\{1 \le i \le n : \sigma(i) = i\}.$$
That's the number of loops in $\sigma$ if you count each fixed point as a loop of length $1$. So $K(e) = n$. The key claim is that multiplying by a single transposition always changes $K$ by exactly $1$, up or down. Try it: sort a scrambled row by swapping tiles, and keep an eye on $K$.
Tap two tiles to swap them. Sort the row back to $1, 2, \dots, n$ and see whether you can ever change the parity of your swap count.
Here's why $K$ always moves by exactly one. A transposition $(i \ j)$ either cuts a cycle in two (when $i$ and $j$ are in the same cycle) or glues two cycles into one (when they aren't):
Claim: $\forall \sigma \in S_n$ and $\forall (i \ j) \in S_n$, $K((i \ j)\sigma) = K(\sigma) \pm 1$.
Proof of claim. There are $2$ cases to consider.
Case 1: $i$ and $j$ both appear in the same cycle in the cycle decomposition of $\sigma$. Then that cycle has one of $4$ forms: $(i \ j)$, $(i \ a_1 \dots a_k \ j)$, $(i \ j \ b_1 \dots b_l)$, or $(i \ a_1 \dots a_k \ j \ b_1 \dots b_l)$. Note:
$$\begin{align*} (i \ j)(i \ j) &= e &&(-1 \text{ cycle}, +2 \text{ fixed points}) \\ (i \ j)(i \ a_1 \dots a_k \ j) &= (i \ a_1 \dots a_k) &&(+1 \text{ fixed point}) \\ (i \ j)(i \ j \ b_1 \dots b_l) &= (j \ b_1 \dots b_l) &&(+1 \text{ fixed point}) \\ (i \ j)(i \ a_1 \dots a_k \ j \ b_1 \dots b_l) &= (i \ a_1 \dots a_k)(j \ b_1 \dots b_l) &&(+1 \text{ cycle}) \end{align*}$$
All other cycles are disjoint from $(i \ j)$, so they're unchanged. Therefore $K((i \ j)\sigma) = K(\sigma) + 1$.
Case 2: $i$ and $j$ do not appear in the same cycle in the cycle decomposition of $\sigma$. Write the cycles that they appear in as $(i \ a_1 \dots a_k)$ (or $(i)$ if $\sigma(i) = i$) and $(j \ b_1 \dots b_l)$ (or $(j)$ if $\sigma(j) = j$). Then:
$$(i \ j)(i \ a_1 \dots a_k)(j \ b_1 \dots b_l) = (i \ a_1 \dots a_k \ j \ b_1 \dots b_l).$$
All other cycles are disjoint from $(i \ j)$. Considering all $4$ possibilities again (each of the two cycles is either a real cycle or a fixed point), two loops always become one, so $K((i \ j)\sigma) = K(\sigma) - 1$. This proves the claim.
Proof of the theorem. Now suppose that $\sigma \in S_n$ and that $\sigma = (a_1 \ b_1)(a_2 \ b_2) \dots (a_k \ b_k)$ and $\sigma = (c_1 \ d_1)(c_2 \ d_2) \dots (c_l \ d_l)$. Then
$$(a_1 \ b_1)(a_2 \ b_2) \dots (a_k \ b_k) = (c_1 \ d_1)(c_2 \ d_2) \dots (c_l \ d_l).$$
Multiply on the left by $(a_1 \ b_1)$, then by $(a_2 \ b_2)$, and so on (each transposition is its own inverse):
$$\begin{align*} \implies (a_2 \ b_2) \dots (a_k \ b_k) &= (a_1 \ b_1)(c_1 \ d_1)(c_2 \ d_2) \dots (c_l \ d_l) \\ \implies (a_3 \ b_3) \dots (a_k \ b_k) &= (a_2 \ b_2)(a_1 \ b_1)(c_1 \ d_1)(c_2 \ d_2) \dots (c_l \ d_l) \\ &\ \ \vdots \\ e &= (a_k \ b_k) \dots (a_1 \ b_1)(c_1 \ d_1) \dots (c_l \ d_l). \end{align*}$$
Now compute $K$ of the right-hand side by building it up one transposition at a time, starting from $e$. By the claim, each of the $k + l$ transpositions changes $K$ by $\pm 1$:
$$K(e) = K((a_k \ b_k) \dots (a_1 \ b_1)(c_1 \ d_1) \dots (c_{l-1} \ d_{l-1})(c_l \ d_l)e)$$
$$n = K(e) \pm 1 \pm 1 \dots \pm 1 = n \pm \underbrace{1 \pm \dots \pm 1}_{k} \pm \underbrace{1 \pm \dots \pm 1}_{l}.$$
So a sum of $k + l$ terms, each $\pm 1$, equals $0$. Since $1 \equiv -1 \pmod 2$, this gives $0 \equiv k + l \pmod 2$, so $k \equiv l \pmod 2$. Any two ways of writing $\sigma$ use numbers of transpositions with the same parity, so $\sigma$ can't be both even and odd. $\blacksquare$
Prove that a $k$-cycle is even if and only if $k$ is odd.
Proof. By the $k$-cycle formula in Fact 1a,
$$(a_1 \ a_2 \dots a_k) = (a_1 \ a_k)(a_1 \ a_{k-1}) \dots (a_1 \ a_3)(a_1 \ a_2),$$
a product of $k - 1$ transpositions. (For $k = 1$ this is the empty product, which is $e$.) So the $k$-cycle is even if $k - 1$ is even and odd if $k - 1$ is odd. By the theorem it can't be both, so it is even if and only if $k - 1$ is even, that is, if and only if $k$ is odd. $\blacksquare$
So the names are backwards on purpose: $3$-cycles are even, transpositions are odd.
Now that "even" is a well-defined property, collect the even permutations together.
The finite subgroup test from Subgroups & Lagrange's Theorem: a nonempty subset of a finite group that's closed under the operation is automatically a subgroup. Inverses come for free.
The subset $A_n \subseteq S_n$ consisting of all even permutations is non-empty ($e \in A_n$) and closed under multiplication (an even number of transpositions followed by another even number is still an even number). Since $S_n$ is finite, the finite subgroup test says $A_n$ is a subgroup.
The subgroup $A_n \le S_n$ consisting of all even permutations is called the alternating group of degree $n$.
Exactly half of $S_n$ makes the cut.
If $n \ge 2$ then $|A_n| = \dfrac{n!}{2}$.
Proof. This follows from the fact that the map $\sigma \mapsto (1 \ 2)\sigma$ is a bijection from the collection of even permutations to the collection of odd permutations. If $\sigma$ is even, then $(1 \ 2)\sigma$ is a product of an odd number of transpositions, so it's odd. The map is injective, since $(1 \ 2)\sigma = (1 \ 2)\sigma'$ implies $\sigma = \sigma'$. It's surjective, since any odd $\tau$ is $(1 \ 2)\big((1 \ 2)\tau\big)$, and $(1 \ 2)\tau$ is even. So there are exactly as many even permutations as odd ones. By the theorem, every element of $S_n$ is exactly one of the two, so $|A_n| = \frac{|S_n|}{2} = \frac{n!}{2}$. $\blacksquare$
Small cases first.
Examples. List the elements of $A_1$, $A_2$, $A_3$, and $A_4$.
$A_1$, $A_2$, $A_3$ are all cyclic, so they're Abelian. That stops at $n = 4$.
For $n \ge 4$, $A_n$ is non-Abelian.
Proof. Suppose $n \ge 4$, $\sigma = (1 \ 2 \ 3)$, and $\tau = (1 \ 4 \ 2)$. Then $\sigma, \tau \in A_n$ ($3$-cycles are even), $\sigma \tau = (1 \ 4 \ 3)$, and $\tau \sigma = (2 \ 3 \ 4)$. Therefore $A_n$ is non-Abelian for $n \ge 4$. $\blacksquare$
$A_n$ has index $2$ in $S_n$, and on Normal Subgroups that's enough to make it a normal subgroup. It's also the kernel of the sign map, which sends even permutations to $1$ and odd ones to $-1$.
To finish, the promise from Groups of Order 4–8.
List the elements of $S_3$ in cycle notation and sort them into even and odd. Then show that $S_3 \cong D_6$.
$|S_3| = 3! = 6$:
$$S_3 = \{\underbrace{e, (1 2 3), (1 3 2)}_{\text{even: } A_3}, \underbrace{(1 2), (1 3), (2 3)}_{\text{odd}}\}.$$
By the classification on Groups of Order 4–8, every group of order $6$ is isomorphic to $C_6$ or $D_6$. $C_6$ is Abelian, but $S_3$ is not (the Proposition with $n = 3$). So $S_3 \cong D_6$.
Geometrically: label the corners of a triangle $1, 2, 3$. Each rigid motion rearranges the corners, the rotations give the $3$-cycles, and the flips give the transpositions.
Transpositions generate $S_n$, but they're all odd, so they can't live in $A_n$. What generates $A_n$, then?
Prove that for $n \ge 3$, $A_n$ is generated by the $3$-cycles:
$$A_n = \langle \{(a \ b \ c) : a, b, c \in \{1, \dots, n\} \text{ distinct}\} \rangle.$$
Proof. Let $H$ be the subgroup generated by the $3$-cycles.
$H \le A_n$: every $3$-cycle is even (it's $(a \ c)(a \ b)$), so every $3$-cycle lies in the subgroup $A_n$, and therefore $H = \langle \text{3-cycles} \rangle \le A_n$.
$A_n \le H$: let $\sigma \in A_n$, and write $\sigma$ as a product of an even number of transpositions. Group them in consecutive pairs, so $\sigma$ is a product of terms $(a \ b)(c \ d)$. It's enough to show each such pair lies in $H$. There are three possibilities.
(Check the last two right to left. In the second, $a \mapsto c$, $c \mapsto a \mapsto b$, $b \mapsto a$.) So every element of $A_n$ is a product of elements of $H$, and $A_n \le H$. Therefore $A_n = H$. $\blacksquare$
The disjoint case is where a careless proof goes wrong: you can't write $(a \ b)(c \ d)$ as a single $3$-cycle, since it moves four numbers. Inserting $(b \ c)(b \ c) = e$ in the middle is the trick.