Symmetric group ($S_n$)

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$.

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.

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.