Mathwords logoMathwords

Permutation Group — Definition, Formula & Examples

A permutation group is a set of permutations of some collection of objects that forms a group under the operation of composition. Every element rearranges the objects, and combining any two rearrangements (or undoing one) always yields another rearrangement in the same set.

A permutation group is a subgroup of the symmetric group SnS_n. Precisely, given a set XX with ∣X∣=n|X| = n, a permutation group on XX is a set GG of bijections σ:X→X\sigma : X \to X that is closed under composition, contains the identity map, and contains the inverse of each of its elements.

How It Works

You build a permutation group by identifying a collection of bijections on a set that satisfies the group axioms: closure, associativity, identity, and inverses. In practice, you often start with one or two generating permutations and then compose them repeatedly (including inverses) until no new permutations appear. The resulting closure is your permutation group. Cayley's theorem guarantees that every finite group is isomorphic to some permutation group, so studying permutation groups is equivalent to studying all finite groups.

Worked Example

Problem: List all elements of the permutation group on {1,2,3}\{1, 2, 3\} generated by the cycle (1 2 3)(1\ 2\ 3).
Generator: Let σ=(1 2 3)\sigma = (1\ 2\ 3), which sends 1↦21 \mapsto 2, 2↦32 \mapsto 3, 3↦13 \mapsto 1.
σ=(1 2 3)\sigma = (1\ 2\ 3)
Compose with itself: Compute σ2=σ∘σ\sigma^2 = \sigma \circ \sigma. Applying σ\sigma twice: 1↦2↦31 \mapsto 2 \mapsto 3, 2↦3↦12 \mapsto 3 \mapsto 1, 3↦1↦23 \mapsto 1 \mapsto 2.
σ2=(1 3 2)\sigma^2 = (1\ 3\ 2)
One more composition: Compute σ3=σ2∘σ\sigma^3 = \sigma^2 \circ \sigma. Every element maps back to itself.
σ3=e=(identity)\sigma^3 = e = \text{(identity)}
Answer: The generated group is ⟨(1 2 3)⟩={e,  (1 2 3),  (1 3 2)}\langle (1\ 2\ 3) \rangle = \{ e,\; (1\ 2\ 3),\; (1\ 3\ 2) \}, a cyclic group of order 3. It is a subgroup of S3S_3.

Why It Matters

Permutation groups appear throughout abstract algebra, combinatorics, and physics. Burnside's lemma uses them to count distinct colorings and configurations under symmetry. In cryptography and coding theory, analyzing permutation groups helps design and break ciphers.

Common Mistakes

Mistake: Confusing a permutation group with the full symmetric group SnS_n.
Correction: Every permutation group is a subgroup of some SnS_n, but it need not contain all n!n! permutations. For example, the group generated by (1 2 3)(1\ 2\ 3) has only 3 elements, while S3S_3 has 6.