Group Theory Basics

June 2026 · 25 min read

Why Group Theory in CP?

When you first see “group theory” on a competitive-programming roadmap, the reaction is usually skepticism. Contests care about speed and correctness — why bother with abstract algebra?

The short answer: symmetry counting. Every time a problem says “count the distinct necklaces,” “how many essentially different colourings,” or “number of unique states of a Rubik’s cube after k moves,” you are implicitly working inside a group. Burnside’s lemma and Pólya enumeration — the workhorses covered in Parts 1 and 2 of this module — are theorems about group actions. Understanding the underlying group makes those tools far less mysterious.

Beyond counting, groups appear whenever a problem involves:

• Permutation puzzles — Rubik’s cube, 15-puzzle, pancake sorting. The legal moves generate a group; reachability is a question about group membership.
• Repeated operations — applying the same permutation k times (matrix exponentiation on the cycle decomposition).
• Symmetry breaking — deciding which placements are “the same” under rotations or reflections of a grid.

This post gives you just enough group theory to wield those tools with confidence and to recognise group structure in problems that don’t explicitly mention it.

Groups: Definition and Examples

A group is a set G together with a binary operation • (often written multiplicatively) satisfying four axioms:

If the operation is also commutative (a • b = b • a), the group is called abelian.

Example 1 — ℤ_n (integers mod n)

The set {0, 1, …, n − 1} under addition modulo n. The identity is 0, and the inverse of a is n − a. This is an abelian group of order n.

Example 2 — S_n (symmetric group)

The set of all permutations of {1, 2, …, n} under composition. |S_n| = n!. For n ≥ 3 this group is non-abelian: swapping elements 1↔2 then 2↔3 gives a different result than 2↔3 then 1↔2.

Example 3 — Cyclic group C_n

Generated by a single element r with rⁿ = e. Think of the n rotations of a regular n-gon. Every cyclic group of order n is isomorphic to ℤ_n.

Example 4 — Dihedral group D_n

The symmetries of a regular n-gon: n rotations and n reflections, giving |D_n| = 2n. This is the group you use when a problem says “consider rotations and reflections equivalent.”

Cayley table for ℤ₄

Every row and column is a permutation of the elements — this is always true in a group (the Latin square property).

Subgroups and Lagrange’s Theorem

A subgroup H ≤ G is a subset of G that is itself a group under the same operation. Equivalently, H is a subgroup if and only if:

1. H is non-empty.
2. For all a, b ∈ H, the product a • b⁻¹ ∈ H (the one-step subgroup test).

Cosets

Given H ≤ G and an element g ∈ G, the left coset is gH = {g • h : h ∈ H}. The distinct left cosets partition G into equal-sized blocks, each of size |H|.

Why this matters for CP:

• The order of any element divides |G|. So in a permutation group of size m, the order of every permutation divides m.
• If you know |G| and |H|, the number of cosets is immediate — this is exactly the count that appears in Burnside’s lemma.
• Lagrange gives a quick sanity check: if a subgroup’s size doesn’t divide the group’s size, you’ve made an error.

Worked example

In S₃ (|S₃| = 6), the rotations of a triangle form a subgroup C₃ of size 3. Lagrange confirms 3 | 6, and there are 6/3 = 2 cosets — one consisting of the three rotations and one of the three reflections.

Group Actions, Orbits, and Stabilizers

A group action of G on a set X is a function G × X → X, written (g, x) ↦ g · x, satisfying:

1. e · x = x for all x ∈ X  (identity acts trivially).
2. (g • h) · x = g · (h · x) for all g, h ∈ G and x ∈ X  (compatibility).

In CP terms: think of X as the set of configurations (e.g., colourings of a necklace) and G as the set of symmetries (rotations, reflections). The action tells you which configurations are “the same.”

Orbit of an element

The orbit of x ∈ X is the set of all elements reachable from x by applying group elements:

Orb(x) = { g · x : g ∈ G }

Two orbits are either identical or disjoint, so orbits partition X. Each orbit corresponds to one “essentially distinct” configuration.

Stabilizer of an element

The stabilizer of x is the set of group elements that fix x:

Stab(x) = { g ∈ G : g · x = x }

Stab(x) is always a subgroup of G.

Worked example — square colourings

Colour the four corners of a square with two colours. The symmetry group is D₄ with |D₄| = 8 (four rotations + four reflections).

Consider the colouring x = (R, R, B, B) where opposite corners share a colour. The stabilizer consists of the identity and the 180° rotation — so |Stab(x)| = 2. By Orbit-Stabilizer, the orbit of x has size 8/2 = 4. Indeed, the four rotations of this colouring yield four distinct colourings that are all “the same up to symmetry.”

Connection to Burnside’s lemma

