Fact-checked by Grok 2 weeks ago

Symmetric group

The symmetric group S_n is the finite group consisting of all bijections from a finite set of n elements to itself, where the group operation is the composition of functions. These bijections, known as permutations, form a set of cardinality n!, reflecting the total number of ways to rearrange n distinct objects. For n \geq 3, S_n is non-abelian, meaning that the order of composition matters, and it is generated by the adjacent transpositions (i, i+1) for i = 1, \dots, n-1. A key subgroup of S_n is the A_n, which comprises all even permutations—those that can be expressed as an even number of transpositions—and serves as the kernel of the sign homomorphism from S_n to \mathbb{Z}/2\mathbb{Z}. This makes A_n a normal subgroup of index 2 in S_n for n \geq 2, and A_n is simple for n \geq 5, a property central to the . Symmetric groups are foundational in theory, with every finite group G embeddable as a subgroup of some S_{|G|} by , which realizes G via its action on itself by left multiplication. Beyond , symmetric groups underpin applications in through enumerative problems like counting permutations with restricted positions, in via their irreducible representations parametrized by partitions of n, and in physics and chemistry for modeling molecular symmetries and particle classifications. Their study also connects to broader symmetry principles, influencing fields from to .

Definition and Basic Properties

Definition

The symmetric group S_n on n letters, where n is a positive , is defined as the set of all bijections \sigma: \{1, 2, \dots, n\} \to \{1, 2, \dots, n\}, with the group operation given by of functions. This structure forms a group under , as verified by the standard group axioms of , associativity, , and inverses./01:_Chapters/1.03:_The_Symmetric_Groups) Permutations in S_n are commonly represented using two-line notation, which displays the elements in the top row and their images under \sigma in the bottom row, such as \begin{pmatrix} 1 & 2 & \cdots & n \\ \sigma(1) & \sigma(2) & \cdots & \sigma(n) \end{pmatrix}. $$/01:_Chapters/1.03:_The_Symmetric_Groups) An equivalent one-line notation omits the top row, listing only the images $ \sigma(1) \, \sigma(2) \, \cdots \, \sigma(n) $.[](https://planetmath.org/onelinenotationforpermutations) The concept of the symmetric group originated in the work of [Joseph-Louis Lagrange](/page/Joseph-Louis_Lagrange) in the late [18th century](/page/18th_century), particularly in his investigations of [permutations](/page/Permutation) of polynomial roots to understand solvability by radicals.[](https://www.math.univ-toulouse.fr/~bauval/Roth.pdf) For illustration, the symmetric group $ S_3 $ consists of the following six elements in one-line notation: - $ 1 \, 2 \, 3 $ ([the identity permutation](/page/Identity)), - $ 2 \, 1 \, 3 $, - $ 3 \, 2 \, 1 $, - $ 1 \, 3 \, 2 $, - $ 2 \, 3 \, 1 $, - $ 3 \, 1 \, 2 $./01:_Chapters/1.03:_The_Symmetric_Groups) ### Order and First Properties The symmetric group $ S_n $ on a set with $ n $ [elements](/page/Fifth_Element) consists of all bijections from the set to itself under [composition](/page/Composition), and its [order](/page/Order), or [cardinality](/page/Cardinality), is $ n! $. This follows from the fact that specifying a [permutation](/page/Permutation) requires choosing an [image](/page/Image) for each of the $ n $ [elements](/page/Fifth_Element) such that all [images](/page/Image) are distinct: there are $ n $ choices for the [image](/page/Image) of the first [element](/page/Element), $ n-1 $ for the second, and so on, down to 1 choice for the last, yielding the product $ n \times (n-1) \times \cdots \times 1 = n! $. Equivalently, the [order](/page/Order) satisfies the [recurrence relation](/page/Recurrence_relation) $ |S_n| = n \cdot |S_{n-1}| $ for $ n \geq 1 $, with base case $ |S_1| = 1 $ (or $ |S_0| = 1 $ for the [empty set](/page/Empty_set)), since the [image](/page/Image) of any distinguished [element](/page/Element) can be chosen in $ n $ ways, after which the remaining $ n-1 $ [elements](/page/Fifth_Element) can be permuted arbitrarily as in $ S_{n-1} $.[](https://mathworld.wolfram.com/SymmetricGroup.html)[](https://ncatlab.org/nlab/show/symmetric+group) For finite $ n $, $ S_n $ is thus a [finite group](/page/Finite_group) of [order](/page/Order) $ n! $. In contrast, the symmetric group $ S_\infty $ on a countably [infinite set](/page/Infinite_set), such as the natural numbers, is infinite, with cardinality equal to that of the [continuum](/page/Continuum), $ 2^{\aleph_0} $, as it bijects with the power set of the underlying set.[](https://ncatlab.org/nlab/show/symmetric+group)[](https://groupprops.subwiki.org/wiki/Symmetric_group) The group $ S_n $ is non-abelian for all $ n \geq 3 $. To verify this, consider the transpositions $ \sigma = (1\ 2) $ and $ \tau = (1\ 3) $ in $ S_n $. Their product is $ \sigma \tau = (1\ 2)(1\ 3) = (1\ 3\ 2) $, while $ \tau \sigma = (1\ 3)(1\ 2) = (1\ 2\ 3) $. Since $ \sigma \tau \neq \tau \sigma $, the group operation is non-commutative. For $ n = 1 $ and $ n = 2 $, $ S_n $ is abelian (isomorphic to the [trivial group](/page/Trivial_group) and $ \mathbb{Z}/2\mathbb{Z} $, respectively), but the non-abelian property holds universally for larger finite $ n $.[](https://math.libretexts.org/Courses/Mount_Royal_University/Abstract_Algebra_I/Chapter_3%3A_Permutation_Groups/3.1%3A_Symmetric_Groups) ## Operations and Group Structure ### Permutation Multiplication The multiplication of two permutations in the symmetric group $S_n$ is defined by their [composition](/page/Composition) as functions on the set $\{1, 2, \dots, n\}$. For permutations $\sigma, \tau \in S_n$, the product $\sigma \tau$ is the permutation given by $(\sigma \tau)(x) = \sigma(\tau(x))$ for all $x \in \{1, 2, \dots, n\}$./01:_Chapters/1.03:_The_Symmetric_Groups)[](https://math.mit.edu/~dav/symmetricgroup.pdf) This convention corresponds to applying the right permutation $\tau$ first, followed by the left permutation $\sigma$, reflecting the standard order of [function composition](/page/Function_composition) from right to left./01:_Chapters/1.03:_The_Symmetric_Groups) To compute the product $\sigma \tau$, evaluate the action on each element in the domain: start with the input $x$, apply $\tau$ to obtain $\tau(x)$, then apply $\sigma$ to that result to get $\sigma(\tau(x))$. This process yields the full mapping of $\sigma \tau$, which can then be expressed in cycle notation or two-line notation if desired. The resulting permutation is unique and belongs to $S_n$, ensuring the operation is well-defined within the group./01:_Chapters/1.03:_The_Symmetric_Groups) For example, consider the permutations $\sigma = (1\ 2\ 3)$ and $\tau = (1\ 2)$ in $S_3$. Compute $\sigma \tau$: - $(\sigma \tau)(1) = \sigma(\tau(1)) = \sigma(2) = 3$, - $(\sigma \tau)(2) = \sigma(\tau(2)) = \sigma(1) = 2$, - $(\sigma \tau)(3) = \sigma(\tau(3)) = \sigma(3) = 1$. The mapping is $1 \mapsto 3$, $2 \mapsto 2$, $3 \mapsto 1$, which corresponds to the transposition $(1\ 3)$./01:_Chapters/1.03:_The_Symmetric_Groups)[](https://groupprops.subwiki.org/wiki/Determination_of_multiplication_table_of_symmetric_group:S3) This multiplication operation is associative because permutations are bijections, and the composition of functions satisfies $(\rho (\sigma \tau)) = ((\rho \sigma) \tau)$ for any $\rho, \sigma, \tau \in S_n$, as the order of successive applications does not affect the final outcome when grouped differently.[](https://math.mit.edu/~dav/symmetricgroup.pdf) This property arises directly from the associativity of [function composition](/page/Function_composition) in [set theory](/page/Set_theory)./01:_Chapters/1.03:_The_Symmetric_Groups) ### Verification of Axioms The symmetric group $S_n$ on a [finite set](/page/Finite_set) with $n$ elements is the set of all [bijections](/page/Bijection) from the set to itself, equipped with the operation of [function composition](/page/Function_composition). To confirm that $S_n$ forms a group under this operation, the axioms of [closure](/page/Closure), associativity, identity, and inverses must be verified, with bijectivity playing a central role in each proof sketch.[](https://rksmvv.ac.in/wp-content/uploads/2021/04/David_S_Dummit_Richard_M_Foote_Abstract_Algeb_230928_225848.pdf) **Closure** holds because the [composition](/page/Composition) of two bijections is itself a bijection: if $\sigma, \tau \in S_n$, then for any $x$ in the set, $\sigma \circ \tau$ maps $x$ to $\sigma(\tau(x))$, and since both $\sigma$ and $\tau$ are [one-to-one](/page/One-to-one) and onto, their composition is also one-to-one (distinct inputs yield distinct outputs via injectivity of $\tau$ and $\sigma$) and onto (every output is hit by composing surjectivities). Thus, $\sigma \circ \tau \in S_n$.[](https://rksmvv.ac.in/wp-content/uploads/2021/04/David_S_Dummit_Richard_M_Foote_Abstract_Algeb_230928_225848.pdf)[](https://www.jmilne.org/math/CourseNotes/GT.pdf) **Associativity** is inherited from the associativity of [function composition](/page/Function_composition): for $\sigma, \tau, \rho \in S_n$, the equality $(\sigma \circ \tau) \circ \rho = \sigma \circ (\tau \circ \rho)$ follows because, for any $x$, both sides evaluate to $\sigma(\tau(\rho(x)))$, as [function application](/page/Function_application) associates regardless of bijectivity. This property ensures the operation is well-defined without relying on the specific bijectivity of elements in $S_n$, though all are bijections.[](https://rksmvv.ac.in/wp-content/uploads/2021/04/David_S_Dummit_Richard_M_Foote_Abstract_Algeb_230928_225848.pdf)[](https://www.jmilne.org/math/CourseNotes/GT.pdf) The **identity** element exists as the identity permutation $\iota$, defined by $\iota(x) = x$ for all $x$ in the set, which is a [bijection](/page/Bijection) (trivially [one-to-one](/page/One-to-one) and onto). It satisfies $\iota \circ \sigma = \sigma \circ \iota = \sigma$ for any $\sigma \in S_n$, since composing with $\iota$ leaves the input unchanged before or after applying $\sigma$. Uniqueness follows from the group axiom requirements, but here it stems from the fact that any other candidate would fail bijectivity or the composition property.[](https://rksmvv.ac.in/wp-content/uploads/2021/04/David_S_Dummit_Richard_M_Foote_Abstract_Algeb_230928_225848.pdf)[](https://resources.saylor.org/wwwresources/archived/site/wp-content/uploads/2011/04/Symmetric-group.pdf) **Inverses** exist for every element because each [bijection](/page/Bijection) $\sigma \in S_n$ has a [unique](/page/Unique) [inverse](/page/Inverse) [bijection](/page/Bijection) $\sigma^{-1}$ such that $\sigma \circ \sigma^{-1} = \sigma^{-1} \circ \sigma = \iota$. The [inverse](/page/Inverse) is constructed by ensuring it undoes $\sigma$'s mapping—since $\sigma$ is bijective, for every $y$, there is a [unique](/page/Unique) $x = \sigma^{-1}(y)$ with $\sigma(x) = y$, making $\sigma^{-1}$ [one-to-one](/page/One-to-one) (distinct $y$s map to distinct $x$s) and onto (every $x$ is hit). This guarantees the set is closed under inverses within $S_n$.[](https://rksmvv.ac.in/wp-content/uploads/2021/04/David_S_Dummit_Richard_M_Foote_Abstract_Algeb_230928_225848.pdf)[](https://www.jmilne.org/math/CourseNotes/GT.pdf) ### Identity and Inverses In the symmetric group $ S_n $, the identity element, denoted $ e $ or $ \mathrm{id} $, is the unique permutation that fixes every point in the set $ \{1, 2, \dots, n\} $, meaning $ e(i) = i $ for all $ i $.[](https://math.libretexts.org/Courses/Mount_Royal_University/Abstract_Algebra_I/Chapter_3%3A_Permutation_Groups/3.1%3A_Symmetric_Groups) In cycle notation, it is represented as the empty product or a product of $ n $ trivial 1-cycles, such as $ (1)(2)\dots(n) $.[](https://math.umd.edu/~immortal/MATH403/lecturenotes/ch5.pdf) This element serves as the neutral component under permutation composition, satisfying $ \sigma \circ e = e \circ \sigma = \sigma $ for any $ \sigma \in S_n $.[](https://feog.github.io/lecture7ws.pdf) Every element $ \sigma \in S_n $ possesses a unique inverse $ \sigma^{-1} $, which is the permutation defined by $ \sigma^{-1}(j) = i $ whenever $ \sigma(i) = j $, ensuring that composition yields the identity: $ \sigma \circ \sigma^{-1} = \sigma^{-1} \circ \sigma = e $.[](https://math.libretexts.org/Courses/Mount_Royal_University/Abstract_Algebra_I/Chapter_3%3A_Permutation_Groups/3.1%3A_Symmetric_Groups) To compute the inverse explicitly, one traces the action of $ \sigma $ in reverse: for each $ i $, identify the preimage under $ \sigma $ to map back to $ i $.[](https://math.umd.edu/~immortal/MATH403/lecturenotes/ch5.pdf) When $ \sigma $ is expressed in disjoint cycle notation, the inverse is obtained by reversing the order of elements within each cycle while preserving the cycle structure.[](https://math.libretexts.org/Courses/Mount_Royal_University/Abstract_Algebra_I/Chapter_3%3A_Permutation_Groups/3.1%3A_Symmetric_Groups) For example, consider $ \sigma = (1\ 2\ 3) $ in $ S_3 $, where $ \sigma(1) = 2 $, $ \sigma(2) = 3 $, and $ \sigma(3) = 1 $. The [inverse](/page/Inverse) $ \sigma^{-1} $ satisfies $ \sigma^{-1}(2) = 1 $, $ \sigma^{-1}(3) = 2 $, and $ \sigma^{-1}(1) = 3 $, corresponding to the [cycle](/page/Cycle) $ (1\ 3\ 2) $.[](https://math.libretexts.org/Courses/Mount_Royal_University/Abstract_Algebra_I/Chapter_3%3A_Permutation_Groups/3.1%3A_Symmetric_Groups) Verification via composition confirms this: (\sigma \circ \sigma^{-1})(1) = \sigma(\sigma^{-1}(1)) = \sigma(3) = 1, \quad (\sigma \circ \sigma^{-1})(2) = \sigma(1) = 2, \quad (\sigma \circ \sigma^{-1})(3) = \sigma(2) = 3, and similarly for the other order, yielding the [identity](/page/Identity) $ e $.[](https://math.umd.edu/~immortal/MATH403/lecturenotes/ch5.pdf) ## Elements and Their Properties ### Cycle Notation Cycle notation provides a compact and intuitive way to represent permutations in the symmetric group $S_n$, where elements are bijections from a [finite set](/page/Finite_set) $\{1, 2, \dots, n\}$ to itself. A [cycle](/page/Cycle) is a sequence of distinct [elements](/page/Fifth_Element) arranged in a circular [permutation](/page/Permutation), denoted by enclosing the elements in parentheses. Specifically, a $k$-[cycle](/page/Cycle) $(a_1 \, a_2 \, \dots \, a_k)$ is defined such that it maps $a_i$ to $a_{i+1}$ for $i = 1, \dots, k-1$, and $a_k$ to $a_1$, while leaving all other [elements](/page/Fifth_Element) fixed.[](https://math.libretexts.org/Bookshelves/Abstract_and_Geometric_Algebra/Abstract_Algebra%253A_Theory_and_Applications_%28Judson%29/05%253A_Permutation_Groups/5.01%253A_Definitions_and_Notation) This notation emphasizes the cyclic structure of the permutation on the specified [elements](/page/Fifth_Element), with the length $k$ indicating the number of [elements](/page/Fifth_Element) in the [cycle](/page/Cycle).[](https://math.libretexts.org/Courses/Mount_Royal_University/Abstract_Algebra_I/Chapter_3%253A_Permutation_Groups/3.1%253A_Symmetric_Groups) The [support](/page/Support) of a [cycle](/page/Cycle) $(a_1 \, a_2 \, \dots \, a_k)$ is the set $\{a_1, a_2, \dots, a_k\}$, consisting of the [elements](/page/Element) that are moved by the [permutation](/page/Permutation). Elements outside this support are fixed points, meaning they are mapped to themselves. For instance, in $S_3$, the [cycle](/page/Cycle) $(1 \, 2)$ has [support](/page/Support) $\{1, 2\}$ and fixes 3.[](https://math.libretexts.org/Bookshelves/Abstract_and_Geometric_Algebra/Abstract_Algebra%253A_Theory_and_Applications_%28Judson%29/05%253A_Permutation_Groups/5.01%253A_Definitions_and_Notation) The [cycle](/page/Cycle) length $k$ determines the [order](/page/Order) of the [cycle](/page/Cycle) as an [element](/page/Element) of the group, which is $k$, since applying the [cycle](/page/Cycle) $k$ times returns the [identity](/page/Identity).[](https://math.libretexts.org/Courses/Mount_Royal_University/Abstract_Algebra_I/Chapter_3%253A_Permutation_Groups/3.1%253A_Symmetric_Groups) Any permutation in $S_n$ can be expressed as a product of disjoint cycles, where the cycles have no elements in common. This decomposition is unique up to the ordering of the cycles and the starting point within each cycle. Disjoint cycles commute under multiplication, simplifying computations. The formal statement is that every $\sigma \in S_n$ decomposes as $\sigma = \tau_1 \tau_2 \dots \tau_m$, where the $\tau_i$ are disjoint [cycles](/page/Cycle) (including 1-cycles for fixed points, though often omitted).[](https://math.libretexts.org/Bookshelves/Abstract_and_Geometric_Algebra/Abstract_Algebra%253A_Theory_and_Applications_%28Judson%29/05%253A_Permutation_Groups/5.01%253A_Definitions_and_Notation)[](https://math.libretexts.org/Courses/Mount_Royal_University/Abstract_Algebra_I/Chapter_3%253A_Permutation_Groups/3.1%253A_Symmetric_Groups) For example, consider a permutation in $S_5$ that maps 1 to 3, 3 to 2, 2 to 1, 4 to 5, and 5 to 4, while fixing nothing else (though 5 elements total). This is written as $(1 \, 3 \, 2)(4 \, 5)$, a product of a [3-cycle](/page/3-2) and a 2-cycle with disjoint supports $\{1,2,3\}$ and $\{4,5\}$.[](https://math.libretexts.org/Bookshelves/Abstract_and_Geometric_Algebra/Abstract_Algebra%253A_Theory_and_Applications_%28Judson%29/05%253A_Permutation_Groups/5.01%253A_Definitions_and_Notation) ### Transpositions A transposition in the symmetric group $S_n$ is a permutation that interchanges two distinct elements $i$ and $j$ while fixing all other elements; in cycle notation, it is denoted by $(i\, j)$.[](https://kconrad.math.uconn.edu/blurbs/grouptheory/genset.pdf) Such a 2-cycle has order 2, since applying it twice returns the identity permutation.[](https://kconrad.math.uconn.edu/blurbs/grouptheory/genset.pdf) Transpositions form a natural generating set for $S_n$, meaning that the set of all transpositions $\{(i\, j) \mid 1 \leq i < j \leq n\}$ generates the entire group under multiplication.[](https://rksmvv.ac.in/wp-content/uploads/2021/04/David_S_Dummit_Richard_M_Foote_Abstract_Algeb_230928_225848.pdf) Every permutation in $S_n$ can be expressed as a product of transpositions, although this decomposition is not unique.[](https://rksmvv.ac.in/wp-content/uploads/2021/04/David_S_Dummit_Richard_M_Foote_Abstract_Algeb_230928_225848.pdf) For instance, the 3-cycle $(1\, 2\, 3)$ can be written as the product $(1\, 3)(1\, 2)$, which involves two transpositions. This non-uniqueness implies that the number of transpositions in such a product is not invariant, but the parity—whether even or odd—is well-defined for each permutation.[](https://rksmvv.ac.in/wp-content/uploads/2021/04/David_S_Dummit_Richard_M_Foote_Abstract_Algeb_230928_225848.pdf) The generating property of transpositions highlights their role as fundamental building blocks, allowing any permutation to be constructed through successive swaps. Even smaller subsets, such as the adjacent transpositions $(i\, i+1)$ for $i = 1$ to $n-1$, suffice to generate $S_n$.[](https://kconrad.math.uconn.edu/blurbs/grouptheory/genset.pdf) This structure underscores the relational nature of permutations as compositions of basic interchanges. ### Sign Homomorphism The sign homomorphism, denoted $\operatorname{sgn}: S_n \to \{\pm 1\}$, assigns to each permutation $\sigma \in S_n$ its sign, which is $+1$ if $\sigma$ is even and $-1$ if $\sigma$ is odd. This function is well-defined because the parity of a permutation, determined by the number of transpositions in its decomposition, is independent of the choice of decomposition.[](https://kconrad.math.uconn.edu/blurbs/grouptheory/sign.pdf) One equivalent definition is $\operatorname{sgn}(\sigma) = (-1)^k$, where $k$ is the number of even-length cycles in the cycle decomposition of $\sigma$ (including fixed points as 1-cycles).[](https://ocw.mit.edu/courses/res-18-011-algebra-i-student-notes-fall-2021/mit18_701f21_lect21.pdf) Alternatively, $\operatorname{sgn}(\sigma) = (-1)^i$, where $i$ is the number of inversions in $\sigma$, that is, the number of pairs $(a, b)$ with $a < b$ but $\sigma(a) > \sigma(b)$.[](https://www.statlect.com/matrix-algebra/sign-of-a-permutation) For basic elements, the sign of a transposition $(i\, j)$ is $-1$, since it is an even-length (2-cycle) permutation.[](https://kconrad.math.uconn.edu/blurbs/grouptheory/sign.pdf) More generally, the sign of a $k$-cycle is $\operatorname{sgn}((a_1\, a_2\, \dots\, a_k)) = (-1)^{k-1}$, which follows from expressing the cycle as a product of $k-1$ transpositions.[](https://dlmf.nist.gov/26.13) Thus, odd-length cycles are even permutations, while even-length cycles are odd permutations.[](https://kconrad.math.uconn.edu/blurbs/grouptheory/sign.pdf) For example, the 3-cycles $(1\, 2\, 3)$ and $(1\, 3\, 2)$ both have sign $+1$, as $3-1 = 2$ is even.[](https://kconrad.math.uconn.edu/blurbs/grouptheory/sign.pdf) The [sign](/page/Sign) is a [group homomorphism](/page/Group_homomorphism) because $\operatorname{sgn}(\sigma \tau) = \operatorname{sgn}(\sigma) \operatorname{sgn}(\tau)$ for all $\sigma, \tau \in S_n$, with the [multiplicative group](/page/Multiplicative_group) operation on $\{\pm 1\}$.[](https://www.math.ubc.ca/~carrell/Book2_Sn.pdf) This property holds since the [parity](/page/Parity) of the product of two permutations equals the product of their parities, as verified through the invariance of [sign](/page/Sign) under decomposition into transpositions or cycles.[](https://kconrad.math.uconn.edu/blurbs/grouptheory/sign.pdf) The [kernel](/page/Kernel) of $\operatorname{sgn}$ is the set of all even permutations, which forms the [alternating group](/page/Alternating_group) $A_n = \{\sigma \in S_n \mid \operatorname{sgn}(\sigma) = 1\}$.[](https://www.math.ubc.ca/~carrell/Book2_Sn.pdf) ### Derangements and Fixed Points In the symmetric group $S_n$, a fixed point of a permutation $\sigma$ is an element $x \in \{1, 2, \dots, n\}$ such that $\sigma(x) = x$.[](https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf) Fixed points represent elements that remain unchanged under the permutation, and the number of fixed points in a given $\sigma$ can range from 0 to $n$, influencing properties like cycle structure and the overall distribution of permutations.[](https://mathworld.wolfram.com/Derangement.html) A [derangement](/page/Derangement) is a [permutation](/page/Permutation) in $S_n$ with no fixed points, meaning $\sigma(x) \neq x$ for all $x$.[](https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf) The number of derangements of $n$ elements, denoted $ !n $ or $D(n)$, is given by the formula !n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}, which arises from the inclusion-exclusion principle applied to counting permutations avoiding fixed points.[](https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf) This exact count is approximately $n!/e$, where $e \approx 2.71828$ is the base of the natural logarithm, and the relative error tends to zero as $n$ increases.[](https://mathworld.wolfram.com/Derangement.html) Derangements model classical combinatorial problems, such as the hat check problem, where $n$ people randomly receive one another's hats, and the goal is to find the probability that no one receives their own hat; this probability equals $ !n / n! \approx 1/e \approx 0.3679$.[](https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf) The problem was first analyzed by Pierre Rémond de Montmort in 1713, who derived early forms of the derangement count in the context of probability and games of chance.[](https://mathworld.wolfram.com/Derangement.html) For example, in $S_3$, the derangements are the two 3-cycles $(1\ 2\ 3)$ and $(1\ 3\ 2)$, each mapping every element to a different position with no fixed points, out of the total 6 permutations.[](https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf) ## Conjugacy and Cycle Types ### Conjugacy Classes In group theory, two elements $\sigma$ and $\tau$ in the symmetric group $S_n$ are conjugate if there exists some $\gamma \in S_n$ such that $\tau = \gamma^{-1} \sigma \gamma$.[](https://planetmath.org/conjugacyclassesinthesymmetricgroupsn) A fundamental result states that two permutations in $S_n$ are conjugate if and only if they have the same cycle type, meaning they correspond to the same [partition](/page/Partition) of the integer $n$ when decomposed into disjoint cycles (up to ordering of the cycles and rotation within each cycle).[](https://maths.nuigalway.ie/~rquinlan/groups/section2-3.pdf) This classification implies that the conjugacy classes of $S_n$ are in one-to-one correspondence with the partitions of $n$, so the number of distinct conjugacy classes is given by $p(n)$, the partition function.[](https://planetmath.org/conjugacyclassesinthesymmetricgroupsn) The size of the centralizer $C_{S_n}(\sigma)$ of an element $\sigma$ with cycle type specified by $m_l$ cycles of length $l$ (for $l = 1, \dots, n$) is $|C_{S_n}(\sigma)| = \prod_{l=1}^n l^{m_l} m_l!$.[](https://ocw.mit.edu/courses/res-18-011-algebra-i-student-notes-fall-2021/mit18_701f21_lect21.pdf) Consequently, the size of the [conjugacy class](/page/Conjugacy_class) of $\sigma$ is $n! / |C_{S_n}(\sigma)|$, which provides a way to count the number of elements sharing that cycle type.[](https://maths.nuigalway.ie/~rquinlan/groups/section2-3.pdf) For example, in $S_4$, the partitions of 4 yield five conjugacy classes: the [identity](/page/Identity) (type $1^4$, size 1); transpositions (type $2,1^2$, size 6); double transpositions (type $2^2$, size 3); 3-cycles (type $3,1$, size 8); and 4-cycles (type $4$, size 6).[](https://ocw.mit.edu/courses/res-18-011-algebra-i-student-notes-fall-2021/mit18_701f21_lect21.pdf) The centralizer sizes are 24, 4, 8, 3, and 4, respectively, verifying the class equation $24 = 1 + 6 + 3 + 8 + 6$.[](https://maths.nuigalway.ie/~rquinlan/groups/section2-3.pdf) ### Cycle Index The cycle index of the symmetric group $ S_n $ is a multivariate [generating function](/page/Generating_function) that encodes the distribution of cycle types among its elements, providing a compact way to summarize [permutation](/page/Permutation) structures for [enumeration](/page/Enumeration) purposes. It is defined as Z(S_n; x_1, x_2, \dots, x_n) = \frac{1}{n!} \sum_{\sigma \in S_n} \prod_{i=1}^n x_i^{c_i(\sigma)}, where $ c_i(\sigma) $ is the number of [cycle](/page/Cycle)s of length $ i $ in the cycle decomposition of the [permutation](/page/Permutation) $ \sigma $. This polynomial was introduced by [George Pólya](/page/George_Pólya) in his foundational work on combinatorial [enumeration](/page/Enumeration).[](https://mathworld.wolfram.com/CycleIndex.html) An explicit formula for the cycle index can be obtained by grouping permutations according to their cycle types, which correspond to [integer](/page/Integer) partitions of $ n $. For a [partition](/page/Partition) $ \lambda \vdash n $ with $ m_i(\lambda) $ parts of size $ i $, the number of permutations of cycle type $ \lambda $ is $ \frac{n!}{\prod_{i=1}^n i^{m_i(\lambda)} m_i(\lambda)!} $. Thus, Z(S_n; x_1, \dots, x_n) = \sum_{\lambda \vdash n} \frac{1}{\prod_{i=1}^n i^{m_i(\lambda)} m_i(\lambda)!} \prod_{i=1}^n x_i^{m_i(\lambda)}. This [summation](/page/Summation) over partitions facilitates computational evaluation and theoretical analysis of symmetric group actions. For example, the cycle index of $ S_3 $ is Z(S_3; x_1, x_2, x_3) = \frac{1}{6} \left( x_1^3 + 3 x_1 x_2 + 2 x_3 \right), reflecting the one identity [permutation](/page/Permutation) with three 1-cycles, the three transpositions each with one 1-cycle and one 2-cycle, and the two 3-cycles.[](https://mathworld.wolfram.com/CycleIndex.html) In Pólya's enumeration theorem, the [cycle index](/page/Cycle_index) serves as the key tool for counting orbits under group actions, such as the number of distinct colorings of an $ n $-element set with $ c $ colors up to [permutation](/page/Permutation) symmetry, obtained by substituting $ x_i = c $ for all $ i $ to yield $ Z(S_n; c, c, \dots, c) $. This substitution generates the count of inequivalent colorings by averaging the fixed points of each [permutation](/page/Permutation). ## The Alternating Group ### Definition via Sign The [alternating group](/page/Alternating_group) $ A_n $ on $ n $ letters is defined as the [subgroup](/page/Subgroup) of the symmetric group $ S_n $ consisting of all even permutations, which is equivalently the [kernel](/page/Kernel) of the [sign](/page/Sign) [homomorphism](/page/Homomorphism) $ \sgn: S_n \to \{ \pm 1 \} $.[](http://www.math.utah.edu/~bertram/6320v2/6320Groups.pdf) As the [kernel](/page/Kernel) of a [group homomorphism](/page/Group_homomorphism), $ A_n $ is a [normal subgroup](/page/Normal_subgroup) of $ S_n $.[](http://www.math.utah.edu/~bertram/6320v2/6320Groups.pdf) For $ n \geq 2 $, $ A_n $ has index 2 in $ S_n $, so $ |A_n| = n!/2 $.[](http://www.math.utah.edu/~bertram/6320v2/6320Groups.pdf) For $ n \geq 3 $, $ A_n $ is generated by the 3-cycles; that is, every even [permutation](/page/Permutation) can be expressed as a product of 3-cycles.[](https://ecroot.math.gatech.edu/3cycle.pdf) This follows from the fact that any even permutation is a product of an even number of transpositions, and products of two transpositions can be rewritten as products of 3-cycles: if the transpositions share an element, such as $ (a\, b)(a\, c) = (a\, c\, b) $; if disjoint, such as $ (a\, b)(c\, d) = (a\, c\, d)(a\, b\, d) $.[](https://ecroot.math.gatech.edu/3cycle.pdf) For small $ n $, explicit structure illustrates this [definition](/page/Definition). The group $ A_3 $ consists of the [identity](/page/Identity) and the two 3-cycles $ (1\, 2\, 3) $ and $ (1\, 3\, 2) $, so $ A_3 = \langle (1\, 2\, 3) \rangle $ is cyclic of order 3.[](https://people.tamu.edu/~yvorobets/MATH415-2021A/Lect1-07web.pdf) Similarly, $ A_4 $ has order 12 and is generated by its 3-cycles, such as $ (1\, 2\, 3) $ and $ (1\, 2\, 4) $.[](https://people.tamu.edu/~yvorobets/MATH415-2021A/Lect1-07web.pdf) ### Index and Cosets The [alternating group](/page/Alternating_group) $ A_n $ is a [subgroup](/page/Subgroup) of the symmetric group $ S_n $ of [index](/page/Index) 2 for $ n \geq 2 $.[](https://faculty.etsu.edu/gardnerr/5410/Beamer-Proofs/Proofs-I-6.pdf) This [index](/page/Index) equals the order of the [quotient group](/page/Quotient_group) $ S_n / A_n $, which is [isomorphic](/page/Isomorphism) to the [cyclic group](/page/Cyclic_group) $ \mathbb{Z}/2\mathbb{Z} $.[](https://www.jmilne.org/math/CourseNotes/GT.pdf) The action of $ S_n $ on the set of left [cosets](/page/Coset) of $ A_n $ by left multiplication induces this isomorphism, where even permutations fix the coset $ A_n $ and odd permutations swap it with the other [coset](/page/Coset).[](https://www.jmilne.org/math/CourseNotes/GT.pdf) The two cosets partition $ S_n $ into even and odd permutations: the coset $ A_n $ contains all even permutations, while the coset $ (1\ 2) A_n $ (or any [transposition](/page/Transposition) times $ A_n $) contains all odd permutations.[](http://webhome.auburn.edu/~huanghu/math7310/1-6.pdf) Since $ A_n $ has index 2, it is [normal](/page/Normal) in $ S_n $, so left and right cosets coincide, and double cosets $ A_n g A_n $ reduce to the ordinary cosets without additional structure.[](https://faculty.etsu.edu/gardnerr/5410/Beamer-Proofs/Proofs-I-6.pdf) For example, in $ S_4 $, which has order 24, the [alternating group](/page/Alternating_group) $ A_4 $ has order 12 and consists of all even permutations; the odd permutations form the [coset](/page/Coset) of any [transposition](/page/Transposition) (such as $ (1\ 2) $) multiplied by elements of $ A_4 $.[](https://dspace.mit.edu/bitstream/handle/1721.1/45589/18-701Fall2003/NR/rdonlyres/Mathematics/18-701Fall2003/FAF4E8CC-1C03-44E8-859A-3EB1B71D7FD9/0/alternating03.pdf) This decomposition highlights the index-2 structure, with $ S_4 / A_4 \cong \mathbb{Z}/2\mathbb{Z} $.[](https://www.jmilne.org/math/CourseNotes/GT.pdf) ### Simple Groups for n ≥ 5 The [alternating group](/page/Alternating_group) $A_n$ is [simple](/page/Simple) for all $n \geq 5$, meaning it possesses no nontrivial proper [normal](/page/Normal) subgroups.[](https://kconrad.math.uconn.edu/blurbs/grouptheory/Ansimple.pdf) This theorem establishes $A_n$ as a fundamental building block in the [classification of finite simple groups](/page/Classification_of_finite_simple_groups), highlighting its role as an indecomposable non-abelian structure in group theory.[](https://www.math.uchicago.edu/~may/VIGRE/VIGRE2010/REUPapers/Shrestha.pdf) The result traces back to [Camille](/page/Camille) Jordan's work in the 1870s, where he demonstrated the simplicity of $A_n$ for $n \geq 5$ as part of his broader investigations into [permutation](/page/Permutation) groups.[](https://kconrad.math.uconn.edu/blurbs/grouptheory/Ansimple.pdf) Jordan's proof relied on analyzing the structure of even permutations and their [normal](/page/Normal) subgroups, predating the full [classification of finite simple groups](/page/Classification_of_finite_simple_groups) by nearly a century.[](https://kconrad.math.uconn.edu/blurbs/grouptheory/Ansimple.pdf) A standard outline of the proof begins with the fact that $A_n$ for $n \geq 3$ is generated by 3-cycles, the even permutations consisting of a single 3-cycle and fixed points elsewhere.[](https://faculty.etsu.edu/gardnerr/4127/notes/An-is-Simple.pdf) To show [simplicity](/page/Simplicity), consider any nontrivial [normal subgroup](/page/Normal_subgroup) $N$ of $A_n$. If $N$ contains a double transposition (a product of two disjoint [transposition](/page/Transposition)s, which is even), conjugation by elements of $A_n$ yields a 3-cycle in $N$ for $n \geq 5$, as there is sufficient room to adjust the supports.[](https://kconrad.math.uconn.edu/blurbs/grouptheory/Ansimple.pdf) Once $N$ contains one 3-cycle, the conjugation action of $A_n$ on itself ensures $N$ contains all 3-cycles, since any two 3-cycles are conjugate in $A_n$ for $n \geq 5$.[](https://www.math.brown.edu/dabramov/MA/f1516/251/AnSimple_PresentationNotes.pdf) Thus, $N$ contains all generators of $A_n$, implying $N = A_n$. If $N$ initially contains a 3-cycle, the same conjugation argument applies directly. This exhausts the possibilities, confirming no proper nontrivial normal subgroups exist.[](https://kconrad.math.uconn.edu/blurbs/grouptheory/Ansimple.pdf) As a consequence, $A_5$ is the smallest non-abelian [simple group](/page/Simple_group), with order $|A_5| = [60](/page/60)$.[](https://www.math.uchicago.edu/~may/VIGRE/VIGRE2010/REUPapers/Shrestha.pdf) No non-abelian [simple group](/page/Simple_group) of order less than [60](/page/60) exists, underscoring $A_5$'s minimal role among infinite families of [simple](/page/Simple) groups.[](https://www.math.uchicago.edu/~may/VIGRE/VIGRE2010/REUPapers/Shrestha.pdf) For $A_5$ specifically, simplicity implies the absence of [normal](/page/Normal) subgroups of orders 10, 12, 15, 20, or 30, as these would divide [60](/page/60) and contradict the [theorem](/page/Theorem); proofs rule them out by showing any such [subgroup](/page/Subgroup) either fails to be [normal](/page/Normal) or leads to a contradiction with [Sylow theorems](/page/Sylow_theorems) or conjugacy classes.[](https://math.stackexchange.com/questions/2995244/how-do-i-prove-that-any-subgroup-of-a-5-has-order-at-most-12) ## Small Symmetric Groups ### Symmetric Groups of Low Degree The symmetric group $ S_1 $ is the trivial group, consisting solely of the identity permutation, and has order $ 1! = 1 $.[](https://mathworld.wolfram.com/SymmetricGroup.html) The symmetric group $ S_2 $ is isomorphic to the cyclic group $ \mathbb{Z}/2\mathbb{Z} $ and is generated by the transposition $ (1\ 2) $; its elements are the identity and this transposition, yielding order $ 2! = 2 $.[](https://mathworld.wolfram.com/SymmetricGroup.html) The Cayley table for $ S_2 $, with elements labeled as $ e $ (identity) and $ \sigma = (1\ 2) $, is as follows: | $ \cdot $ | $ e $ | $ \sigma $ | |-------------|---------|--------------| | $ e $ | $ e $ | $ \sigma $ | | $ \sigma $| $ \sigma $ | $ e $ | The symmetric group $ S_3 $ has order $ 3! = 6 $ and consists of the identity, the three transpositions $ (1\ 2) $, $ (1\ 3) $, $ (2\ 3) $, and the two 3-cycles $ (1\ 2\ 3) $, $ (1\ 3\ 2) $, where elements are expressed in cycle notation.[](https://groupprops.subwiki.org/wiki/Symmetric_group:S3)[](https://mathworld.wolfram.com/SymmetricGroup.html) It is isomorphic to the [dihedral group](/page/Dihedral_group) $ D_3 $, which describes the symmetries of an [equilateral triangle](/page/Equilateral_triangle). The [Cayley table](/page/Cayley_table) for $ S_3 $, using cycle notation with left multiplication, is: | $ \cdot $ | $ () $ | $ (1\ 2) $ | $ (2\ 3) $ | $ (1\ 3) $ | $ (1\ 2\ 3) $ | $ (1\ 3\ 2) $ | |---------------|------------|--------------|--------------|--------------|-----------------|-----------------| | $ () $ | $ () $ | $ (1\ 2) $ | $ (2\ 3) $ | $ (1\ 3) $ | $ (1\ 2\ 3) $ | $ (1\ 3\ 2) $ | | $ (1\ 2) $ | $ (1\ 2) $ | $ () $ | $ (1\ 2\ 3) $ | $ (1\ 3\ 2) $ | $ (2\ 3) $ | $ (1\ 3) $ | | $ (2\ 3) $ | $ (2\ 3) $ | $ (1\ 3\ 2) $ | $ () $ | $ (1\ 2\ 3) $ | $ (1\ 3) $ | $ (1\ 2) $ | | $ (1\ 3) $ | $ (1\ 3) $ | $ (1\ 2\ 3) $ | $ (1\ 3\ 2) $ | $ () $ | $ (1\ 2) $ | $ (2\ 3) $ | | $ (1\ 2\ 3) $| $ (1\ 2\ 3) $ | $ (1\ 3) $ | $ (1\ 2) $ | $ (2\ 3) $ | $ (1\ 3\ 2) $ | $ () $ | | $ (1\ 3\ 2) $| $ (1\ 3\ 2) $ | $ (2\ 3) $ | $ (1\ 3) $ | $ (1\ 2) $ | $ () $ | $ (1\ 2\ 3) $ |[](https://groupprops.subwiki.org/wiki/Determination_of_multiplication_table_of_symmetric_group:S3) The symmetric group $ S_4 $ has order $ 4! = 24 $ and includes, as a [normal subgroup](/page/Normal_subgroup), the [Klein four-group](/page/Klein_four-group) $ V_4 $, which comprises the [identity](/page/Identity) and the three double transpositions $ (1\ 2)(3\ 4) $, $ (1\ 3)(2\ 4) $, $ (1\ 4)(2\ 3) $.[](https://groupprops.subwiki.org/wiki/Normal_Klein_four-subgroup_of_symmetric_group:S4)[](https://mathworld.wolfram.com/SymmetricGroup.html) ### Embeddings and Maps The symmetric group $S_n$ embeds naturally as a [subgroup](/page/Subgroup) of $S_{n+1}$ via the injective [homomorphism](/page/Homomorphism) that maps each [permutation](/page/Permutation) $\sigma \in S_n$ to the permutation in $S_{n+1}$ obtained by letting $\sigma$ act on $\{1, \dots, n\}$ and fixing the point $n+1$.[](https://www.math.ubc.ca/~carrell/Book2_Sn.pdf) This embedding preserves the group operation, as composition of such extended permutations corresponds to composition in $S_n$. Iterating this construction yields [embeddings](/page/Embedding) $S_m \hookrightarrow S_n$ for any $m < n$, where permutations in $S_m$ fix the points $\{m+1, \dots, n\}$.[](https://www.math.ubc.ca/~carrell/Book2_Sn.pdf) This inductive embedding allows the symmetric groups to be built sequentially: starting from $S_1$, which is trivial, one extends the action on the initial set to larger finite sets by fixing additional points, yielding a chain of subgroups $S_1 \subset S_2 \subset \cdots \subset S_n \subset \cdots$.[](https://www.math.ubc.ca/~carrell/Book2_Sn.pdf) For a concrete example, $S_3$ embeds into $S_4$ as the subgroup of permutations fixing 4; under this embedding, the transposition $(1\ 2) \in S_3$ maps to $(1\ 2)$ in $S_4$, and the 3-cycle $(1\ 2\ 3)$ maps similarly, preserving the structure of $S_3$.[](https://www.math.ubc.ca/~carrell/Book2_Sn.pdf) Cayley's theorem provides a broader embedding result: every finite group $G$ is isomorphic to a subgroup of the symmetric group $S_{|G|}$, via the regular action where $G$ permutes its own elements by left multiplication.[](https://mathweb.ucsd.edu/~asalehig/math200a-22-f-lectures.pdf) This realizes any group as a permutation group, though the details of such realizations for symmetric groups themselves are addressed elsewhere. ## Presentations ### Generating Sets The symmetric group $ S_n $ is generated by the set of all transpositions $ (i\, j) $ for $ 1 \leq i < j \leq n $.[](https://people.tamu.edu/~yvorobets/MATH415-2021A/Lect1-07web.pdf) More precisely, a subset $ T $ of transpositions generates $ S_n $ if and only if the graph with vertex set $ \{1, \dots, n\} $ and edge set $ T $ is connected; in this case, the subgroup generated by $ T $ acts transitively on the set and equals $ S_n $.[](https://arxiv.org/pdf/math/0405185) The minimal size of such a generating set of transpositions is $ n-1 $, achieved precisely when the graph is a tree.[](https://arxiv.org/pdf/math/0405185) A canonical example of a minimal generating set of transpositions is the set of adjacent transpositions $ s_i = (i\, i+1) $ for $ i = 1, \dots, n-1 $; these generate $ S_n $ because any transposition can be expressed as an odd-length product of adjacent transpositions, and the associated path graph is connected.[](https://people.tamu.edu/~yvorobets/MATH415-2021A/Lect1-07web.pdf)[](https://planetmath.org/symmetricgroupisgeneratedbyadjacenttranspositions) For $ n=4 $, the adjacent transpositions $ (1\, 2) $, $ (2\, 3) $, and $ (3\, 4) $ thus form a minimal generating set.[](https://people.tamu.edu/~yvorobets/MATH415-2021A/Lect1-07web.pdf) Although $ n-1 $ is the minimal size for generating sets consisting solely of transpositions, the overall minimal number of generators for $ S_n $ (with $ n \geq 3 $) is 2.[](https://people.tamu.edu/~yvorobets/MATH415-2021A/Lect1-07web.pdf) One such 2-generated presentation uses the transposition $ (1\, 2) $ and the $ n $-cycle $ (1\, 2\, \dots\, n) $; powers of the cycle conjugate the transposition to yield all adjacent transpositions, which in turn generate $ S_n $.[](https://people.tamu.edu/~yvorobets/MATH415-2021A/Lect1-07web.pdf) The adjacent transpositions also arise in the bubble sort algorithm, where repeated swaps along them suffice to sort any input permutation into the identity.[](https://planetmath.org/symmetricgroupisgeneratedbyadjacenttranspositions) ### Relations and Presentations The symmetric group $ S_n $ has a standard presentation in terms of the adjacent transpositions $ s_i = (i\, i+1) $ for $ i = 1, \dots, n-1 $, given by \langle s_1, \dots, s_{n-1} \mid s_i^2 = 1,\ (s_i s_{i+1})^3 = 1,\ (s_i s_j)^2 = 1 \ \text{for} \ |i-j| \geq 2 \rangle. This presentation defines $ S_n $ abstractly as the group generated by these involutions subject to the specified relations, with the natural map from this group to $ S_n $ being an isomorphism, as verified by showing that the relations hold in $ S_n $ and that the presentation captures all elements via word reductions corresponding to reduced decompositions.[](https://nreadin.math.ncsu.edu/papers/MSRI4b.pdf)[](https://core.ac.uk/download/pdf/82644421.pdf) This presentation was first established by E. H. Moore in his work on abstract groups isomorphic to substitution groups.[](https://londmathsoc.onlinelibrary.wiley.com/doi/10.1112/plms/s1-28.1.357) It is known as the Coxeter presentation, identifying $ S_n $ as the finite Coxeter group of type $ A_{n-1} $, where the braid relations $ (s_i s_{i+1})^3 = 1 $ and commuting relations $ (s_i s_j)^2 = 1 $ for non-adjacent generators reflect the structure of the associated Dynkin diagram, a linear chain of $ n-1 $ nodes.[](https://sites.math.washington.edu/~billey/classes/reflection.groups/references/Humphreys.ReflectionGroupsAndCoxeterGroups.pdf) The Coxeter presentation connects to broader algebraic structures: it is the quotient of the Artin group of type $ A_{n-1} $ (the braid group on $ n $ strands) by the relations $ s_i^2 = 1 $, where the Artin presentation replaces quadratic relations with braid equalities of length 3 for adjacent generators.[](https://nreadin.math.ncsu.edu/papers/MSRI4b.pdf) Similarly, it underlies the Iwahori-Hecke algebra of type $ A_{n-1} $, a $ q $-deformation where the quadratic relations become $ (T_i + 1)(T_i - q) = 0 $ for generators $ T_i $ corresponding to $ s_i $, generalizing representations of $ S_n $ to quantum settings.[](https://www.math.auckland.ac.nz/~obrien/research/an-sn-present.pdf) For $ n=3 $, the presentation simplifies to $ \langle a, b \mid a^2 = b^2 = 1,\ (ab)^3 = 1 \rangle $, where $ a = (1\,2) $ and $ b = (2\,3) $, yielding the dihedral group of order 6 as expected for $ S_3 $.[](https://nreadin.math.ncsu.edu/papers/MSRI4b.pdf) ## Subgroups ### Normal Subgroups The alternating group $A_n$ is a normal subgroup of the symmetric group $S_n$ for all $n \geq 2$, as it is the kernel of the sign homomorphism from $S_n$ to $\{ \pm 1 \}$, or equivalently, because subgroups of index 2 are always normal.[](https://kconrad.math.uconn.edu/blurbs/grouptheory/Ansimple.pdf) The trivial subgroup $\{e\}$ and $S_n$ itself are also normal in $S_n$ for every $n$. For $n \neq 4, 6$, these are the only normal subgroups of $S_n$. For $n=4$, there is an additional normal subgroup, the Klein four-group $V_4 = \{ e, (1\,2)(3\,4), (1\,3)(2\,4), (1\,4)(2\,3) \}$, which consists of the identity and the three double transpositions and is normal because it is the kernel of the quotient map $S_4 \to S_3$.[](https://www.math.lsu.edu/~adkins/m7200/A_W_chap1.pdf) For $n=6$, despite $S_6$ possessing nontrivial outer automorphisms (unlike $S_n$ for other $n$), the normal subgroups remain only $\{e\}$, $A_6$, and $S_6$.[](https://groupprops.subwiki.org/wiki/Subgroup_structure_of_symmetric_group:S6) To classify normal subgroups more generally, note that any normal subgroup $N$ of $S_n$ must be invariant under conjugation, hence a union of conjugacy classes of $S_n$, where conjugacy classes are partitioned by cycle type.[](https://www.math.washington.edu/~smith/Teaching/504/gps.pdf) For $n \geq 5$, any proper nontrivial normal subgroup must contain $A_n$ (as the unique minimal nontrivial normal subgroup), yielding the stated classification.[](https://kconrad.math.uconn.edu/blurbs/grouptheory/Ansimple.pdf) The exceptional cases for $n=4$ and $n=6$ arise from explicit enumeration of unions of conjugacy classes that form subgroups closed under conjugation.[](https://planetmath.org/normalsubgroupsofthesymmetricgroups) ### Maximal Subgroups The maximal subgroups of the symmetric group $S_n$ (for $n \geq 2$) are classified into three types based on their action on the natural set $\Omega = \{1, 2, \dots, n\}$: intransitive, imprimitive, and primitive.[](https://link.springer.com/book/10.1007/978-1-4612-0731-3) This classification arises from the structure of permutation groups and ensures that no larger proper subgroup contains them.[](https://ensaios.sbm.org.br/wp-content/uploads/sites/14/2021/08/em_36_garonzi.pdf) Intransitive maximal subgroups preserve a nonempty proper subset of $\Omega$ as a union of orbits, specifically the stabilizers of subsets of size $k$ where $1 \leq k < n/2$. These are isomorphic to $S_k \times S_{n-k}$ and have index $\binom{n}{k}$.[](https://link.springer.com/book/10.1007/978-1-4612-0731-3) The case $k=1$ gives the point stabilizer, isomorphic to $S_{n-1}$ with index $n$, which is maximal.[](https://link.springer.com/book/10.1007/978-1-4612-0731-3) When $n$ is even and $k = n/2 > 1$, $S_{n/2} \times S_{n/2}$ is not maximal, as it is properly contained in the larger imprimitive subgroup $S_2 \wr S_{n/2}$.[](https://ensaios.sbm.org.br/wp-content/uploads/sites/14/2021/08/em_36_garonzi.pdf) Imprimitive maximal subgroups preserve a nontrivial [partition](/page/Partition) of $\Omega$ into $k$ blocks of equal size $m$, where $n = km$ with $k, m \geq 2$. These are isomorphic to the [wreath product](/page/Wreath_product) $S_m \wr S_k$ in its imprimitive action, with index $\binom{n}{m, m, \dots, m} = n! / (m!)^k / k!$.[](https://link.springer.com/book/10.1007/978-1-4612-0731-3) For example, when $m=2$ and $k = n/2$, this yields the hyperoctahedral group, which contains the intransitive subgroup $S_{n/2} \times S_{n/2}$.[](https://ensaios.sbm.org.br/wp-content/uploads/sites/14/2021/08/em_36_garonzi.pdf) Primitive maximal subgroups act transitively on $\Omega$ without nontrivial blocks of imprimitivity. Their [classification](/page/Classification) in $S_n$ relies on a simplified version of the O'Nan–Scott theorem, which categorizes [primitive](/page/Primitive) permutation groups into types such as affine, almost simple, and products, but excludes the normal subgroup $A_n$ (for $n \neq 6$) covered elsewhere.[](https://doi.org/10.1017/S1446788700029079) Non-normal [primitive](/page/Primitive) maximals occur for specific $n$, such as when $n = p^d$ for prime $p$, including affine groups like $\mathrm{AGL}(d, p)$.[](https://link.springer.com/book/10.1007/978-1-4612-0731-3) For $S_5$, the non-normal maximal subgroups include the point [stabilizer](/page/Stabilizer) $S_4$ (index 5), the intransitive $S_3 \times S_2$ (index 10), and the primitive normalizer of a Sylow 5-subgroup, isomorphic to $C_5 \rtimes C_4$ of order 20 ([index](/page/Index) 6).[](https://ensaios.sbm.org.br/wp-content/uploads/sites/14/2021/08/em_36_garonzi.pdf) No imprimitive maximals exist in $S_5$, as 5 is prime and has no suitable block sizes.[](https://link.springer.com/book/10.1007/978-1-4612-0731-3) ### Sylow Subgroups The order of a Sylow $p$-subgroup of the symmetric group $S_n$, for a prime $p$, is $p^k$, where $k = \sum_{m=1}^{\infty} \lfloor n / p^m \rfloor$ is the exponent of $p$ in the prime factorization of $n!$. This $k$ counts the total number of $p$-cycles needed to generate the $p$-power part of $n!$. The structure of a Sylow $p$-subgroup $P$ of $S_n$ is determined by the base-$p$ expansion of $n = \sum_{i=0}^k a_i p^i$ with $0 \leq a_i < p$. Specifically, $P$ is isomorphic to the direct product $\prod_{i=0}^k Q_i$, where $Q_i \cong \left( P_{p^i} \right)^{a_i}$ and $P_{p^i}$ is the Sylow $p$-subgroup of $S_{p^i}$, acting on $a_i$ disjoint copies of a set of $p^i$ elements. Here, $P_{p^i}$ itself is the iterated (imprimitive) wreath product of $i+1$ copies of the cyclic group $C_p$ of order $p$, with order $p^{(p^i - 1)/(p-1)}$. This construction embeds $P$ into $S_n$ by partitioning the $n$ points into $a_i$ blocks of size $p^i$ for each $i$, with $P$ acting separately on each collection of blocks while fixing the partition. Sylow $p$-subgroups are thus special cases contained within Young subgroups corresponding to partitions derived from this base-$p$ expansion. The number $n_p$ of Sylow $p$-subgroups of $S_n$ satisfies $n_p \equiv 1 \pmod{p}$ and equals the index $[S_n : N_{S_n}(P)] = n! / |N_{S_n}(P)|$, where $N_{S_n}(P)$ is the normalizer of $P$ in $S_n$. This normalizer is isomorphic to $\prod_{i=0}^k \left( P_{p^i}^{a_i} \rtimes [S_{a_i}](/page/Symmetric_group) \right)$, acting by permuting the $a_i$ blocks of size $p^i$ via $S_{a_i}$ (whose order $a_i!$ is coprime to $p$) while $P_{p^i}^{a_i}$ acts internally on the blocks. Thus, $|N_{S_n}(P)| = \left( \prod_{i=0}^k |P_{p^i}|^{a_i} \cdot a_i! \right)$, yielding $n_p = n! / \prod_{i=0}^k \left( |P_{p^i}|^{a_i} \cdot a_i! \right)$. This formula arises from counting the ways to choose the block partitions stabilized by the normalizer. For example, in $S_6$ with $p=2$, we have $6 = 0 \cdot 2^0 + 1 \cdot 2^1 + 1 \cdot 2^2$, so $k=2$ and $P \cong C_2 \times [D_8](/page/Dihedral_group)$, where $D_8$ is the dihedral group of order &#36;8$ (the Sylow &#36;2$-subgroup of $S_4$). The normalizer has order $16 \cdot 1! \cdot 1! = 16$, so $n_2 = 720 / 16 = 45 \equiv 1 \pmod{2}$. In $S_7$ with $p=3$, we have $7 = 1 \cdot 3^0 + 2 \cdot 3^1$, so $k=2$ and $P \cong [C_3](/page/Cyclic_group) \times [C_3](/page/Cyclic_group)$ (since the Sylow &#36;3$-subgroup of $S_3$ is $C_3$). The normalizer has order $9 \cdot 1! \cdot 2! = 18$, so $n_3 = 5040 / 18 = 280 \equiv 1 \pmod{3}$. ### Transitive Subgroups A transitive subgroup $ H $ of the symmetric group $ S_n $ is a subgroup that acts transitively on the set $\{1, 2, \dots, n\}$, meaning that for any two points $ i, j \in \{1, 2, \dots, n\} $, there exists an element $ h \in H $ such that $ h(i) = j $.[](https://link.springer.com/book/10.1007/978-1-4612-0731-3) This condition implies that $ H $ has a single orbit under its action, and every transitive permutation group of degree $ n $ is isomorphic to a transitive subgroup of $ S_n $.[](https://link.springer.com/book/10.1007/978-1-4612-0731-3) The full symmetric group $ S_n $ and the alternating group $ A_n $ (for $ n \geq 3 $) are prominent examples of transitive subgroups, as they permute all points freely.[](https://doi.org/10.1017/CBO9780511623675) Among transitive subgroups, a key distinction is between primitive and imprimitive actions. A transitive subgroup $ H $ is primitive if it preserves no nontrivial partition (or block system) of $\{1, 2, \dots, n\}$, where a [block](/page/Block) is a subset $ B $ with $ |B| > 1 $ and $ B \neq \{1, 2, \dots, n\} $ such that for every $ h \in H $, either $ h(B) = B $ or $ h(B) \cap B = \emptyset $.[](https://link.springer.com/book/10.1007/978-1-4612-0731-3) In contrast, an imprimitive transitive subgroup preserves at least one nontrivial block system. Many maximal transitive subgroups of $ S_n $ are primitive, as maximality often precludes nontrivial blocks.[](https://doi.org/10.1017/CBO9780511623675) For instance, the [dihedral group](/page/Dihedral_group) $ D_n $ of order $ 2n $, which consists of the symmetries of a regular $ n $-gon (rotations and reflections), acts transitively but imprimitively on the $ n $ vertices for $ n \geq 4 $.[](https://link.springer.com/book/10.1007/978-1-4612-0731-3) The classification of transitive subgroups up to conjugacy in $ S_n $ is well-understood computationally for small $ n $, with the number of distinct classes increasing rapidly: 1 for $ n=2 $, 2 for $ n=3 $, 5 for $ n=4 $, 5 for $ n=5 $, and 16 for $ n=6 $.[](https://people.maths.bris.ac.uk/~matyd/GroupNames/T31.html) Examples for small degrees include the affine [general linear group](/page/General_linear_group) $ \mathrm{AGL}(1,p) $ of [order](/page/Order) $ p(p-1) $ for prime $ p $, which acts primitively and transitively on $ p $ points as the group of affine transformations over the [finite field](/page/Finite_field) $ \mathbb{F}_p $.[](https://doi.org/10.1017/CBO9780511623675) Primitive transitive subgroups in general are classified via the O'Nan–Scott theorem, which reduces them to types involving almost simple groups, affine groups, or products related to simple groups, though complete listings for larger $ n $ rely on computational databases.[](https://webspace.maths.qmul.ac.uk/l.h.soicher/designtheory.org/library/encyc/topics/primitive.pdf) ### Young Subgroups In the symmetric group $ S_n $, a Young subgroup associated to a partition $ \lambda = (\lambda_1, \lambda_2, \dots, \lambda_k) $ of the [integer](/page/Integer) $ n $ (with $ \lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_k \geq 1 $ and $ \sum \lambda_i = n $) is the [subgroup](/page/Subgroup) $ S_\lambda = S_{\lambda_1} \times S_{\lambda_2} \times \cdots \times S_{\lambda_k} $, where each symmetric group $ S_{\lambda_i} $ acts faithfully on a disjoint block of $ \lambda_i $ elements from the underlying set $ \{1, 2, \dots, n\} $. This [embedding](/page/Embedding) ensures that $ S_\lambda $ stabilizes the set [partition](/page/Partition) of $ \{1, 2, \dots, n\} $ into $ k $ blocks of sizes $ \lambda_1, \dots, \lambda_k $, making it the [stabilizer](/page/Stabilizer) of that [partition](/page/Partition) under the natural [action](/page/Action) of $ S_n $. The [order](/page/Order) of $ S_\lambda $ is $ \prod_{i=1}^k \lambda_i! $. The standard embedding of $ S_\lambda $ in $ S_n $ places the blocks as consecutive initial segments of $ \{1, 2, \dots, n\} $: the first block is $ \{1, \dots, \lambda_1\} $, the second is $ \{\lambda_1 + 1, \dots, \lambda_1 + \lambda_2\} $, and so on.[](https://web.math.princeton.edu/~charchan/RepresentationTheorySymmetricGroupsNotes.pdf) A prominent example is the standard Young subgroup of type $ (k, n-k) $, denoted $ S_k \times S_{n-k} $, which stabilizes an arbitrary $ k $-element [subset](/page/Subset) of $ \{1, 2, \dots, n\} $ (up to conjugacy). For instance, in $ S_4 $, the Young subgroup $ S_{(2,2)} $ is isomorphic to $ S_2 \times S_2 $, has order $ (2!)^2 = 4 $, and acts by permuting elements within two disjoint 2-element blocks, such as $ \{1,2\} $ and $ \{3,4\} $. Young subgroups are central to the representation theory of symmetric groups, serving as the base for induction procedures that construct key modules. Specifically, the permutation representation induced from the trivial representation of $ S_\lambda $ to $ S_n $ yields the permutation module $ M^\lambda $, a free module over the group algebra with basis corresponding to cosets $ S_n / S_\lambda $; its composition series includes the Specht module $ S^\lambda $ as a key factor, which affords an irreducible representation of $ S_n $ labeled by $ \lambda $. The decomposition of $ M^\lambda $ into irreducibles is governed by Kostka numbers, counting semistandard Young tableaux of shape $ \lambda $ and content given by another partition. All Young subgroups of $ S_n $ corresponding to the same [partition](/page/Partition) $ \lambda $ (up to reordering of parts) are conjugate within $ S_n $, as conjugation by an element of $ S_n $ permutes the blocks while preserving their sizes. The standard Young subgroups $ S_k \times S_{n-k} $ (for $ 1 \leq k \leq \lfloor n/2 \rfloor $) are precisely the maximal intransitive subgroups of $ S_n $. ### Cyclic Subgroups In the symmetric group $S_n$, cyclic [subgroups](/page/Subgroup) are generated by single elements, which are [permutations](/page/Permutation). Every [permutation](/page/Permutation) $\sigma \in S_n$ decomposes into a product of disjoint [cycles](/page/Cycle), and the order of $\sigma$—and thus the order of the cyclic subgroup $\langle \sigma \rangle$—is the [least common multiple](/page/Least_common_multiple) of the lengths of these [cycles](/page/Cycle). This follows because powers of $\sigma$ act independently on each [cycle](/page/Cycle), and the smallest positive [integer](/page/Integer) $k$ such that $\sigma^k$ is the identity [permutation](/page/Permutation) is the LCM of the cycle lengths. Maximal cyclic subgroups in $S_n$ are those generated by elements of maximal order, denoted $g(n)$, which is Landau's function giving the largest possible LCM of the lengths in any [partition](/page/Partition) of $n$.[](https://arxiv.org/abs/1312.2569) To achieve this maximum, the cycle lengths are chosen such that their prime factors are distributed to maximize the LCM, often by selecting lengths that are pairwise coprime and sum to $n$ (or as close as possible, with fixed points if needed).[](https://arxiv.org/abs/1312.2569) For instance, in $S_6$, $g(6) = 6$, attained by a 6-[cycle](/page/Cycle) like $(1\,2\,3\,4\,5\,6)$ or a product of disjoint cycles of lengths 3 and 2, such as $(1\,2\,3)(4\,5)$, where the lengths are coprime.[](https://oeis.org/A000793) The number of distinct cyclic subgroups in $S_n$ can be determined by considering the conjugacy classes corresponding to cycle types and using the Euler totient function $\phi(m)$. Specifically, for each possible order $m$, the number of cyclic subgroups of order $m$ is the number of elements of order $m$ divided by $\phi(m)$, since each such subgroup has exactly $\phi(m)$ generators.[](https://mathoverflow.net/questions/112117/cyclic-subgroups-of-the-symmetric-group) The total count sums this over all possible $m$ that arise as LCMs of partitions of integers up to $n$.[](https://mathoverflow.net/questions/112117/cyclic-subgroups-of-the-symmetric-group) As an example in $S_6$, the subgroup $\langle (1\,2\,3)(4\,5\,6) \rangle$ is cyclic of order 3, since the cycle lengths are both 3 and $\operatorname{lcm}(3,3) = 3$. In contrast, a maximal cyclic subgroup of order 6 is $\langle (1\,2\,3)(4\,5) \rangle$, with $\operatorname{lcm}(3,2) = 6$.[](https://oeis.org/A000793) ## Automorphisms and Outer Automorphisms ### Inner Automorphisms The inner automorphisms of the symmetric group $S_n$ are the automorphisms induced by conjugation by elements of $S_n$. Specifically, for each $\gamma \in S_n$, the map $\phi_\gamma: S_n \to S_n$ defined by $\phi_\gamma(\sigma) = \gamma^{-1} \sigma \gamma$ is an automorphism, and the set of all such maps forms the inner automorphism group $\operatorname{Inn}(S_n)$.[](https://people.brandeis.edu/~igusa/Math131b/auto.pdf) The [inner automorphism](/page/Inner_automorphism) group $\operatorname{Inn}(S_n)$ is isomorphic to the quotient $S_n / Z(S_n)$, where $Z(S_n)$ denotes [the center](/page/The_Center) of $S_n$. For $n \geq 3$, [the center](/page/The_Center) $Z(S_n)$ is trivial, consisting only of the [identity element](/page/Identity_element), because no non-identity [permutation](/page/Permutation) commutes with every element of $S_n$.[](https://people.brandeis.edu/~igusa/Math131b/auto.pdf) Consequently, $|\operatorname{Inn}(S_n)| = |S_n| = n!$ for $n \geq 3$.[](https://people.brandeis.edu/~igusa/Math131b/auto.pdf) The conjugation action of $S_n$ on itself defines a faithful representation, as the kernel of the corresponding homomorphism $S_n \to \operatorname{Aut}(S_n)$ is precisely $Z(S_n)$, which is trivial for $n \geq 3$. For example, in $S_3$, the center is trivial, so $\operatorname{Inn}(S_3) \cong S_3$.[](https://people.brandeis.edu/~igusa/Math131b/auto.pdf) ### Full Automorphism Group The automorphism group of the symmetric group $ S_n $ coincides with its group of inner automorphisms for all $ n \neq 2, 6 $. Since the center of $ S_n $ is trivial for $ n \geq 3 $, this implies that $\Aut(S_n) \cong S_n$ for $ n \geq 3 $, $ n \neq 6 $.[](https://link.springer.com/book/10.1007/978-1-4612-0731-3) The case $ n = 6 $ is exceptional: $ \Aut(S_6) $ has order twice that of $ S_6 $, namely $ 2 \times 720 = 1440 $, and the outer [automorphism group](/page/Automorphism_group) $ \Out(S_6) = \Aut(S_6)/\Inn(S_6) $ is cyclic of order 2. This outer automorphism arises from a non-trivial [symmetry](/page/Symmetry) in the structure of $ S_6 $, first described by Otto Hölder in 1895.[](http://math.stanford.edu/~vakil/files/sixjan2308.pdf) The non-trivial outer automorphism of $ S_6 $ interchanges certain conjugacy classes with the same [cycle index](/page/Cycle_index), notably swapping the class of [transpositions](/page/Transposition) (cycle type $ 2,1^4 $, size 15) with the class of products of three disjoint [transpositions](/page/Transposition) (cycle type $ 2^3 $, size 15). For instance, it can map the [transposition](/page/Transposition) $ (1\ 2) $ to $ (1\ 2)(3\ 4)(5\ 6) $, while preserving the group operation. This swapping reflects an underlying duality in the permutation representations of $ S_6 $.[](https://web.math.ucsb.edu/~jon.mccammond/papers/out-sym-6.pdf) ## Representation Theory ### Permutation Representations The [symmetric group](/page/Symmetric_group) $ S_n $ admits a natural [permutation](/page/Permutation) [representation](/page/Representation) on the [vector space](/page/Vector_space) $ \mathbb{C}^n $, where the group acts by permuting the [standard basis](/page/Standard_basis) vectors $ e_1, \dots, e_n $ via [permutation](/page/Permutation) matrices.[](https://math.mit.edu/research/highschool/primes/materials/2022/December/2-Kang-Zhao-Rabinovitz.pdf) This [representation](/page/Representation), often denoted $ \rho $, sends each [permutation](/page/Permutation) $ \sigma \in S_n $ to the matrix with 1 in position $ (i, \sigma(i)) $ and 0 elsewhere.[](https://math.berkeley.edu/~ltomczak/notes/Mich2022/RepSn_Notes.pdf) The [character](/page/Character) $ \chi $ of this [representation](/page/Representation) is given by $ \chi(\sigma) = $ the number of fixed points of $ \sigma $, since the [trace](/page/Trace) equals the number of basis vectors unchanged by the action.[](https://math.berkeley.edu/~ltomczak/notes/Mich2022/RepSn_Notes.pdf) This permutation representation decomposes as a direct sum of the trivial representation and the standard representation.[](https://math.mit.edu/research/highschool/primes/materials/2022/December/2-Kang-Zhao-Rabinovitz.pdf) The trivial summand is the one-dimensional subspace spanned by the vector $ \sum_{i=1}^n e_i $, on which $ S_n $ acts trivially. The standard representation arises on the orthogonal complement, the hyperplane $ W = \{ x \in \mathbb{C}^n \mid \sum_{i=1}^n x_i = 0 \} $, which is invariant under the action and has dimension $ n-1 $.[](https://math.mit.edu/research/highschool/primes/materials/2022/December/2-Kang-Zhao-Rabinovitz.pdf) For $ n \geq 2 $, the standard [representation](/page/Representation) is irreducible over $ \mathbb{C} $.[](https://www.math.ucla.edu/~emilg/pdfs/math_thesis.pdf) This follows from the fact that $ W $ has no proper nontrivial [invariant](/page/Invariant) subspaces under the $ S_n $-[action](/page/Action), as verified by explicit checks for small $ n $ and general arguments using the theory of Specht modules.[](https://www.math.ucla.edu/~emilg/pdfs/math_thesis.pdf) As an example, consider $ S_3 $ acting on $ \mathbb{C}^3 $. The permutation [representation](/page/Representation) decomposes as the [direct sum](/page/Direct_sum) of the trivial [representation](/page/Representation) and the two-dimensional standard [representation](/page/Representation), which is irreducible.[](https://math.mit.edu/research/highschool/primes/materials/2022/December/2-Kang-Zhao-Rabinovitz.pdf) Here, the standard subspace is spanned by vectors like $ e_1 - e_2 $ and $ e_2 - e_3 $, and the [action](/page/Action) preserves this plane while mixing its basis elements according to the group's transpositions and 3-cycles.[](https://math.mit.edu/research/highschool/primes/materials/2022/December/2-Kang-Zhao-Rabinovitz.pdf) ### Character Theory In the representation theory of the symmetric group $S_n$, the characters of its representations are class functions, constant on each [conjugacy class](/page/Conjugacy_class), which are parameterized by [partitions](/page/Partition) of $n$ corresponding to cycle types. This property arises because conjugate elements in $S_n$ have the same cycle structure, ensuring that the [trace](/page/Trace) of a representation [matrix](/page/Matrix) depends only on this structure. The set of class functions on $S_n$ forms a [vector space](/page/Vector_space) over $\mathbb{C}$, with the irreducible characters forming an [orthonormal basis](/page/Orthonormal_basis) under the inner product $\langle \chi, \psi \rangle = \frac{1}{|S_n|} \sum_{g \in S_n} \chi(g) \overline{\psi(g)}$. This [orthogonality](/page/Orthogonality) relation, fundamental to decomposing representations, implies that the inner product of distinct irreducible characters is zero, while $\langle \chi, \chi \rangle = 1$ for each irreducible $\chi$. By the general theory of finite groups, the number of irreducible [complex](/page/Complex) representations of $S_n$ equals the number of conjugacy classes, which is the partition function $p(n)$, the number of [integer](/page/Integer) partitions of $n$. Consequently, the irreducible characters are in one-to-one correspondence with partitions of $n$. The character table of $S_n$ tabulates these irreducible characters evaluated on conjugacy classes, with rows indexed by partitions and columns by cycle types. The dimension of the [irreducible representation](/page/Irreducible_representation) associated to a [partition](/page/Partition) $\lambda \vdash n$ is given by the hook-length formula: $\dim V^\lambda = n! / \prod_{(i,j) \in \lambda} h_{(i,j)}$, where $h_{(i,j)}$ is the hook length of the cell $(i,j)$ in the Young [diagram](/page/Diagram) of $\lambda$, equal to the number of cells to the right and below plus one. This formula, discovered by [Frame](/page/Frame), Robinson, and [Thrall](/page/Thrall), provides explicit degrees and is essential for constructing the table entries. For illustration, consider $S_3$, which has order 6 and three conjugacy classes: the [identity](/page/Identity) (cycle type $1^3$), transpositions (type $2,1$), and 3-cycles (type $3$). The character table is: | Partition | $\dim$ | $1^3$ | $2,1$ | $3$ | |-----------|----------|---------|---------|-------| | $(3)$ (trivial) | 1 | 1 | 1 | 1 | | $(2,1)$ ([standard](/page/Standard)) | 2 | 2 | 0 | -1 | | $(1^3)$ ([sign](/page/Sign)) | 1 | 1 | -1 | 1 | Here, the trivial representation has character values all 1, the [sign](/page/Sign) representation evaluates to the sign of permutations (1 on even, -1 on odd), and the 2-dimensional irreducible has values as traces in the permutation [representation](/page/Representation) modulo the trivial subrepresentation. This table satisfies [orthogonality](/page/Orthogonality), confirming completeness for $S_3$. ### Irreducible Representations The irreducible representations of the symmetric group $S_n$ over the complex numbers are parameterized by the partitions $\lambda \vdash n$ of the integer $n$, and are commonly denoted by $V^\lambda$ or the Specht modules $S^\lambda$.[](https://math.uchicago.edu/~may/REU2013/REUPapers/McNamara.pdf)[](https://link.springer.com/book/10.1007/978-1-4757-6804-1) These modules form a complete, irredundant set of pairwise non-isomorphic irreducible representations, up to isomorphism.[](https://math.uchicago.edu/~may/REU2013/REUPapers/McNamara.pdf)[](https://yufeizhao.com/research/youngtab-hcmr.pdf) A partition $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_k)$ with $\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_k \geq 1$ and $\sum \lambda_i = n$ is visualized by its associated Young diagram, consisting of $\lambda_i$ left-justified boxes in the $i$-th row. The conjugate partition $\lambda'$ is obtained by reflecting the diagram over its main diagonal, yielding the column lengths. The Robinson–Schensted–Knuth (RSK) correspondence provides a bijection between permutations in $S_n$ and pairs of standard Young tableaux of the same shape $\lambda \vdash n$, where a standard Young tableau is a filling of the diagram with $1$ to $n$ such that entries increase across rows and down columns; this links the combinatorial structure of tableaux to the representation theory of $S_n$.[](https://yufeizhao.com/research/youngtab-hcmr.pdf)[](https://www.symmetricfunctions.com/rsk.htm) The Specht module $S^\lambda$ is constructed using the Young symmetrizer associated to a fixed standard Young tableau $T$ of shape $\lambda$. Let $R_T$ be the row stabilizer subgroup of $S_n$ (generated by transpositions within rows of $T$) and $C_T$ the column stabilizer (generated by transpositions within columns). The row symmetrizer is $a_T = \sum_{\sigma \in R_T} \sigma$ and the column antisymmetrizer is $b_T = \sum_{\tau \in C_T} \operatorname{sgn}(\tau) \tau$. The Young symmetrizer is then $c_T = a_T b_T$, an idempotent (up to scalar) in the group algebra $\mathbb{C}[S_n]$ that projects the regular representation onto a copy of $S^\lambda$. More generally, $s_\lambda = \sum_T c_T$, where the sum is over all standard tableaux $T$ of shape $\lambda$, generates the left ideal corresponding to $S^\lambda$.[](https://math.uchicago.edu/~may/REU2013/REUPapers/McNamara.pdf)[](https://indico.cern.ch/event/396357/sessions/161619/attachments/1129258/1619380/Young_Tableaux.pdf) A basis for $S^\lambda$ is given by the polytabloids $\{e_T \mid T \text{ standard of shape } \lambda\}$, where $e_T = \sum_{\pi \in C_T} \operatorname{sgn}(\pi) \pi \cdot \{T\}$ and $\{T\}$ is the tabloid obtained by ignoring row distinctions in $T$. The dimension of $S^\lambda$, equal to the number of standard Young tableaux of shape $\lambda$, is provided by the hook-length formula: f^\lambda = \frac{n!}{\prod_{u \in \lambda} h_u}, where $h_u$ is the hook length of box $u$, the number of boxes to the right and below $u$ in the diagram, plus one for $u$ itself.[](https://math.uchicago.edu/~may/REU2013/REUPapers/McNamara.pdf)[](https://math.mit.edu/~rstan/transparencies/hooks.pdf) This formula was proved by Frame, Robinson, and Thrall.[](https://math.mit.edu/~rstan/transparencies/hooks.pdf) For $S_4$, the partitions are $(4)$, $(3,1)$, $(2,2)$, $(2,1,1)$, and $(1^4)$, with corresponding dimensions $1$, $3$, $2$, $3$, and $1$. These yield the trivial [representation](/page/Representation), the standard [representation](/page/Representation) of dimension $3$, the sign [representation](/page/Representation) (for $(1^4)$), and two other irreducibles of dimensions $2$ and $3$.[](https://math.uchicago.edu/~may/REU2013/REUPapers/McNamara.pdf)[](https://yufeizhao.com/research/youngtab-hcmr.pdf) The [branching rule](/page/Rule) describes the restriction $\operatorname{Res}_{S_{n-1}}^{S_n} S^\lambda$: it decomposes as the [direct sum](/page/Direct_sum) $\bigoplus_\mu S^\mu$, where the sum is over all partitions $\mu \vdash (n-1)$ obtained by removing a single box (a removable rim $1$-hook) from the Young [diagram](/page/Diagram) of $\lambda$, with multiplicity one for each such $\mu$.[](https://www.math.columbia.edu/~dejong/notes-bob/symmetricgroup.pdf) This [rule](/page/Rule) allows recursive computation of representation-theoretic data from smaller symmetric groups.[](https://www.math.columbia.edu/~dejong/notes-bob/symmetricgroup.pdf) ## Homological Algebra ### Homology Groups The group homology $ H_*(S_n; \mathbb{Z}) $ with trivial $\mathbb{Z}$-action is the singular homology of the [classifying space](/page/Classifying_space) $ BS_n $. This homology captures algebraic properties of the symmetric group, such as its abelianization in degree 1 and [Schur multiplier](/page/Schur_multiplier) in degree 2. Computations of these groups rely on resolutions of the trivial module or geometric models of $ BS_n $, including configuration spaces of points in [Euclidean space](/page/Euclidean_space). In low degrees, the first homology group is $ H_1(S_n; \mathbb{Z}) = \mathbb{Z}/2\mathbb{Z} $ for $ n \ge 2 $, isomorphic to the abelianization $ S_n / [S_n, S_n] = S_n / A_n $, where $ A_n $ is the [alternating group](/page/Alternating_group). The second homology group is $ H_2(S_n; \mathbb{Z}) = 0 $ for $ n \le 3 $ and $ H_2(S_n; \mathbb{Z}) = \mathbb{Z}/2\mathbb{Z} $ for $ n \ge 4 $, coinciding with the [Schur multiplier](/page/Schur_multiplier) of $ S_n $. These results follow from explicit computations using the bar resolution and properties of central extensions. As $ n \to \infty $, the [homology](/page/Homology) groups stabilize in degrees $ k \le n - 2 $, a phenomenon established by Nakaoka's [stability theorem](/page/Theorem). The stable [homology](/page/Homology) $ H_*^s(S_\infty; \mathbb{F}_p) $ of the infinite symmetric group $ S_\infty $ with mod $ p $ coefficients is an algebra over the Dyer-Lashof algebra $ \mathbb{Q}_p $, generated by admissible operations $ Q^I $ acting on the polynomial generators in [homology](/page/Homology). This structure arises from the identification of $ BS_\infty $ with the basepoint component of the infinite loop space $ \Omega^\infty_0 S^\infty $, where the Dyer-Lashof operations encode excess relations and provide a minimal [resolution](/page/Resolution) of the trivial module mod $ p $. Over the integers, the stable [homology](/page/Homology) is torsion, with rational [homology](/page/Homology) vanishing in positive degrees due to the finiteness of each $ S_n $. Since $ S_n $ is finite, the Betti numbers $ b_k(n) = \rank H_k(S_n; \mathbb{Z}) = 0 $ for all $ k > 0 $, reflecting the absence of free parts in the torsion [homology](/page/Homology) groups. Nakaoka's decomposition theorem expresses $ H_k(S_n; \mathbb{Z}) $ as a [direct sum](/page/Direct_sum) of terms induced from [wreath](/page/Wreath) products and stable factors. Alternatively, geometric models via configuration spaces yield recursive formulas; for instance, the Fadell-Neuwirth [fibration](/page/Fibration) relates the [homology](/page/Homology) of unordered configurations in $ \mathbb{R}^d $ (for $ d \ge 3 $) to that of $ BS_n $ via the associated [fibration](/page/Fibration) of classifying spaces and the [Serre spectral sequence](/page/Serre_spectral_sequence), though the Betti numbers of $ BS_n $ remain zero in positive degrees. For the small case $ n=3 $, the homology groups are computable via the [classifying space](/page/Classifying_space) $ BS_3 $, which admits a model as the total space of a [fibration](/page/Fibration) with [fiber](/page/Fiber) $ B\mathbb{Z}/3\mathbb{Z} = S^\infty $ and base $ B\mathbb{Z}/2\mathbb{Z} = \mathbb{RP}^\infty $. The resulting [spectral sequence](/page/Spectral_sequence) yields $ H_0(BS_3; \mathbb{Z}) = \mathbb{Z} $, $ H_1(BS_3; \mathbb{Z}) = \mathbb{Z}/2\mathbb{Z} $, $ H_2(BS_3; \mathbb{Z}) = 0 $, $ H_3(BS_3; \mathbb{Z}) = \mathbb{Z}/6\mathbb{Z} $, and torsion in higher degrees reflecting the [semidirect product](/page/Semidirect_product) structure $ S_3 = \mathbb{Z}/3\mathbb{Z} \rtimes \mathbb{Z}/2\mathbb{Z} $. This computation aligns with the general low-degree pattern and serves as a benchmark for stability. ### Connections to Topology The ordered configuration space $ F_n(\mathbb{R}^2) $ consists of $ n $-tuples of distinct points in the plane, and its [fundamental group](/page/Fundamental_group) is the pure braid group $ P_n $. The symmetric group $ S_n $ acts freely on $ F_n(\mathbb{R}^2) $ by permuting the coordinates, and the quotient space $ C_n(\mathbb{R}^2) := F_n(\mathbb{R}^2)/S_n $, known as the unordered configuration space, has [fundamental group](/page/Fundamental_group) the full [braid group](/page/Braid_group) $ B_n $. This action induces a short [exact sequence](/page/Exact_sequence) $ 1 \to P_n \to B_n \to S_n \to 1 $, reflecting the central role of $ S_n $ in the topological structure of braid groups. The Fadell-Neuwirth [fibration](/page/Fibration) provides a recursive structure for these spaces: the [projection](/page/Projection) $ F_n(M) \to F_{n-1}(M) $ forgetting the last point is a [fiber bundle](/page/Fiber_bundle) with fiber $ M $ minus $ n-1 $ points, for a manifold $ M $ without [boundary](/page/Boundary). For $ M = \mathbb{R}^2 $, this yields $ \pi_1(P_n) $ as a free product of free groups, enabling inductive computations of [braid group](/page/Braid_group) presentations. In the unordered case, this [fibration](/page/Fibration) lifts to relate the topology of $ C_n(\mathbb{R}^2) $ to lower-dimensional configurations, highlighting how $ S_n $-actions encode permutations in the braiding process. The homology of the unordered configuration space $ H_*(C_n(\mathbb{R}^2)) $ coincides with the group homology $ H_*(B_n; \mathbb{Z}) $, since $ C_n(\mathbb{R}^2) $ is a model for the classifying space $ BB_n $. The extension $ P_n \to B_n \to S_n $ induces a fibration of classifying spaces $ BP_n \to BB_n \to BS_n $, allowing the Serre spectral sequence to relate $ H_*(BB_n) $ to $ H_*(BS_n) $ and $ H_*(BP_n) $. For instance, with rational coefficients, $ H_1(BS_n; \mathbb{Q}) = 0 $ since $ S_n $ is finite and its abelianization is torsion of order 2, but higher-degree terms arise from the fiber's homology via the Fadell-Neuwirth structure, contributing nontrivial classes in degrees up to $ n-1 $. Arnold's seminal computation describes the [cohomology](/page/Cohomology) ring of the pure [braid group](/page/Braid_group) $ H^*(P_n; \mathbb{Z}) $ as an [exterior algebra](/page/Exterior_algebra) on $ \binom{n}{2} $ generators in degree 1, corresponding to [linking classes](/page/Linking_number) between pairs of strands. For the full [braid group](/page/Braid_group), the stable [cohomology](/page/Cohomology) ring $ H^*(B_n; \mathbb{Z}) $ in low degrees stabilizes as $ n $ grows, with $ H^1(B_n; \mathbb{Z}) \cong \mathbb{Z} $ generated by the total [linking number](/page/Linking_number), and higher stable classes forming a [polynomial ring](/page/Polynomial_ring) tensored with an [exterior algebra](/page/Exterior_algebra) on generators in even degrees. These results stem from the topological invariants of [configuration](/page/Configuration) spaces and have influenced computations of $ S_n $-equivariant [homology](/page/Homology) through the associated fibrations.[](https://link.springer.com/article/10.1007/BF01098313) ## Applications ### Combinatorics and Enumeration The symmetric group $ S_n $ consists of all bijections (permutations) of a set with $ n $ elements, and its [order](/page/Order) is therefore $ n! $, which counts the total number of distinct arrangements of $ n $ objects.[](https://mathworld.wolfram.com/SymmetricGroup.html) This factorial growth underscores the group's foundational role in [combinatorics](/page/Combinatorics), where permutations model rearrangements and symmetries of finite sets./04%3A_Families_of_Groups/4.03%3A_Symmetric_Groups) Permutations in $ S_n $ admit a unique encoding via inversion tables, which provide a [bijection](/page/Bijection) between the set of all permutations and the set of [integer](/page/Integer) sequences $ (a_1, a_2, \dots, a_n) $ where $ 0 \leq a_i \leq i-1 $ for each $ i $.[](https://arxiv.org/pdf/2305.09457) The entry $ a_i $ records the number of elements to the left of $ i $ in the permutation that are greater than $ i $, offering a direct way to reconstruct the permutation by inserting elements from largest to smallest while accounting for inversions. This representation also establishes a [bijection](/page/Bijection) with parking functions, sequences $ (b_1, \dots, b_n) $ with $ 1 \leq b_i \leq n $ satisfying the condition that if sorted as $ b_{(1)} \leq \cdots \leq b_{(n)} $, then $ b_{(i)} \leq i $; the map shifts the inversion table by adding 1 to each entry.[](https://math.mit.edu/~rstan/pubs/pubfiles/107.pdf) Additionally, inversion tables correspond bijectively to certain 0-1 matrices, specifically those that are strictly upper triangular with row sums given by the table entries, facilitating combinatorial interpretations in terms of partial orders and tableaux.[](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v27i1p39/pdf/) A key enumeration tool for permutations involves their cycle decompositions. The unsigned Stirling numbers of the first kind $ c(n,k) $ count the number of permutations in $ S_n $ with exactly $ k $ cycles, satisfying the recurrence $ c(n,k) = c(n-1,k-1) + (n-1) c(n-1,k) $ with $ c(0,0) = 1 $ and $ c(n,0) = 0 $ for $ n > 0 $./01%3A_Fundamentals/1.09%3A_Stirling_numbers) More generally, the number of permutations with a specified cycle type—given by multiplicities $ m_i $ of cycles of length $ i $, where $ \sum i m_i = n $—is $ \frac{n!}{\prod_i (i^{m_i} m_i!)} $.[](https://planetmath.org/conjugacyclassesinthesymmetricgroupsn) This formula arises from choosing elements for each cycle length, arranging them cyclically (dividing by $ i $ for rotational symmetry), and accounting for indistinguishability among cycles of the same length (dividing by $ m_i! $). Involutions, permutations that are their own inverses (equivalently, products of disjoint fixed points and transpositions), provide a concrete example of cycle-type enumeration restricted to partitions of $ n $ into parts of size at most 2. The number of such involutions in $ S_n $ is $ \sum_{k=0}^{\lfloor n/2 \rfloor} \frac{n!}{2^k k! (n-2k)!} $, obtained by choosing $ 2k $ elements for the $ k $ transpositions (arranged in $ (2k)! / (2^k k!) $ ways) and fixing the rest. For instance, in $ S_3 $, there are 4 involutions: the [identity](/page/Identity) and the three transpositions.[](https://oeis.org/A000085) ### Geometry and Symmetry The symmetric group $ S_n $ serves as the full symmetry group of the regular $(n-1)$-simplex embedded in $(n-1)$-dimensional Euclidean space, where the $ n $ vertices can be labeled distinctly, and any permutation of these labels induces an isometry preserving the simplex's regularity. This realization highlights $ S_n $'s role in geometric symmetry, as the group acts faithfully by permuting the vertices while fixing the barycenter. Similarly, $ S_n $ is the automorphism group of the complete graph $ K_n $, the graph with $ n $ vertices and all possible edges between them; any relabeling of vertices via a permutation preserves the edge set completely.[](https://webbox.lafayette.edu/~gordong/pubs/auto1.pdf)[](https://mathworld.wolfram.com/GraphAutomorphism.html) As a finite Coxeter group of type $ A_{n-1} $, $ S_n $ can be realized as a [reflection group](/page/Reflection_group) acting on $ \mathbb{R}^{n-1} $, generated by $ n-1 $ simple reflections corresponding to adjacent transpositions $ (i \ i+1) $ for $ i = 1, \dots, n-1 $. The Coxeter presentation is given by relations $ s_i^2 = 1 $ and $ (s_i s_{i+1})^3 = 1 $ for adjacent generators, with commuting relations for non-adjacent ones, embedding $ S_n $ into the [orthogonal group](/page/Orthogonal_group) $ O(n-1, \mathbb{R}) $ via reflections across hyperplanes perpendicular to the roots of the $ A_{n-1} $ [root system](/page/Root_system). The action of $ S_n $ on this [root system](/page/Root_system)—the set of vectors $ e_i - e_j $ for $ i \neq j $ in the hyperplane $ \sum x_k = 0 $ of $ \mathbb{R}^n $—preserves the [lattice](/page/Lattice) structure and permutes the roots transitively, reflecting the group's [permutation](/page/Permutation) nature in a geometric [lattice](/page/Lattice) context.[](https://sites.math.washington.edu/~billey/classes/reflection.groups/references/Humphreys.ReflectionGroupsAndCoxeterGroups.pdf)[](https://mathworld.wolfram.com/RootSystem.html) A concrete example is $ S_3 $, which is isomorphic to the [dihedral group](/page/Dihedral_group) $ D_3 $ of [order](/page/Order) 6, representing the full [symmetry group](/page/Symmetry_group) of an [equilateral triangle](/page/Equilateral_triangle) in the plane. The three rotations (by 0°, 120°, and 240°) and three reflections across the altitudes correspond to the [identity](/page/Identity), 3-cycles, and transpositions in $ S_3 $, illustrating how permutations translate to rigid motions preserving the triangle's shape.[](https://math.berkeley.edu/~arash/113/notes/8.pdf) In [crystallography](/page/Crystallography), symmetric groups appear only in low dimensions among the [32](/page/32) crystallographic point groups, which are finite subgroups of $ O(3) $ compatible with lattice translations. Specifically, $ S_2 \cong C_2 $ ([cyclic group](/page/Cyclic_group) of [order](/page/Order) 2) arises as a twofold rotation group, and $ S_3 \cong D_3 $ as the point group of trigonal symmetry, such as in certain [mineral](/page/Mineral) structures; S_4 is isomorphic to Td, the full tetrahedral point group; symmetric groups $ S_n $ for $ n > 4 $ do not embed faithfully into these point groups due to dimensional constraints in 3D space.[](https://chem.libretexts.org/Bookshelves/Inorganic_Chemistry/Chemical_Group_Theory_(Miller)/02%3A_Rotational_Symmetry/2.04%3A_Crystallographic_Point_Groups)[](http://gernot-katzers-spice-pages.com/character_tables/Td.html) ### Computational Aspects Computational aspects of the symmetric group $S_n$ are facilitated by specialized [computer algebra](/page/Computer_algebra) systems such as [GAP](/page/Gap) and [Magma](/page/Magma), which support efficient operations on [permutation group](/page/Permutation_group)s including $S_n$. In [GAP](/page/Gap), the symmetric group is constructed via `SymmetricGroup(n)`, enabling computations like order determination, [subgroup](/page/Subgroup) identification, and [element](/page/Element) [enumeration](/page/Enumeration), leveraging internal algorithms optimized for [permutation](/page/Permutation) representations. Similarly, Magma provides `SymmetricGroup(n)` for creating $S_n$ as a [permutation group](/page/Permutation_group), supporting advanced tasks such as computing conjugacy classes and centralizers with built-in efficiency for large degrees.[](https://magma.maths.usyd.edu.au/magma/handbook/text/1101) A cornerstone algorithm for computations in permutation groups like $S_n$ is the Schreier-Sims algorithm, which constructs a [base](/page/Base) and strong generating set (BSGS) from given generators, allowing deterministic membership testing in polynomial time relative to the degree $n$ and group order logarithm. This [algorithm](/page/Algorithm), refined in implementations within [GAP](/page/Gap) and [Magma](/page/Magma), reduces the stabilizer chain to enable fast queries such as verifying if a permutation belongs to $S_n$ or a [subgroup](/page/Subgroup), with [time complexity](/page/Time_complexity) $O(n^2 \log^3 |G|)$ in practice for $S_n$.[](https://www.researchgate.net/publication/239215244_The_Schreier-Sims_algorithm) For example, applying Schreier-Sims to the standard generators of $S_n$ (transpositions) yields a BSGS that supports efficient orbit-stabilizer computations essential for enumerative tasks. The [cycle index](/page/Cycle_index) polynomial of $S_n$, $Z(S_n; x_1, \dots, x_n) = \frac{1}{n!} \sum_{\sigma \in S_n} \prod_{i=1}^n x_i^{c_i(\sigma)}$, where $c_i(\sigma)$ counts $i$-cycles in $\sigma$, can be computed exactly using recurrences based on exponential generating functions, achieving $O(n^2)$ [time complexity](/page/Time_complexity) by iteratively building coefficients from smaller degrees. This polynomial encodes [enumeration](/page/Enumeration) under group actions, and its computation in systems like [GAP](/page/Gap) via `CycleIndex` is optimized for degrees up to several hundred.[](https://www.mathe2.uni-bayreuth.de/frib/html/symman/manual_21.html) Generating random elements uniformly from $S_n$ is typically performed using the Fisher-Yates shuffle algorithm, which produces a [random permutation](/page/Random_permutation) in $O(n)$ time by sequentially swapping elements. For the [alternating group](/page/Alternating_group) $A_n$, a standard method to generate a random even permutation involves producing a uniform random element of $S_n$ and, if odd, multiplying by a fixed transposition; more direct approaches exploit the generation by 3-cycles, where a random even permutation can be obtained as a product of randomly selected 3-cycles, ensuring uniformity through sufficient length products in $O(n \log n)$ expected steps.[](https://www.jjj.de/pub/arndt-rand-perm-thesis.pdf) Permutation [multiplication](/page/Multiplication) in $S_n$, when represented as arrays of [length](/page/Length) $n$, requires $O(n)$ time to compose two [elements](/page/Fifth_Element) by applying one to the images under the other. For large $n$, sparse representations—storing only moved points and cycles—reduce complexity to $O(s)$, where $s$ is the support size (number of non-fixed points), enabling efficient handling of [elements](/page/Fifth_Element) with small support in applications like random walks on $S_n$.[](https://people.cs.uchicago.edu/~laci/papers/debrecen.pdf) Precomputed data for $S_n$ is available in the ATLAS of Finite Group Representations, which includes character tables, irreducible representations, and modular data for symmetric groups up to degree 20, supporting theoretical computations without on-the-fly generation. Recent post-2020 developments include quantum algorithms for evaluating characters of $S_n$, offering potential exponential speedups over classical methods for large $n$ in quantum settings, though classical tools like ATLAS remain standard for practical representation data.[](https://brauer.maths.qmul.ac.uk/Atlas/v3/)

References

  1. [1]
    [PDF] The symmetric group
    Definition 1.3. The symmetric group Sn is the group Perm({1,...,n}) of all permutations on the first n integers.Missing: mathematics | Show results with:mathematics
  2. [2]
    [PDF] Math 412. The Symmetric Group Sn.
    DEFINITION: The symmetric group Sn is the group of bijections from any set of n objects, which we usu- ally call simply {1,2,...,n}, to itself. An element of ...Missing: S_n | Show results with:S_n
  3. [3]
    [PDF] The symmetric group
    The symmetric group of degree n, denoted Sn, is the group whose elements are p.29 the permutations on the set {1,...,n}, and the binary operation is function ...Missing: S_n | Show results with:S_n
  4. [4]
    [PDF] Lecture 2.3: Symmetric and alternating groups
    Symmetric groups are the collection of all n! permutations of n objects. Alternating groups are similar. The symmetric group of n items is denoted by Sn.Missing: S_n | Show results with:S_n<|control11|><|separator|>
  5. [5]
    [PDF] Chapter 1 Symmetries, groups, and group actions - UCSD Math
    Every group G can be embedded into SG. A subgroup of a symmetric group is called a permutation group. Cayley's theorem says that every group group can be ...
  6. [6]
    [PDF] representations of the symmetric group - UChicago Math
    Sep 1, 2010 · This section introduces characters and how they can be used to find irreducible representations and decompositions of arbitrary representations.
  7. [7]
    [PDF] 7 Symmetry and Group Theory - Penn Math
    One of the primary applications of group theory is the study of symmetries of shapes of different kinds. Symmetries of shapes form groups, and this sec-.
  8. [8]
    Symmetric Group -- from Wolfram MathWorld
    The symmetric group S_n of degree n is the group of all permutations on n symbols. S_n is therefore a permutation group of order n!
  9. [9]
    one-line notation for permutations - PlanetMath.org
    Mar 22, 2013 · First consider the permutation π=(134)(25) π = ( 134 ) ⁢ ( 25 ) in the symmetric group S5 𝔖 5 . Here π π is written in cycle notation, ...
  10. [10]
    [PDF] A History of Lagrange's Theorem on Groups
    Lagrange's Theorem first appeared in 1770-71 in connection with the problem of solving the general polynomial of degree 5 or higher, and its relation to.
  11. [11]
    symmetric group in nLab
    ### Summary of Order of Symmetric Group \( S_n \) and Infinite Case
  12. [12]
    Symmetric group - Groupprops
    Jul 26, 2011 · Two-line notation and one-line notation · Cycle decomposition for permutations · Upto conjugacy · Upto automorphism.
  13. [13]
    3.1: Symmetric Groups
    ### Summary: Symmetric Groups Being Non-Abelian for n ≥ 3
  14. [14]
    Determination of multiplication table of symmetric group:S3
    Feb 23, 2014 · The purpose of this page is to give a detailed description of the construction of the multiplication table of symmetric group:S3.
  15. [15]
    [PDF] Abstract Algebra
    ... group of) invertible integers modulo n the ... ABSTRACT ALGEBRA. Third Edition. David S. Dummit. University of Vermont. Richard M. Foote. University of Vermont.
  16. [16]
    [PDF] Group Theory - James Milne
    These notes give a concise exposition of the theory of groups, including free groups and Coxeter groups, the Sylow theorems, and the representation theory ...
  17. [17]
    [PDF] Symmetric group
    To check that the symmetric group on a set X is indeed a group, it is necessary to verify the group axioms of associativity, identity, and inverses. The ...
  18. [18]
    [PDF] Math 403 Chapter 5 Permutation Groups: 1. Introduction
    (a) Definition: The symmetric group Sn is the group of all permutations of the set 11, 2, ..., nl. Example: The group S3 consists of six elements.Missing: S_n | Show results with:S_n
  19. [19]
    [PDF] Chapter 7 Permutation Groups
    Let us see a few examples of symmetric groups Sn. Example 26. If n = 1, S1 contains only one element, the permutation identity! Example 27. If n = ...<|control11|><|separator|>
  20. [20]
    5.1: Definitions and Notation - Mathematics LibreTexts
    Apr 5, 2024 · Example 5.5. The permutation. σ = ( 1 2 3 ... Every permutation in S n can be written as the product of disjoint cycles.
  21. [21]
    3.1: Symmetric Groups - Mathematics LibreTexts
    Nov 20, 2024 · Note. Notice that all the elements in S 3 in S 4 . The following theorem proves that S n are non-Abelian for integer n ≥ 3, which means that the ...
  22. [22]
    [PDF] GENERATING SETS 1. Introduction In Rn, every vector can be ...
    ... 1 and 2 is generated by the 3-cycles of the form (12i). For a 3-cycle containing 1 but not 2, say (1ij), check. (1ij) = (12j)(12j)(12i)(12j). By Theorem 3.2 ...
  23. [23]
    [PDF] Sign of permutations - Keith Conrad
    The 3-cycle (123) is (12)(23), a product of 2 transpositions, so sgn(123) = 1. Example 2.9. What is the sign of a k-cycle? Since. (i1i2 ···ik)=(i1i2)(i2i3)· ...
  24. [24]
    26.13 Permutations: Cycle Notation
    A permutation is even or odd according to the parity of the number of transpositions. The sign of a permutation is + if the permutation is even, − if it is odd.
  25. [25]
    [PDF] The Symmetric Group - UBC Math
    The symmetric group S(n) is the group of bijections or permutations of a set of n objects, playing a fundamental role in mathematics.
  26. [26]
    [PDF] Enumerative Combinatorics Volume 1 second edition - Mathematics
    Chapter 1. What is Enumerative Combinatorics? 1.1. How to count. 9. 1.2. Sets and multisets. 23. 1.3. Cycles and inversions.
  27. [27]
    Derangement -- from Wolfram MathWorld
    Nicholas Bernoulli also solved the problem using the inclusion-exclusion principle (de Montmort 1713-1714, p. 301; Bhatnagar 1995, p. 8). Derangements are ...
  28. [28]
    conjugacy classes in the symmetric group S_n - PlanetMath
    The above theorem proves that the cycle type is well-defined. Theorem 2. Two ... Proof. The size of a conjugacy class is the number of cycles of the given cycle ...
  29. [29]
    [PDF] 2.3 Conjugacy in symmetric groups - maths.nuigalway.ie
    Our conclusion is the following theorem. Theorem 2.3.8. Two elements of Sn are in the same conjugacy class if and only if they have the same cycle type.
  30. [30]
    [PDF] 21 Conjugacy Classes for Symmetric and Alternating Groups
    Today, we will be looking at the conjugacy classes for Sn and An, the symmetric group and the alternating group, which consists of even permutations. Recall ...Missing: theorem | Show results with:theorem
  31. [31]
    Cycle Index -- from Wolfram MathWorld
    The cycle index Z(X) of a permutation group X of order m=|X| and degree d is then the polynomial in d variables x_1, x_2, ..., x_d given by the formula
  32. [32]
    [PDF] Abstract Algebra. Math 6320. Bertram/Utah 2022-23. Groups We ...
    The alternating group An is the kernel of the sign homomorphism: sgn : Sn → {±1} and therefore it is a normal subgroup of Sn, with two cosets, and. |Sn| = 2 ...
  33. [33]
    [PDF] An is generated by the 3-cycles
    Mar 5, 2008 · The idea of the proof is that we will show that any product of two trans- positions is a product of 3-cycles; and, if so, then since every ...
  34. [34]
    [PDF] Lecture 7 - MATH 415, Spring 2021 [3mm] Modern Algebra I
    The alternating group A3 has 3 elements: the identity function and two cycles of length 3, (1 2 3) and (1 3 2). • The alternating group A4 has 12 elements of ...
  35. [35]
    [PDF] Modern Algebra
    Symmetric ... index 2 and order |Sn|/2 = n!/2. Furthermore An is the only subgroup of Sn of index. 2. The group An is called the alternating group on n letters.
  36. [36]
    [PDF] 1.6 Symmetric, Alternating, and Dihedral Groups
    The set An of all even permutations of Sn forms a subgroup of Sn of index 2. So An is a normal subgroup of Sn with |An| = n!/2. An is called the alternating ...
  37. [37]
    [PDF] The Alternating Groups - DSpace@MIT
    The symmetric group Sn consists of all permutations of a set of n elements. Any set of n elements will do, but we usually use the set S = {1, 2, ..., n}. The ...
  38. [38]
    [PDF] SIMPLICITY OF An - KEITH CONRAD
    We need three lemmas: two are about alternating groups and one is about symmetric groups on n letters for n ≥ 5. Lemma 2.1. For n ≥ 3, An is generated by 3- ...
  39. [39]
    [PDF] classification of finite simple groups - UChicago Math
    Aug 31, 2010 · The alternating group on 3 elements A3 is a member of the family of cyclic ... |A4| = 12, so is not a group of prime order. In fact, it is ...
  40. [40]
    [PDF] Supplement. The Alternating Groups A are Simple for n ≥ 5
    Jan 10, 2013 · So N contains a 3-cycle and by Case I, N = An and An is simple (this case holds for n ≥ 5). n ≥ 5 in the proof that An is simple. In fact, A4 ...
  41. [41]
    [PDF] Simplicity of An Proposition 1. The group A5 is simple. Proof. There ...
    Oct 11, 2015 · So N = A6 or N = {1}. A6 is simple. Lemma 3. For n ≥ 5, any two 3-cycles in An are conjugate in An. Proof. It is sufficient to show that ...Missing: A_n | Show results with:A_n
  42. [42]
    How do i prove that any subgroup of $A_5$ has order at most 12?
    Nov 12, 2018 · Any subgroup of order 30 would have index 2, so would be normal, contradicting your previous result. Thus, H must have order 15 or 20. Now, both ...Subgroups of $A_5$ have order at most $12 - Math Stack ExchangeAlternative proofs that $A_5$ is simple - Math Stack ExchangeMore results from math.stackexchange.com
  43. [43]
    Symmetric group:S3 - Groupprops
    Dec 3, 2024 · It is the symmetric group on a set of three elements, viz., the group of all permutations of a three-element set. · It is the dihedral group of ...Element structure of symmetric... · Subgroup structure of... · Standard representation
  44. [44]
    Normal Klein four-subgroup of symmetric group:S4 - Groupprops
    Jun 27, 2011 · This article discusses the normal subgroup in the symmetric group of degree four comrpising the identity and the three double transpositions.4Effect of subgroup operators · 6Description in terms of... · 7Related subgroups
  45. [45]
    [PDF] 9 Automorphism groups - Brandeis
    The symmetric groups Sn are complete for n 6= 2, 6. If n ≥ 3, Sn has no center. So it suffices to show that every automorphism of Sn is inner for n 6= 6. Lemma ...<|separator|>
  46. [46]
    None
    ### Summary of the Outer Automorphism of S_6
  47. [47]
    [PDF] Exercises on the outer automorphism of S6
    Having proven that S6 is the only symmetric group with an outer auto- morphism, let's investigate another description of this outer automorphism. This ...
  48. [48]
    [PDF] arXiv:math/0405185v1 [math.GR] 11 May 2004
    Consider the group generated by the transpositions (ab) ∈ Sn for the edges (a, b) in T; obviously this is the full symmetric group Sn iff T is connected.Missing: S_n | Show results with:S_n
  49. [49]
    symmetric group is generated by adjacent transpositions - PlanetMath
    Mar 22, 2013 · symmetric group is generated by adjacent transpositions · Theorem 1. · Proof. We proceed by induction on n n . If n=2 n = 2 , ...
  50. [50]
    [PDF] Lecture 4B: Coxeter groups - Nathan Reading
    combinatorial group theory. That is, we are given a presentation of a group by generators and relations. The abstract algebra encodes the geometry ...
  51. [51]
    [PDF] Presenting the Symmetric Group with Transpositions - CORE
    In this note we give a presentation of S, relative to any set of n - l generating transpositions. 2. STATEMENT AND PROOF OF THE THEOREM. Let T be a graph with ...Missing: 1893 | Show results with:1893
  52. [52]
    Concerning the Abstract Groups of Order k ! and ½k ! Holohedrically ...
    Concerning the Abstract Groups of Order k ! and ½k ! Holohedrically Isomorphic with the Symmetric and the Alternating Substitution-Groups on k Letters.
  53. [53]
    [PDF] Reflection groups and Coxeter groups
    Chapter 1 develops the most important facts about finite reflection groups and related geometry, leading to the presentation of such groups as Coxeter groups.
  54. [54]
    [PDF] Short Presentations for alternating and symmetric groups
    We construct two kinds of presentations for the alternating and symmetric groups of degree n: the first are on two generators in which the number of relations ...
  55. [55]
    [PDF] Groups - LSU Math
    (Cayley) Any group G is isomorphic to a subgroup of the symmetric group SG. ... Then H is a subgroup of S4 isomorphic with the Klein 4-group, and since H consists.
  56. [56]
    Subgroup structure of symmetric group:S6 - Groupprops
    Jun 1, 2012 · The only normal subgroups are the whole group, the trivial subgroup, and alternating group:A6 as A6 in S6.
  57. [57]
    [PDF] Chapter 1 Group theory - UW Math Department
    The nth symmetric group, denoted Sn, is the group of all per- mutations of ... The only normal subgroups of S5 are A5, S5, and {1}. Proof. Let H be a ...
  58. [58]
    normal subgroups of the symmetric groups - PlanetMath.org
    Mar 22, 2013 · Proof. If n=1 , S1 is the trivial group, so it has no nontrivial [normal] subgroups. If n=2 , S2=C2 S 2 = C 2 , the unique group on 2 elements, ...
  59. [59]
    Permutation Groups - SpringerLink
    This text can serve as an introduction to permutation groups in a course at the graduate or advanced undergraduate level, or for self- study.
  60. [60]
    [PDF] The maximal subgroups of the symmetric group - Ensaios Matemáticos
    We will discuss the proof of the fact that the maximal intransitive and the maximal imprimitive subgroups of Sn are indeed maximal subgroups of Sn and we will ...
  61. [61]
    https://doi.org/10.1017/S1446788700029079
  62. [62]
    https://doi.org/10.1017/CBO9780511623675
  63. [63]
    Transitive groups of degree up to 31 - GroupNames
    The transitive group database in GAP and Magma contains all transitive subgroups of S n up to conjugacy for n≤31, numbered nTi (or T n,i ).<|control11|><|separator|>
  64. [64]
    [PDF] Primitive permutation groups 1 The basics 2 Minimal normal ...
    Aug 27, 2004 · It can be shown that the permutation group H, of degree m, is primitive and not regular, while K is transitive. The relevant part of the O'Nan– ...<|control11|><|separator|>
  65. [65]
    [PDF] Representation Theory of Symmetric Groups - Princeton Math
    We call λ0 the conjugate partition of λ. That is, for every λ-tableau r, Rt is a Young subgroup of type λ, and Ct is a Young subgroup of type λ0 ...
  66. [66]
    [1312.2569] On Landau's function g(n) - arXiv
    Dec 9, 2013 · Abstract:Let S_n be the symmetric group of n letters; Landau considered the function g(n) defined as the maximal order of an element of S_n.
  67. [67]
    A000793 - OEIS
    Landau's function g(n): largest order of permutation of n elements. Equivalently, largest LCM of partitions of n. (Formerly M0537 N0190)
  68. [68]
    Cyclic Subgroups of the Symmetric Group - MathOverflow
    Nov 11, 2012 · It is clear that every cyclic subgroup will arise this way, by considering the cycle type of a generator.Missing: lengths | Show results with:lengths
  69. [69]
    [PDF] THE EXCEPTIONAL SYMMETRY When we study symmetric groups ...
    Dec 4, 2014 · I am referring to the fact that the outer automorphism group of the symmetric group Symn is trivial unless n = 6 and the outer automorphism ...
  70. [70]
    [PDF] Representation Theory of the Symmetric Group - MIT Mathematics
    Dec 6, 2022 · These permutations satisfy the property of a group: inverse, closure, identity. A concrete example of an element π ∈ S5 is: π = 1 2 3 4 5. 3 4 5 ...
  71. [71]
    [PDF] Representation Theory of Symmetric Groups - Lecture Notes
    The natural permutation of Sn on ∆λ descends to a well-defined action on Ωλ. Definition. Let λ ⊢ n. The λ-Young permutation module Mλ is the Sn-module ...
  72. [72]
    [PDF] REPRESENTATIONS OF THE SYMMETRIC GROUP FROM ...
    Denote V the standard representation. Page 15. 11. Lemma 5.1.2. The standard representation V of Sn is irreducible. Proof. The subspace V is complementary to ...
  73. [73]
    [PDF] irreducible representations of the symmetric group - UChicago Math
    This paper will explore what may be the second most accessible example, the symmetric group. We will begin by establishing the basics of representation theory ...
  74. [74]
    https://link.springer.com/book/10.1007/978-1-4757-6804-1
  75. [75]
    [PDF] 4 Young Tableaux and the Representations of the Symmetric Group
    For instance, the number 4 has five partitions: (4), (3, 1), (2, 2), (2, 1, 1), (1, 1, 1, 1). We can also represent partitions pictorially using Young diagrams ...<|control11|><|separator|>
  76. [76]
    RSK, the Robinson–Schensted–Knuth correspondence
    Oct 10, 2025 · The Robinson–Schensted–Knuth correspondence (RSK), is a bijection between matrices with non-negative integer entries and pairs of semi-standard Young tableaux ...The Robinson–Schensted... · RSK (variant I) · Properties of RSK · Rimhook RSK
  77. [77]
    [PDF] REPRESENTATIONS OF THE SYMMETRIC GROUPS - CERN Indico
    Definition 5.4 (Symmetrizer, Anti-symmetrizer, Irreducible Symmetrizer): The ... The irreducible symmetrizer e will sometimes be called a Young Symmetrizer.
  78. [78]
    [PDF] Hook Lengths and Contents
    Hook length formula. For u ∈ λ, let hu be the hook length at u, i.e. ... Theorem (Frame-Robinson-Thrall). Let λ ` n. Then fλ = n! Qu∈λ hu . f. (4,4,3 ...
  79. [79]
    [PDF] Representations of the symmetric group - Columbia Math Department
    Branching rules: The group Sn naturally contains Sn−1 as a subgroup and in turn is naturally a subgroup of Sn+1. Given λ ` n and the irre- ducible ...
  80. [80]
    [math/0410261] The complex of words and Nakaoka stability - arXiv
    Oct 11, 2004 · We give a new simple proof of the exactness of the complex of injective words and use it to prove Nakaoka's homology stability for symmetric ...
  81. [81]
    The cohomology ring of the colored braid group | Mathematical Notes
    The cohomology ring is obtained for the space of ordered sets of n different points of a plane. Article PDF. Download to read the full article text ...
  82. [82]
    [PDF] Permutations with few inversions - arXiv
    May 16, 2023 · It is easy to see that the inversion table of a permutation is a subdiagonal sequence and that any such sequence is an inversion table, so the ...<|separator|>
  83. [83]
    [PDF] Hyperplane Arrangements, Parking Functions and Tree Inversions
    Jul 15, 1996 · Thus (R) is essentially the inversion table or code of w, as defined in 19, p. ... (R) from regions to parking functions is injective.
  84. [84]
    [PDF] A statistics–respecting bijection between permutation matrices and ...
    Oct 24, 2018 · ... inversion table of a permutation: This table (also called inversion word) gives a (well–known) unique encoding of permutations. The missing ...
  85. [85]
    A000085 - OEIS
    Number of self-inverse permutations on n letters, also known as involutions; number of standard Young tableaux with n cells.
  86. [86]
    [PDF] Matroid Automorphisms and Symmetry Groups - Webbox
    These groups are extremely well studied and of fundamental importance in many areas. The symmetry group of the (n−1)-simplex is just Sn, the symmetric group.
  87. [87]
    Graph Automorphism -- from Wolfram MathWorld
    The automorphism groups of a graph characterize its symmetries, and are therefore very useful in determining certain of its properties. The group of graph ...<|separator|>
  88. [88]
    Root System -- from Wolfram MathWorld
    ### Summary of Root System A_n and Weyl Group
  89. [89]
    [PDF] 8 Groups of Permutations - UC Berkeley math
    S3 is also called the group D3 of symmetries of an equilateral triangle. D3 means the third dihedral group. The nth dihedral group Dn is the group of ...
  90. [90]
    Documentation - Magma Computational Algebra System
    This chapter describes functions available in Magma for computations concerning the non modular representation theory of the symmetric group and the ...Missing: system | Show results with:system
  91. [91]
    (PDF) The Schreier-Sims algorithm - ResearchGate
    Given an arbitrary generating set for a permutation group, the Schreier-Sims algorithm calculates a base and strong generating set. We describe ...
  92. [92]
    SYMMETRICA-MANUAL -- Some basic cycle index formulae
    There exist some basic routines in order to compute the cycle indices of the natural group actions of cyclic, dihedral, alternating and symmetric groups in ...
  93. [93]
    [PDF] Generating Random Permutations
    Mar 10, 2010 · The group Sn of all bijections from the set of n elements to itself is called the symmetric group. A permutation P is an element of Sn. In ...
  94. [94]
    [PDF] The probability of generating the symmetric group when one of the ...
    Theorem 13.​​ In particular, if G has o(n) fixed points then G and σ generate a transitive group with high probability.
  95. [95]
    V3 - ATLAS of Finite Group Representations
    This ATLAS contains information on about 716 groups, including 5215 representations. To find a group, choose its family or use the group lookup facility.