vi. Burnside, Pólya and Permutation Groups

Counting objects up to symmetry (necklaces, bracelets, coloured cubes and grids, graphs up to isomorphism), and computing with permutation groups (Schreier–Sims order and membership, $k$-th roots of a permutation, permutation encodings). Modular arithmetic from Modular Arithmetic.

Burnside’s lemma. For a finite group $G$ acting on a set $X$,
$|X/G|=\frac{1}{|G|}{\sum }_{g\in G}|X^g|,X^g=\{x:gx=x\}:$
the number of orbits is the average number of fixed points. Fixed points are usually easy to count, orbits are not; that asymmetry is the whole value of the lemma.

Recipe for colourings. (1) Identify the group of symmetries acting on the positions (rotations, reflections, coordinate permutations). (2) Decompose each $g$ into cycles on the positions. (3) A colouring is fixed by $g$ iff it is constant on every cycle, so $|X^g|=k^{c(g)}$. (4) Average. When the group is small (a square’s 8 symmetries, a cube’s 24 rotations), generate it from a few generators and count cycles by brute force: less error-prone than deriving formulas.

Pólya enumeration tracks colour multiplicities: with the cycle index $Z_G=\frac{1}{|G|}{\sum }_g{\prod }_i{x}_i^{c_i(g)}$ ($c_i$ = number of $i$-cycles), substituting $x_i\to {\sum }_j{y}_j^i$ gives a polynomial whose coefficient of ${\prod }_j{y}_j^{m_j}$ counts orbits of colourings using colour $j$ exactly $m_j$ times. Burnside is Pólya with all $y_j=1$; Pólya is needed when the group is complicated (reflections, graph automorphisms) and $c(g)$ must come from each permutation’s structure rather than a simple gcd.

Objects	Group	Order	Count with $k$ colours
necklaces of $n$ beads	rotations $C_n$	$n$	$\frac{1}{n}{\sum }_{d\mid n}\phi (\frac{n}{d})k^d$ (rotation by $s$ has $\gcd (n,s)$ cycles)
bracelets	dihedral $D_n$	$2n$	necklace sum plus $n{k}^{(n+1)/2}$ ($n$ odd) or $\frac{n}{2}(k^{n/2}+k^{n/2+1})$ ($n$ even), over $2n$
necklaces with exactly $m_j$ beads of colour $j$	$C_n$	$n$	$\frac{1}{n}{\sum }_{d\mid \gcd (m)}\phi (d)\left(\genfrac{}{}{0ex}{}{n/d}{m_1/d,\dots }\right)$; two colours: $\frac{1}{n}{\sum }_{d\mid \gcd (a,b)}\phi (d)\left(\genfrac{}{}{0ex}{}{n/d}{a/d}\right)$
aperiodic necklaces = Lyndon words			$\frac{1}{n}{\sum }_{d\mid n}\mu (d)k^{n/d}$ (Lyndon Words)
$n\times n$ grid	rotations $C_4$	4	$\frac{1}{4}(k^{n^2}+k^{\lceil n^2/2\rceil }+2k^{\lceil n^2/4\rceil })$
$n\times n$ grid	$D_4$	8	add $2k^{n\lceil n/2\rceil }+2k^{n(n+1)/2}$ (axis and diagonal mirrors), over 8
cube faces	rotations	24	$\frac{1}{24}(k^6+3k^4+12k^3+8k^2)$
cube vertices	rotations	24	$\frac{1}{24}(k^8+17k^4+6k^2)$
cube edges	rotations	24	$\frac{1}{24}(k^{12}+6k^7+3k^6+8k^4+6k^3)$
graphs on $n$ vertices up to isomorphism	$S_n$ on the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges	$n!$	sum over cycle types (partitions of $n$) below: 1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668