Burnside’s lemma counts the number of orbits:

|X / G| = (1 / |G|) ∑_{g ∈ G} |Fix(g)|

where Fix(g) = { x ∈ X : g · x = x }. This is a direct consequence of the Orbit-Stabilizer theorem combined with double counting.

Permutation Groups in CP

Most group-theory problems in CP boil down to permutation groups. A permutation of {0, 1, …, n−1} is stored as a vector p where p[i] is the image of i.

Cycle notation

The permutation [1, 2, 0, 4, 3] sends 0→1, 1→2, 2→0, 3→4, 4→3. In cycle notation: (0 1 2)(3 4). Cycles are disjoint, and the order of the permutation is the LCM of the cycle lengths — here lcm(3, 2) = 6.

Composition

If p and q are permutations, the composition p ∘ q means “apply q first, then p.” In code: r[i] = p[q[i]].

Inverse

The inverse permutation satisfies p⁻¹[p[i]] = i. In code: inv[p[i]] = i.

Applying a permutation k times

To compute p^k, use binary exponentiation on the permutation — exactly like fast power for integers, but replacing multiplication with composition. This runs in O(n log k).

// Compose two permutations: apply q first, then p
vector<int> compose(const vector<int>& p, const vector<int>& q) {
    int n = p.size();
    vector<int> r(n);
    for (int i = 0; i < n; i++)
        r[i] = p[q[i]];
    return r;
}

// Permutation exponentiation via binary lifting
vector<int> perm_pow(vector<int> p, long long k) {
    int n = p.size();
    vector<int> result(n);
    iota(result.begin(), result.end(), 0);  // identity
    while (k > 0) {
        if (k & 1) result = compose(result, p);
        p = compose(p, p);
        k >>= 1;
    }
    return result;
}

Order of a permutation

The order of a permutation is the smallest positive k such that p^k = identity. It equals the LCM of its cycle lengths.

// Cycle decomposition and order of a permutation
long long perm_order(const vector<int>& p) {
    int n = p.size();
    vector<bool> visited(n, false);
    long long order = 1;
    for (int i = 0; i < n; i++) {
        if (visited[i]) continue;
        int cycle_len = 0;
        int j = i;
        while (!visited[j]) {
            visited[j] = true;
            j = p[j];
            cycle_len++;
        }
        order = lcm(order, (long long)cycle_len);
    }
    return order;
}

C++ Toolkit

Below is a self-contained C++ toolkit for permutation-group operations that covers the most common contest needs. All permutations are 0-indexed vectors.

#include <bits/stdc++.h>
using namespace std;

// ---- Permutation basics ----

vector<int> identity(int n) {
    vector<int> id(n);
    iota(id.begin(), id.end(), 0);
    return id;
}

vector<int> compose(const vector<int>& p, const vector<int>& q) {
    int n = p.size();
    vector<int> r(n);
    for (int i = 0; i < n; i++) r[i] = p[q[i]];
    return r;
}

vector<int> inverse(const vector<int>& p) {
    int n = p.size();
    vector<int> inv(n);
    for (int i = 0; i < n; i++) inv[p[i]] = i;
    return inv;
}

vector<int> perm_pow(vector<int> p, long long k) {
    int n = p.size();
    auto result = identity(n);
    while (k > 0) {
        if (k & 1) result = compose(result, p);
        p = compose(p, p);
        k >>= 1;
    }
    return result;
}

// ---- Cycle decomposition ----

vector<vector<int>> cycles(const vector<int>& p) {
    int n = p.size();
    vector<bool> vis(n, false);
    vector<vector<int>> cyc;
    for (int i = 0; i < n; i++) {
        if (vis[i]) continue;
        vector<int> c;
        int j = i;
        while (!vis[j]) {
            vis[j] = true;
            c.push_back(j);
            j = p[j];
        }
        if (c.size() > 1) cyc.push_back(c);  // skip fixed points
    }
    return cyc;
}

long long perm_order(const vector<int>& p) {
    long long ord = 1;
    for (auto& c : cycles(p))
        ord = lcm(ord, (long long)c.size());
    // handle fixed points (cycle length 1, lcm unchanged)
    return ord;
}

// ---- Group generation from generators (BFS) ----

// Given a set of generators, enumerate the entire group.
// Use only when the group is small (|G| <= ~10^6).
vector<vector<int>> generate_group(int n, const vector<vector<int>>& gens) {
    map<vector<int>, bool> seen;
    queue<vector<int>> bfs;
    auto id = identity(n);
    seen[id] = true;
    bfs.push(id);
    vector<vector<int>> group;
    group.push_back(id);
    while (!bfs.empty()) {
        auto cur = bfs.front(); bfs.pop();
        for (auto& g : gens) {
            auto nxt = compose(cur, g);
            if (!seen.count(nxt)) {
                seen[nxt] = true;
                bfs.push(nxt);
                group.push_back(nxt);
            }
        }
    }
    return group;
}

