Symmetric group ($S_n$)

The permutation group of a three-element set has six elements: the identity, three transpositions, and two three-cycles. A three-cycle and any transposition generate it, with relations $x^3=h^2=e$, $hx{h}^{-1}=x^{-1}$. Its alternating group is the normal cyclic subgroup of order three. It is the unique nonabelian isomorphism type of a group of order six.

The conjugacy classes of the symmetric group on three letters have sizes $1,3,2$: the identity, the three transpositions and the two 3-cycles. A normal subgroup is a union of whole conjugacy classes and contains the identity. Its candidate orders are therefore $1,4,3,6$. Lagrange's theorem excludes four, leaving precisely $\{e\}$, $A_3$ and $S_3$. The order-three subgroup is the cyclic group of the two 3-cycles and the identity; it is also the kernel of a group homomorphism of the sign map.

The first isomorphism theorem gives the corresponding quotients $S_3$, $C_2$ and the trivial group. Thus these are exactly the possible images of surjective group homomorphisms from $S_3$. Each occurs, by the identity map, the sign map and the constant identity map, respectively.

An automorphism preserving the transposition class is inner: commuting relations recover the vertex stars of the complete graph, with a small-case adjustment in degrees three and four. An involution class has the same size as the transposition class only in degree six, when triple transpositions also have size fifteen. Hence outer automorphism groups of symmetric groups are trivial outside degree six and have size at most two in degree six.

// Target: combinatorics.bigb

A permutation of order two is a product of $k$ disjoint transpositions. Its conjugacy class has the displayed size. For $k\ge 2$, equality with the transposition class requires $(n-2)!/(n-2k)!=2^{k-1}k!$. The left side grows strictly with $n$. At $n=2k$, its ratio to the right side is one only for $k=3$; at $k=2$ it jumps from below to above one between $n=4$ and $n=5$, and for $k\ge 4$ it is already greater than one. Thus degree six is the only possible exceptional degree for an group automorphism not preserving transpositions.

A subgroup of the symmetric group of a set, acting faithfully by permutations. A finite permutation group specified by generators can be enumerated by repeatedly multiplying the elements already found by those generators until no new element appears. Its orbits and conjugacy classes can then be computed directly.

The historical study of permutations of letters or quantities and their compositions, closely connected with the development of group theory and the theory of polynomial equations.

A permutation group on a set is oligomorphic when its diagonal action on ordered $n$-tuples has finitely many orbits for every positive integer $n$. For a countable model of a complete theory, an oligomorphic automorphism group makes every finite-arity type space finite: realized types are dense, and only finitely many are possible because types are constant on orbits.

For $n\ge 2$ and $1\le k<n$, an $n$-cycle $c=(12\dots n)$ and $t=(11+k)$ generate $S_n$ exactly when $\gcd (n,k)=1$. Their conjugate transpositions connect labels differing by $k$ modulo $n$. This graph is connected exactly at coprime separation, so transpositions on a connected graph generate the symmetric group. Otherwise residue classes modulo $\gcd (n,k)$ form a nontrivial block system preserved by both generators.

Associate a transposition to each edge of a finite connected graph. For a simple path $v_0,\dots ,v_{\ell }$, let $t_j=(v_{j-1}{v}_j)$. Then $t_1\cdots t_{\ell -1}{t}_{\ell }{t}_{\ell -1}\cdots t_1=(v_0{v}_{\ell })$, using rightmost-first composition. Thus edge transpositions generate every transposition, and hence the full symmetric group.

The parity of a permutation records whether it is a product of an even or odd number of transpositions. It is well-defined and equals the sign of the corresponding permutation matrix.

The sign homomorphism sends an even permutation to $1$ and an odd permutation to $-1$; its kernel is the alternating group.

A symmetric group is the group of all bijections from a set to itself, with function composition as its operation.

A permutation cycle $(a_1{a}_2\dots a_k)$ sends $a_i$ to $a_{i+1}$, sends $a_k$ to $a_1$, and fixes every other element. Its order is $k$.

For $n>1$, every permutation of order of a permutation $n$ in $S_n$ is one full cycle if and only if $n$ is a prime power. If $n=p^r$, all lengths in its disjoint cycle decomposition divide $p^r$, and their least common multiple is their maximum. One cycle therefore has length $n$ and uses every symbol. If $n$ has more than one prime divisor, write $n=ab$ with $a,b>1$ coprime by separating one full prime-power factor from the others. Since $a+b\le ab=n$, disjoint cycles of lengths $a$ and $b$ fit inside $S_n$. Their product has order of a permutation $\mathrm{lcm}(a,b)=n$, but is not a full cycle.

A disjoint cycle decomposition writes a permutation as a product of disjoint permutation cycles. Repeatedly apply the permutation to a point until it returns to that point; these successive points form one cycle. Repeat on points not yet used. Finiteness and injectivity ensure that each process returns to its starting point. This partitions the underlying finite set into cycles. The decomposition is unique up to reordering the cycles, cyclically rotating the entries within each cycle, and optionally omitting fixed-point one-cycles. Include the one-cycles when specifying cycle type.

The cycle type of a permutation is the multiset of lengths in its decomposition into disjoint permutation cycles, including one-cycles for fixed points. Two permutations in the same symmetric group are conjugate exactly when they have the same cycle type.

Conjugation preserves order of a group element, because $(gx{g}^{-1}{)}^k=g{x}^k{g}^{-1}$, and preserves the sign of a permutation, because sign is a group homomorphism into $\{1,-1\}$. These invariants do not determine cycle type. In $S_6$, $(123)$ and $(123)(456)$ both have order three and positive sign, but have three and zero fixed points respectively. Conjugation relabels cycles, so these permutations are not conjugate.

Squaring an odd-length permutation cycle retains its length, whereas an even-length cycle splits into two cycles of half its length. Thus if any even cycle is present, the number of cycles strictly increases, so the cycle type changes. Since conjugate permutations in a symmetric group have the same cycle type, a permutation is conjugate to its square precisely when all its cycle lengths are odd, equivalently when its order of a group element is odd.

Left multiplication of a permutation by a transposition $(ab)$ swaps the two target labels $a,b$. If they occur in different cycles, $(a{x}_1\dots x_p)(b{y}_1\dots y_q)$ becomes the single cycle $(a{x}_1\dots x_{p}b{y}_1\dots y_q)$. If they occur in the same cycle, that formula reverses and splits the cycle in two. All other cycles are unchanged, so the total number of cycles, including fixed points, decreases or increases by exactly one. Empty intermediate lists yield one-cycles and require no exceptional case.

A three-cycle is a permutation cycle of length three. On any chosen set of three letters, the two possible three-cycles are inverses of one another.

Permutation cycles with disjoint supports commute. The order of their product is the least common multiple of their lengths.

The support of a permutation is the set of elements it does not fix. A permutation has finite support when this set is finite.

The sign homomorphism $\mathrm{sgn}:S_n\to \{\pm 1\}$ is the determinant of the corresponding permutation matrix. A transposition has sign $-1$, so this also proves that the parity of any transposition decomposition is well-defined.

An odd permutation has sign $-1$, equivalently it is a product of an odd number of transpositions.

An even permutation has sign $+1$, equivalently it is a product of an even number of transpositions.