Practical notes. The division by $|G|$ needs $\gcd (|G|,p)=1$ (fine for $10^9+7$ and 998244353 unless $|G|$ is a multiple of the modulus: for $n\ge p$ compute exactly or modulo $p\cdot n$). For cyclic groups sum over divisors, $O(\sqrt{n})$ instead of $O(n)$, which handles $n$ up to $10^{12}$.

mint necklaces(ll n, mint k) {                             // rotations only, O(sqrt n); n invertible mod p
    vector<ll> pr; ll m = n; for (ll p = 2; p * p <= m; p++) if (m % p == 0) { pr.push_back(p); while (m % p == 0) m /= p; } if (m > 1) pr.push_back(m);
    auto phi = [&](ll x) { ll r = x; for (ll p : pr) if (x % p == 0) r = r / p * (p - 1); return r; };
    mint total = 0;
    for (ll d = 1; d * d <= n; d++) if (n % d == 0) {
        total += mint(phi(n / d)) * k.pow(d);
        if (d != n / d) total += mint(phi(d)) * k.pow(n / d);
    }
    return total / mint(n);
}
 
mint bracelets(ll n, mint k) {
    mint refl = n % 2 ? mint(n) * k.pow((n + 1) / 2) : mint(n / 2) * (k.pow(n / 2) + k.pow(n / 2 + 1));
    return (necklaces(n, k) * mint(n) + refl) / mint(2 * n);
}
 
mint necklacesWithCounts(const vector<int>& m, const Comb& cb) {   // colour j used exactly m[j] times, rotations
    int n = 0, g = 0; for (int x : m) n += x, g = std::gcd(g, x);
    if (n == 0) return 1;
    mint total = 0;
    for (int d = 1; d <= g; d++) if (g % d == 0) {
        int ph = d; for (int x = d, p = 2; x > 1; p++) if (x % p == 0) { ph = ph / p * (p - 1); while (x % p == 0) x /= p; }
        mint multi = cb.f[n / d]; for (int x : m) multi *= cb.fi[x / d];
        total += mint(ph) * multi;
    }
    return total / mint(n);
}
 
vector<vector<int>> generateGroup(const vector<vector<int>>& gens) {   // all elements of <gens>, BFS; small groups only
    int n = sz(gens[0]); vector<int> id(n); iota(all(id), 0);
    set<vector<int>> seen = {id}; vector<vector<int>> q = {id};
    for (int h = 0; h < sz(q); h++) for (auto& g : gens) {
        vector<int> c(n); for (int i = 0; i < n; i++) c[i] = g[q[h][i]];
        if (seen.insert(c).second) q.push_back(c);
    }
    return q;
}
 
mint burnside(const vector<vector<int>>& group, mint k) {  // colourings of positions up to the group
    mint total = 0;
    for (auto& g : group) {
        int n = sz(g), c = 0; vector<char> vis(n, 0);
        for (int i = 0; i < n; i++) if (!vis[i]) { c++; for (int j = i; !vis[j]; j = g[j]) vis[j] = 1; }
        total += k.pow(c);
    }
    return total / mint(sz(group));
}
 
mint graphsUpToIsomorphism(int n, const Comb& cb) {        // Polya over cycle types of S_n acting on edges, n <~ 40
    mint total = 0; vector<int> parts;
    function<void(int, int)> rec = [&](int rem, int mx) {
        if (rem == 0) {
            ll c = 0; mint cnt = cb.f[n]; map<int, int> mult;
            for (int i = 0; i < sz(parts); i++) {
                c += parts[i] / 2; mult[parts[i]]++; cnt *= cb.iv[parts[i]];
                for (int j = i + 1; j < sz(parts); j++) c += std::gcd(parts[i], parts[j]);
            }
            for (auto [len, t] : mult) cnt *= cb.fi[t];            // n! / prod(i^{m_i} m_i!) permutations of this type
            total += cnt * mint(2).pow(c);
            return;
        }
        for (int x = min(rem, mx); x >= 1; x--) { parts.push_back(x); rec(rem - x, x); parts.pop_back(); }
    };
    rec(n, n);
    return total * cb.fi[n];
}

