By Cayley’s theorem, left multiplication embeds a group \(G\) in the symmetric group on the set \(G\). The sign \(\operatorname{sgn}\colon S_n\to\{\pm1\}\) is a homomorphism, and a cycle of length \(\ell\) has sign \((-1)^{\ell-1}\). Two permutations in \(S_n\) are conjugate if and only if they have the same cycle type, so the conjugacy classes of \(S_n\) correspond to the partitions of \(n\). The alternating group \(A_n\) is simple for \(n\ge5\), so \(S_n\) is not solvable for \(n\ge5\). The Galois group of an irreducible separable polynomial of degree \(n\) is a transitive subgroup of \(S_n\).
Transposition presentation of the symmetric group (Tag D-6BTFJ)
Let \(n\geq 2\). The symmetric group \(S_n\) is the group with presentation \[ S_n \coloneqq \gens{ \sigma_1, \ldots, \sigma_{n-1} \st \sigma_i^2 \ (1\leq i\leq n-1),\ \sigma_i\sigma_j\sigma_i^{-1}\sigma_j^{-1} \ (\abs{i-j}\geq 2),\ \sigma_i \sigma_{i+1} \sigma_i \sigma_{i+1}^{-1} \sigma_i^{-1} \sigma_{i+1}^{-1} \ (1\leq i\leq n-2) }. \]
Sending \(\sigma_i\) to the transposition \((i, i+1)\) identifies this group with the group of bijections of \(\theset{1, \ldots, n}\).
Sign homomorphism (Tag D-BZ3KD)
Let \(n\geq 1\). The sign homomorphism is the map \[ \sgn\colon S_n \to (\ZZ/2, +), \qquad \sigma \mapsto k \bmod 2, \] where \(\sigma = \tau_1 \cdots \tau_k\) is any expression of \(\sigma\) as a product of \(k\geq 0\) transpositions.
Let \(n \geq 1\). For \(\sigma\in S_n\), all expressions of \(\sigma\) as a product of transpositions have the same number of factors modulo \(2\), so \(\sgn\) is well defined, and \(\sgn\) is a group homomorphism.
Even and odd permutations (Tag FD-PIVQZ)
Let \(\varepsilon\colon S_n\to\theset{\pm1}\) be the sign homomorphism and \(\sigma\in S_n\). The permutation \(\sigma\) is even if \(\varepsilon(\sigma) = 1\) and odd if \(\varepsilon(\sigma) = -1\).
Since every permutation is a product of transpositions and each transposition has sign \(-1\), a product of \(t\) transpositions has sign \((-1)^t\). So \(\sigma\) is even if and only if it is a product of an even number of transpositions, and odd if and only if it is a product of an odd number of transpositions.
Sign of a permutation from its cycle decomposition (Tag FD-GHDF2)
Let \(\sgn\colon S_n\to\theset{\pm1}\) be the sign homomorphism, and let \(\sigma\in S_n\) have disjoint cycle decomposition \(\sigma=c_1\cdots c_t\) with \(c_j\) a cycle of length \(k_j\). Then \[ \sgn(\sigma)=\prod_{j=1}^t(-1)^{k_j-1}. \] In particular, a cycle of length \(k\) is odd if and only if \(k\) is even, and \(\sigma\) is odd if and only if an odd number of the \(c_j\) have even length.
A \(k\)-cycle is a product of \(k-1\) transpositions: \((a_1\,a_2\,\cdots\,a_k)=(a_1\,a_k)(a_1\,a_{k-1})\cdots(a_1\,a_2)\). Since each transposition has sign \(-1\) and \(\sgn\) is a homomorphism, \(\sgn(c_j)=(-1)^{k_j-1}\), and the displayed formula follows by multiplying over \(j\). The factor \((-1)^{k_j-1}\) equals \(-1\) exactly when \(k_j\) is even, so the product equals \(-1\) exactly when the number of even-length cycles is odd.
Sign of $(1\,2\,3\,4\,5\,6)(7\,8\,9)(10\,11)(12\,13\,14\,15)(16\,17\,18)$ (Tag FF-6MNV6)
The permutation \(\sigma=(1\,2\,3\,4\,5\,6)(7\,8\,9)(10\,11)(12\,13\,14\,15)(16\,17\,18)\in S_{18}\) has sign \(\varepsilon(\sigma)=-1\).
A cycle of length \(\ell\) is a product of \(\ell-1\) transpositions, so its sign is \((-1)^{\ell-1}\) (FD-GHDF2). The disjoint cycles of \(\sigma\) have lengths \(6,3,2,4,3\), so \[ \varepsilon(\sigma)=(-1)^{5+2+1+3+2}=(-1)^{13}=-1. \] Equivalently, \(\sigma\) has three cycles of even length.
Alternating group (Tag D-TMME3)
Let \(n\geq 1\). A permutation \(\sigma\in S_n\) is even if \(\sgn(\sigma) = 0\), where \(\sgn\colon S_n\to\ZZ/2\) is the sign homomorphism. The alternating group is the subgroup of even permutations of the symmetric group: \[ A_n \coloneqq \theset{\sigma \in S_n \suchthat \sgn(\sigma) = 0} = \ker(\sgn). \]
A cycle of length \(\ell\) is a product of \(\ell-1\) transpositions, so a permutation is even if and only if its disjoint cycle decomposition has an even number of cycles of even length.
Alternating group (Tag FD-X4DBP)
Let \(n\geq 1\) and let \(\sgn\colon S_n\to\theset{\pm1}\) be the sign homomorphism. The alternating group is \[ A_n\coloneqq\ker(\sgn)=\theset{\sigma\in S_n \st \sgn(\sigma)=1}, \] the subgroup of even permutations of \(S_n\).
$A_n$ is generated by $3$-cycles (Tag PR-JY4PV)
For \(n\geq 3\), the alternating group \(A_n\) is generated by \(3\)-cycles.
Transitive subgroup of $S_n$ (Tag D-7UIPO)
Let \(n\geq 1\). A subgroup \(H\leq S_n\) is transitive if its action on \(\theset{1, \ldots, n}\) is transitive, that is, if for all \(i, j\in\theset{1,\ldots,n}\) there exists \(\sigma\in H\) with \(\sigma(i) = j\).
Subgroups of $S_n$ for $n$ prime containing an $n$-cycle (Tag PR-5PI25)
Let \(n\) be a prime and let \(G \leq S_n\) contain an \(n\)-cycle.
If \(G\) contains a transposition, then \(G = S_n\).
If \(n \geq 3\) and \(G\) contains a \(3\)-cycle, then \(G = A_n\) or \(G = S_n\).
For composite \(n\), a transposition and an \(n\)-cycle need not generate \(S_n\). In \(S_4\), the elements \((1\,3)\) and \((1\,2\,3\,4)\) preserve the partition \(\theset{\theset{1,3},\theset{2,4}}\), and they generate the dihedral group of order \(8\). The specific transposition \((1\,2)\) and the specific \(n\)-cycle \((1\,2\,\cdots\,n)\) do generate \(S_n\) for every \(n \geq 2\).
For composite \(n\), a \(3\)-cycle and an \(n\)-cycle need not generate a group containing \(A_n\). In \(S_6\), both \((1\,2\,3)\) and \((1\,4\,2\,5\,3\,6)\) preserve the partition \(\theset{\theset{1,2,3},\theset{4,5,6}}\), so the group they generate lies in the stabilizer of that partition, which has order \(72 < \abs{A_6} = 360\).
For the Galois group \(G \leq S_n\) of an irreducible separable polynomial \(f\) of degree \(n\), the action on the roots is transitive, so \(n \divides \abs{G}\) by the orbit-stabilizer theorem. If \(n\) is prime, Cauchy’s theorem gives an element of order \(n\) in \(G\), and every element of order \(n\) in \(S_n\) is an \(n\)-cycle.
Simple groups (Tag D-T2NZ4)
A group \(G\neq\theset{e}\) is simple if its only normal subgroups are \(\theset{e}\) and \(G\).
Simple group (Tag FD-2UWAQ)
A group \(G\) is simple if \(G\neq\theset{e}\) and its only normal subgroups are the trivial subgroup \(\theset{e}\) and \(G\) [@DF04].
A simple group with a proper subgroup of index $n$ embeds in $S_n$ (Tag PR-5FGA7)
Let \(G\) be a simple group and \(H < G\) a proper subgroup of finite index \([G:H] = n\). Then there is an injective group homomorphism \(\phi\colon G \injects S_n\).
The action of \(G\) on the set \(G/H\) of left cosets by \(g \cdot xH \coloneqq gxH\) gives a homomorphism \(\phi\colon G \to \operatorname{Sym}(G/H) \cong S_n\). If \(g \in \ker\phi\), then \(gH = H\), so \(\ker\phi \subseteq H \neq G\). Since \(\ker\phi\) is a normal subgroup of the simple group \(G\) and \(\ker\phi \neq G\), \(\ker\phi\) is trivial.
$S_n$ is solvable if and only if $n\leq 4$ (Tag T-EN5H4)
Let \(n\geq1\). The symmetric group \(S_n\) is solvable if and only if \(n\leq 4\).
For \(n\leq4\), \(S_n\) is isomorphic to a subgroup of \(S_4\), and subgroups of solvable groups are solvable. The series \(\theset{e}\normal V_4\normal A_4\normal S_4\), with \(V_4=\theset{e,(12)(34),(13)(24),(14)(23)}\), has abelian quotients \(V_4\), \(C_3\), and \(C_2\), so \(S_4\) is solvable.
For \(n\geq5\), \(A_n\) is simple and nonabelian. Its commutator subgroup \([A_n,A_n]\) is normal and nontrivial, so \([A_n,A_n]=A_n\), and the derived series of \(A_n\) is constant at \(A_n\) and never reaches \(\theset e\). Hence \(A_n\) is not solvable, and neither is \(S_n\), which contains it.
Number of abelian groups of order $n$ as a product of partition numbers (Tag PR-2JG3F)
Let \(n = \prod_{k=1}^m p_k^{e_k}\), where \(p_1, \ldots, p_m\) are distinct primes and \(e_1, \ldots, e_m \geq 1\), and for an integer \(e \geq 1\) let \(P(e)\) be the number of partitions of \(e\). Up to isomorphism, there are exactly \(\prod_{k=1}^m P(e_k)\) abelian groups of order \(n\).
Recurrence for the partition numbers $P_k(n)$ and $P(n)$ (Tag PR-434DX)
For integers \(m \geq 0\) and \(k \geq 0\), let \(P_k(m)\) be the number of partitions of \(m\) into exactly \(k\) positive parts, so that \(P_0(0) = 1\), \(P_0(m) = 0\) for \(m \geq 1\), and \(P_k(m) = 0\) for \(k > m\). Let \(P(m) \coloneqq \sum_{k=0}^m P_k(m)\) be the number of partitions of \(m\). Then for \(n \geq k \geq 1\), \[ P_k(n) = P_k(n-k) + P_{k-1}(n-1), \] and for \(n \geq 1\), \[ P(n) = \sum_{k=1}^n P_k(n-k) + P(n-1). \]
Divide the partitions of \(n\) into \(k\) parts into two classes. Those whose parts are all at least \(2\) correspond bijectively to partitions of \(n-k\) into \(k\) parts, by subtracting \(1\) from each part; in the other direction, \([1,1,1,3] \mapsto [2,2,2,4]\). Those with a part equal to \(1\) correspond bijectively to partitions of \(n-1\) into \(k-1\) parts, by deleting one part equal to \(1\); in the other direction, \([1,1,2,5] \mapsto [1,1,2,5,1]\). This proves the first identity.
Summing it over \(1 \leq k \leq n\) gives \[ P(n) = \sum_{k=1}^n P_k(n-k) + \sum_{j=0}^{n-1} P_j(n-1) = \sum_{k=1}^n P_k(n-k) + P(n-1). \] Applying the same identity to \(P(n-1)\), \(P(n-2)\), and so on computes \(P(n)\) recursively: \[ \begin{aligned} P(n) &= \sum_{k=1}^n P_k(n-k) + P(n-1) \\ &= \sum_{k=1}^n P_k(n-k) + \sum_{k=1}^{n-1} P_k(n-1-k) + P(n-2) \\ &= \cdots \end{aligned} \]