Lab 10 — Inclusion-Exclusion and Burnside

Goal

Master two combinatorial counting techniques used across competitive programming and discrete math:

Inclusion-Exclusion Principle (PIE) for counting objects satisfying / violating multiple conditions
Burnside’s lemma for counting orbits under group actions (counting distinct configurations modulo symmetry)

Background

Inclusion-Exclusion

For sets A₁, …, Aₙ:

$$|A_1 \cup \cdots \cup A_n| = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - \cdots$$

In counting form, for “objects with property P_i”:

$$\text{count violating none} = \sum_{S \subseteq {1..n}} (-1)^{|S|} \cdot |\text{objects with all properties in S}|$$

Burnside

For a group G acting on a set X, the number of orbits is:

$$|X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|$$

where X^g is the set of elements fixed by g.

Interview Context

Codeforces / ICPC: regular (PIE constantly, Burnside in counting problems with symmetry)
Quant: combinatorial pricing models
Cryptography / coding theory: standard tools
Standard interviews: occasional easy PIE problem (e.g., “count integers ≤ N divisible by none of {2, 3, 5}”)

PIE appears more often than people realize; Burnside is rarer.

When to Skip This Topic

Skip if any of these are true:

You’re not targeting competitive / combinatorics-heavy roles
You haven’t done basic combinatorics (Phase 1–2 foundations)
You have less than 1 week for this lab

PIE is high-leverage even outside competitive — learn it. Burnside is optional.

Problem Statement

Part A — Count Coprime to N

Given integers L ≤ R and N, count integers in [L, R] coprime to N.

Part B — Distinct Necklaces

Given k colors and n beads in a circle, count the number of distinct necklaces (two necklaces are equivalent if one is a rotation of the other).

Constraints

A: 1 ≤ L ≤ R ≤ 10^18, 1 ≤ N ≤ 10^9
B: 1 ≤ n ≤ 10^6, 1 ≤ k ≤ 10^9

Clarifying Questions

Coprime means gcd(x, N) = 1?
Do we include endpoints?

Are reflections considered equivalent (bracelets) or only rotations (necklaces)?
Modulo what prime?

Examples

A

L=1, R=10, N=6  → coprime to 6 are {1, 5, 7}. Wait, in [1,10]: {1, 5, 7}. Answer: 3.

B

n=3, k=2  → 4 distinct necklaces: BBB, BBW, BWW, WWW (BBW and BWB and WBB are all rotations of each other).

Brute Force

A: iterate x in [L, R], check gcd. O(R - L). For R - L = 10^18: TLE.

B: generate all k^n colorings, group by rotation equivalence. O(k^n).

Brute Force Complexity

A: O(R - L)
B: O(k^n)

Both fail for given constraints.

Optimization Path

A (Inclusion-Exclusion)

Let p₁, …, pₘ be the distinct prime divisors of N. Then:

$$\text{coprime}(1..M) = \sum_{S} (-1)^{|S|} \cdot \lfloor M / \prod_{p \in S} p \rfloor$$

Compute for f(M) = count of integers in [1, M] coprime to N. Answer = f(R) - f(L-1).

def count_coprime(M, N):
    primes = prime_divisors(N)
    m = len(primes)
    total = 0
    for mask in range(1 << m):
        prod = 1
        bits = 0
        for i in range(m):
            if mask & (1 << i):
                prod *= primes[i]
                bits += 1
        total += ((-1) ** bits) * (M // prod)
    return total

answer = count_coprime(R, N) - count_coprime(L - 1, N)

Complexity: O(2^m · log N) where m = number of distinct prime factors of N (≤ 9 for N ≤ 10^9).

B (Burnside)

Group G = cyclic group of n rotations. By Burnside:

$$|\text{necklaces}| = \frac{1}{n} \sum_{d=0}^{n-1} k^{\gcd(n, d)}$$

Group by gcd(n, d) = g: the count of d with this gcd is φ(n/g). So:

$$= \frac{1}{n} \sum_{g | n} \varphi(n/g) \cdot k^g$$

Compute φ on divisors of n. O(σ(n)) divisors; per divisor, O(log n) for fast exponentiation. Total: O(d(n) · log n) which is tiny.

A: O(2^m) where m = distinct prime factors ≤ 9 → constant
B: O(σ(n) · log n) → effectively O(√n · log n) since divisors ≤ 2√n

Implementation Requirements

A: efficient prime factorization (trial division up to √N is fine for N ≤ 10^9)
B: divisor enumeration via trial division; Euler totient by formula φ(n) = n · ∏(1 - 1/p)
Modular exponentiation for k^g mod p
Modular inverse for division by n (use Fermat: n^(p-2) mod p)

Tests

A

L=1, R=10, N=6 → 3
L=1, R=N → φ(N) (Euler totient)
L=R, x coprime to N → 1
L=R, x not coprime → 0
Very large R for performance check

B

n=1, k=2 → 2 (B, W)
n=2, k=2 → 3 (BB, BW, WW)
n=3, k=2 → 4
n=4, k=2 → 6
Compare with brute force for n ≤ 6

Follow-up Questions

For A:

Count coprime to multiple Ns simultaneously. → PIE on union of all prime sets.
Count squarefree numbers in [L, R]. → Möbius function = PIE on prime squares.
Sum of φ(i) for i in [1, N]. → Sieve-like O(N log log N) or O(N^{2/3}) with Mertens.

For B:

Bracelets (rotations + reflections). → Group = dihedral D_n. Add reflection terms.
Necklaces with at most k uses of each color. → Multiset Burnside; harder.
Polya enumeration with cycle index polynomial. → Generalizes Burnside; gives generating function.
Distinct binary trees of n nodes. → Catalan numbers; different problem but related counting.

Product Extension

Combinatorial design (DOE, experimental design)
Code generation (counting equivalence classes of programs)
Chemistry (counting molecular isomers — Polya’s original motivation)
Cryptography (group orbits in elliptic curves)

Language/Runtime Follow-ups

Python: big-int arithmetic for free; ideal for PIE/Burnside with modular arithmetic.
C++: modular arithmetic with manual care for overflow; faster execution.
Java: BigInteger for safety; modular arithmetic mature.

Common Bugs

PIE sign wrong: off-by-one in (-1)^|S|.
PIE on factored N: counted prime factors with multiplicity. Only distinct primes matter.
Burnside: forgot to take modular inverse for division by n.
Euler totient computed via brute force gcd: O(n) per value, way too slow.
Modular exponentiation overflow: use pow(k, g, MOD) in Python; manual loop with mod in C++.

Debugging Strategy

Brute force for small parameters; assert PIE/Burnside match
For PIE: print each subset’s contribution; verify signs alternate
For Burnside: enumerate orbits manually for n ≤ 4

Mastery Criteria

Apply PIE to: count divisible/coprime, derangements, surjections, squarefree
Apply Burnside to: necklaces, bracelets, colored cubes
Compute Euler totient in O(√n)
Compute Möbius function (PIE generalized)
State group-action correctness conditions
Identify a “this needs symmetry handling” problem and reach for Burnside

LeetCode Interview — Extreme Coding