Proof: Burnside, Pólya and the formulas

Burnside. Count pairs $(g,x)$ with $gx=x$ in two ways: ${\sum }_g|X^g|={\sum }_x|\mathrm{Stab}(x)|$. By the orbit–stabiliser theorem $|\mathrm{Stab}(x)|=|G|/|Gx|$, so each orbit contributes ${\sum }_{x\in O}\frac{|G|}{|O|}=|G|$, and the total is $|G|$ times the number of orbits. Colourings: $g$ fixes a colouring iff the colour is invariant along each cycle of $g$ on the positions. Pólya: apply Burnside to the colourings with the prescribed multiplicities; a fixed colouring assigns one colour per cycle, a cycle of length $i$ contributes $i$ beads of its colour, so the fixed colourings of $g$ are counted by the coefficient of $\prod y_j^{m_j}$ in ${\prod }_i({\sum }_j{y}_j^i{)}^{c_i(g)}$.

Necklaces. Rotation by $s$ has $\gcd (n,s)$ cycles of length $n/\gcd (n,s)$; the number of $s\in [0,n)$ with $\gcd (n,s)=d$ is $\phi (n/d)$. With prescribed counts, a rotation whose cycles have length $\ell =n/d$ fixes a colouring iff it is periodic with period $d$, which needs $\ell \mid m_j$ for all $j$, and then there are $\left(\genfrac{}{}{0ex}{}{d}{m_1/\ell ,\dots }\right)$ such colourings; there are $\phi (\ell )$ rotations with cycle length $\ell$, giving the formula after renaming $\ell \to d$. Lyndon words: a word of length $n$ has a primitive root of length $d\mid n$, so $k^n={\sum }_{d\mid n}dL(d)$ and Möbius inversion gives $L(n)$. Bracelets: for odd $n$ every reflection fixes one bead and pairs the rest ($\frac{n+1}{2}$ cycles); for even $n$, $\frac{n}{2}$ reflections fix two opposite beads ($\frac{n}{2}+1$ cycles) and $\frac{n}{2}$ fix none ($\frac{n}{2}$ cycles).

Grids and cubes. Quarter turns of an $n\times n$ grid have $\lceil n^2/4\rceil$ cycles (4-cycles plus the centre for odd $n$), the half turn $\lceil n^2/2\rceil$, an axis mirror $n\lceil n/2\rceil$, a diagonal mirror $\frac{n(n+1)}{2}$. The cube’s 24 rotations: identity, 6 face quarter turns, 3 face half turns, 8 vertex turns, 6 edge half turns; counting their cycles on faces, vertices and edges gives the three formulas. All were checked by burnside on groups generated from two rotations.

Graphs. $S_n$ acts on the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ potential edges and a graph is a 2-colouring of them. For a vertex permutation with cycle lengths ${\lambda }_1,\dots$: an edge inside a cycle of length $\ell$ lies in an edge cycle of length $\ell$, except the “diameters” of an even cycle, which have length $\frac{\ell }{2}$, giving $\lfloor \ell /2\rfloor$ edge cycles inside each vertex cycle; edges between cycles of lengths ${\ell }_1,{\ell }_2$ form $\gcd ({\ell }_1,{\ell }_2)$ cycles of length $\mathrm{lcm}$. The number of permutations of cycle type with $m_i$ cycles of length $i$ is $\frac{n!}{{\prod }_i{i}^{m_i}{m}_i!}$. Checked against the known values through $n=10$ and against brute force (canonical forms) for $n\le 6$.

Permutation groups

Operation	Method	Cost
order of $⟨g_1,\dots ,g_m⟩$, membership	Schreier–Sims stabiliser chain	$O(n^5)$-ish (simple incremental version), fine for $n\le 50$
$q$ with $q^k=p$	merge equal-length cycles in groups of $g$ with $\gcd (Lg,k)=g$, interleave with step $k$	$O(n\log n)$
bijection with $[0,n!)$, not lexicographic	Myrvold–Ruskey style swap encoding	$O(n)$
factoradic digits	$x=\sum d_{i}i!$	$O(n)$