// ---- Count fixed points (for Burnside) ----

// Given a permutation g acting on colourings of n positions with c colours,
// the number of colourings fixed by g is c^(number of cycles of g).
long long count_fixed(const vector<int>& g, int c, long long mod) {
    int n = g.size();
    vector<bool> vis(n, false);
    int num_cycles = 0;
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            num_cycles++;
            int j = i;
            while (!vis[j]) { vis[j] = true; j = g[j]; }
        }
    }
    // compute c^num_cycles mod mod
    long long result = 1;
    long long base = c % mod;
    int exp = num_cycles;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

Usage example — necklace counting

Count distinct necklaces of length n with c colours (rotations only). The group is C_n = {rotation by 0, 1, …, n−1 positions}.

long long count_necklaces(int n, int c, long long mod) {
    // Build the n rotations as permutations
    vector<vector<int>> rotations(n);
    for (int r = 0; r < n; r++) {
        rotations[r].resize(n);
        for (int i = 0; i < n; i++)
            rotations[r][i] = (i + r) % n;
    }

    long long total = 0;
    for (int r = 0; r < n; r++)
        total = (total + count_fixed(rotations[r], c, mod)) % mod;

    // Burnside: answer = total / |G| = total / n
    // Need modular inverse of n
    // (Assuming mod is prime, use Fermat's little theorem)
    auto mod_pow = [&](long long b, long long e, long long m) {
        long long r = 1; b %= m;
        while (e > 0) { if (e & 1) r = r * b % m; b = b * b % m; e >>= 1; }
        return r;
    };
    long long inv_n = mod_pow(n, mod - 2, mod);
    return total % mod * inv_n % mod;
}

CP Applications

Application 1 — Rubik’s cube reachability

Each face turn of a Rubik’s cube is a permutation of 48 facets (ignoring centres). The set of all reachable states forms a group generated by six face turns. While the full group has ≈4.3 × 10¹⁹ elements, contest problems typically work with restricted subgroups (e.g., only two generators) or ask for the order of a specific move sequence.

Strategy: Represent the state as a permutation, compose move sequences, and use cycle decomposition to find the order (minimum number of repetitions to return to the solved state).

Application 2 — grid symmetry counting

Problem: count the distinct ways to place k identical pieces on an m × n grid, where two placements are the same if one can be obtained from the other by rotation/reflection.

Strategy:

1. Identify the symmetry group G acting on the grid cells. For a square grid: D₄ (8 elements). For a rectangular grid: the Klein four-group V₄ (4 elements: identity, 180° rotation, horizontal flip, vertical flip).
2. Each group element induces a permutation of the m × n cells.
3. Apply Burnside: for each symmetry, count how many placements of k pieces are fixed. A placement is fixed by a symmetry if and only if the set of occupied cells is invariant under that permutation.

Application 3 — recognising group structure

Not every group-theory problem says “group” in the statement. Look for these patterns:

Classic contest problem: repeated shuffle

Given an array of n elements and a shuffle pattern (a permutation), find the array after k applications of the shuffle where k can be up to 10¹⁸.

Solution: Store the shuffle as a permutation p. Compute p^k using binary exponentiation. Apply the resulting permutation to the original array. Total time: O(n log k).

// Apply permutation to array: result[i] = arr[perm[i]]
template <typename T>
vector<T> apply_perm(const vector<int>& perm, const vector<T>& arr) {
    int n = perm.size();
    vector<T> result(n);
    for (int i = 0; i < n; i++)
        result[i] = arr[perm[i]];
    return result;
}

void solve() {
    int n; long long k;
    cin >> n >> k;

    vector<int> arr(n), perm(n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    for (int i = 0; i < n; i++) { cin >> perm[i]; perm[i]--; } // 0-indexed

    auto pk = perm_pow(perm, k);
    auto result = apply_perm(pk, arr);

    for (int i = 0; i < n; i++)
        cout << result[i] << " \n"[i == n - 1];
}

Summary

What to remember for contests:

1. “Up to symmetry” ⇒ identify the group ⇒ Burnside / Pólya.
2. Permutation × k times ⇒ cycle decomposition + binary exponentiation.
3. Reachability in a puzzle ⇒ BFS on the group generated by the legal moves.
4. Always double-check whether a permutation means “where i goes” or “where i comes from.”
5. Overflow from LCM of cycle lengths is a classic trap — plan your integer type.

Next up: Permanent of a Matrix, where we connect permutation sums to a harder counting problem.