Lexicographic rank / unrank: permutationRank / kthPermutation in Counting Fundamentals. Schreier–Sims also solves the Rubik’s Cube group order.

struct PermutationGroup {                                  // Schreier-Sims (incremental, Jerrum-style filter)
    int n; vector<vector<char>> flag; vector<vector<vector<int>>> sigma, gen;   // sigma[k][t]: fixes points > k, maps k to t
    PermutationGroup(int size) : n(size), flag(size, vector<char>(size, 0)), sigma(size, vector<vector<int>>(size)), gen(size) {
        for (int k = 0; k < n; k++) flag[k][k] = 1, sigma[k][k] = identity();
    }
    vector<int> identity() const { vector<int> v(n); iota(all(v), 0); return v; }
    static vector<int> inverse(const vector<int>& v) { vector<int> r(sz(v)); for (int i = 0; i < sz(v); i++) r[v[i]] = i; return r; }
    static vector<int> compose(const vector<int>& a, const vector<int>& b) { vector<int> c(sz(a)); for (int i = 0; i < sz(a); i++) c[i] = a[b[i]]; return c; }   // a after b
    bool check(const vector<int>& cur, int k) const {     // is cur (fixing points > k) in the group?
        if (k <= 0) return true;
        int t = cur[k];
        return flag[k][t] ? check(compose(inverse(sigma[k][t]), cur), k - 1) : false;
    }
    void ins(const vector<int>& cur, int k) {
        if (check(cur, k)) return;
        gen[k].push_back(cur);
        for (int i = 0; i < n; i++) if (flag[k][i]) updateX(compose(cur, sigma[k][i]), k);
    }
    void updateX(const vector<int>& cur, int k) {
        int t = cur[k];
        if (flag[k][t]) ins(compose(inverse(sigma[k][t]), cur), k - 1);
        else { flag[k][t] = 1, sigma[k][t] = cur; for (auto& x : gen[k]) updateX(compose(x, cur), k); }
    }
    void add(const vector<int>& p) { if (n > 0) ins(p, n - 1); }
    __uint128_t order() const {                           // exact for n <= 34 (34! < 2^128)
        __uint128_t tot = 1;
        for (int i = 0; i < n; i++) { int cnt = 0; for (int j = 0; j <= i; j++) cnt += flag[i][j]; tot *= cnt; }
        return tot;
    }
    bool contains(const vector<int>& p) const { return n == 0 || check(p, n - 1); }
};
 
vector<int> permutationRoot(const vector<int>& p, ll k) {  // some q with q^k = p, {} if none
    int n = sz(p); vector<char> seen(n, 0); map<int, vector<vector<int>>> byLen;
    for (int i = 0; i < n; i++) if (!seen[i]) { vector<int> cyc; for (int j = i; !seen[j]; j = p[j]) seen[j] = 1, cyc.push_back(j); byLen[sz(cyc)].push_back(cyc); }
    vector<int> q(n);
    for (auto& [L, cycles] : byLen) {
        int cnt = sz(cycles), g = -1;
        for (int c = 1; c <= cnt; c++) if (cnt % c == 0 && std::gcd((ll)L * c, k) == c) { g = c; break; }
        if (g == -1) return {};
        int N = L * g;
        for (int start = 0; start < cnt; start += g) {
            vector<int> s(N);
            for (int t = 0; t < g; t++) for (int j = 0; j < L; j++) s[(t + (ll)j * k) % N] = cycles[start + t][j];
            for (int i = 0; i < N; i++) q[s[i]] = s[(i + 1) % N];
        }
    }
    return q;
}
 
ull encodePermutation(const vector<int>& b) {             // bijection S_n -> [0, n!), n <= 20
    int n = sz(b); ull a = 0, mul = 1; vector<int> pos(n), el(n); iota(all(pos), 0); iota(all(el), 0);
    for (int i = 0; i < n; i++) {
        int z = pos[b[i]]; a += mul * z; mul *= sz(el);
        swap(pos[el[z]], pos[el.back()]); swap(el[z], el.back()); el.pop_back();
    }
    return a;
}
vector<int> decodePermutation(int n, ull a) {
    vector<int> el(n), b; iota(all(el), 0);
    for (int i = 0; i < n; i++) { int z = a % sz(el); b.push_back(el[z]); a /= sz(el); swap(el[z], el.back()); el.pop_back(); }
    return b;
}
vector<int> toFactoradic(ull x, int n) { vector<int> d(n, 0); for (int i = 1; i <= n; i++) d[n - i] = x % i, x /= i; return d; }   // digit i (from the left) in [0, n - i)
ull fromFactoradic(const vector<int>& d) { int n = sz(d); ull x = 0; for (int i = 0; i < n; i++) x = x * (n - i) + d[i]; return x; }

Proof: Schreier–Sims, permutation roots and the encodings

Schreier–Sims. Let $G_k$ be the subgroup fixing every point $>k$ (so $G_{n-1}=G$, $G_0$ trivial). Level $k$ stores, for each $t$ in the orbit of $k$ under $G_k$, a representative sigma[k][t] $\in G_k$ mapping $k\mapsto t$. check sifts: if $cur\in G_k$ then $cur(k)=t$ must be in the orbit, and ${\sigma }_t^{-1}cur$ fixes $k$ as well, i.e. lies in $G_{k-1}$. ins adds a non-member as a new generator of level $k$ and closes the orbit: updateX extends the orbit with every product of a level-$k$ generator and a known representative, and products that land on a known point produce Schreier generators ${\sigma }_t^{-1}\cdot (\dots )$ of $G_{k-1}$, which are inserted recursively. By Schreier’s lemma these generate the stabiliser, so at the end every level stores a complete transversal of $G_{k-1}$ in $G_k$ and $|G|={\prod }_k|G_k:G_{k-1}|={\prod }_k|{\text{orbit}}_k|$, which order returns; membership is the sift. Checked against BFS closure of random generators for $n\le 7$.

Roots. A cycle of length $m$ of $q$ splits in $q^k$ into $\gcd (m,k)$ cycles of length $\frac{m}{\gcd (m,k)}$ (positions $i,i+k,i+2k,\dots$ modulo $m$). So $p$‘s cycles of length $L$ must come from $q$-cycles of length $Lg$ with $\gcd (Lg,k)=g$, each producing exactly $g$ of them. The condition is $g\mid k$ and $\gcd (L,k/g)=1$, so every valid $g$ is a multiple of $g_0={\prod }_{p\mid L}{p}^{v_p(k)}$, which is valid itself: a root exists iff $g_0$ divides the number of length-$L$ cycles for every $L$, and the smallest valid divisor of the count found by the loop is $g_0$. Interleaving: placing cycle $t$‘s $j$-th element at position $t+jk\mathrm{mod}Lg$ is injective ($g\mid k$ forces $t=t^{\prime }$, then $\gcd (L,k/g)=1$ forces $j=j^{\prime }$), and $q^k$ moves position $t+jk$ to $t+(j+1)k$, i.e. along cycle $t$ of $p$.

Encodings. encodePermutation writes $b$ as the sequence of indices $z_i\in [0,n-i)$ chosen from a shrinking array (swap-with-last removal); this is a mixed-radix number with radices $n,n-1,\dots ,1$, and decodePermutation replays the same removals, so the maps are inverse bijections. Factoradic: every $x<n!$ has a unique representation ${\sum }_i{d}_{i}i!$ with $0\le d_i\le i$ (mixed radix). All verified exhaustively for $n\le 7$.

Related notes

• Lyndon Words
• Arithmetic Functions ($\phi$, $\mu$)
• Rubik’s Cube