Combinatorics: The Principle of Inclusion-Exclusion

Combinatorics

Fundamental Counting Principles

Sum Rule: if A and B are disjoint, $|A \cup B| = |A| + |B|$. Product Rule: sequential choices $k_1, k_2, ...$: $k_1 \cdot k_2 \cdot ...$

Arrangements $A(n, k) = \frac{n!}{(n - k)!}$ (ordered selection of $k$ out of $n$). Combinations $C(n, k) = \frac{n!}{k!(n-k)!}$ (unordered selection).

The binomial theorem: $(a+b)^n = \sum_k C(n, k) a^k b^{n-k}$.

Principle of Inclusion-Exclusion

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

Number of derangements (permutations with no fixed points): $ D(n) = n! \sum_{k=0}^n \frac{(-1)^k}{k!} \approx \frac{n!}{e} $

Euler's totient function $\varphi(n)$: number of $m \leq n$ with $\gcd(m, n) = 1 = n \prod_{p|n} (1 - 1/p)$.

Via inclusion-exclusion: $\varphi(n) = n \cdot (1 - 1/p_1) \cdot (1 - 1/p_2) \cdot ...$

Generating Functions

Ordinary generating function: $f(x) = \sum_n a_n x^n$.

Number of partitions of $n$ into summands from set $S$: coefficient at $x^n$ in $\prod_{s\in S} \frac{1}{1 - x^s}$.

Exponential generating function: $f(x) = \sum_n a_n \frac{x^n}{n!}$ is used for labeled objects.

The method of generating functions transforms combinatorial problems into analysis problems.

Principle of Double Counting and Identities

Many combinatorial identities are proven by double counting—calculating the same quantity in two different ways. Example: $\sum_{k=0}^n C(n,k) = 2^n$. On the left—the sum of combinations. On the right—the number of subsets of an $n$-element set (each element is either included or not: two choices, $2^n$ in total). The Vandermonde identity $C(m+n,r) = \sum_k C(m,k)C(n,r-k)$ is proven by choosing $r$ people from $m$ men and $n$ women.

Pascal’s Identity: $C(n, k) = C(n-1, k-1) + C(n-1, k)$. Meaning: A $k$-element subset of an $n$-element set either contains the distinguished element (choose $k-1$ from $n-1$) or it doesn't (choose $k$ from $n-1$). This is the recurrence for Pascal’s triangle.

The Method of Arrangements with Repetitions and Multisets

Multiset—a collection with repetitions. The number of $k$-element submultisets of an $n$-element set: $C(n+k-1, k)$ = “stars and bars”. Interpretation: distribute $k$ indistinguishable balls into $n$ distinguishable boxes. Example: the number of solutions to $x_1 + x_2 + x_3 = 10$ in non-negative integers = $C(12,2) = 66$.

Multinomial coefficient: $C(n; k_1, k_2, ..., k_m) = \frac{n!}{k_1! k_2! ... k_m!}$—the number of permutations of $n$ elements where $k_i$ elements of $i$-th type. Generalization of Newton's binomial theorem: $(x_1 + ... + x_m)^n = \sum C(n; k_1, ..., k_m)x_1^{k_1}...x_m^{k_m}$.

Principle of Inclusion-Exclusion: Generalization and Applications

The inclusion-exclusion formula gives exact formulas for problems with restrictions. Hatcheck problem, derangement numbers: $D(n) = n! (1 - 1/1! + 1/2! - ... + (-1)^n / n!) \approx n! / e$. As $n \to \infty$: $D(n)/n! \to 1/e \approx 0.368$. Nearly 37% of permutations are derangements.

Problème des rencontres: Cards $1,...,n$ are shuffled, you win if the $i$-th card never appears in the $i$-th position for any $i$. $P(\text{win}) = D(n)/n! \to 1/e$. This problem, posed by Montmort in 1708, was the first historical application of inclusion-exclusion.

In number theory, the Möbius function $\mu(n)$ is an analog of the inclusion-exclusion principle for multiplicative functions: $\sum_{d|n} \mu(d) = [n=1]$. This allows "inverting" sums: if $g(n) = \sum_{d|n} f(d)$, then $f(n) = \sum_{d|n} \mu(d)g(n/d)$—the Möbius inversion formula. It is used for counting primitive polynomials, the number of coprime pairs, etc.

Extremal Combinatorics

Turán’s Theorem: The maximum number of edges in a graph with $n$ vertices and no clique $K_{r+1}$ is the Turán graph $T(n,r)$: $n$ vertices are divided into $r$ equal parts, edges between different parts. Number of edges: $e(T(n,r)) = (1-1/r) \cdot n^2/2$. For $r=2$ (bipartite graph), this is a triangle-free graph.

Zawadzki–Turán Problem: What is the maximum number of edges in an $n$-vertex hypergraph with no complete $k$-partite $k$-hypergraph? Open in most cases.

Szemerédi’s Regularity Lemma (1975): Any sufficiently dense graph can be partitioned into $\varepsilon$-regular pairs. Corollary: contains arithmetic progressions of any length (Szemerédi’s theorem on natural numbers). The regularity lemma has become a main tool in the combinatorics of dense graphs.

Lovász’s Lemma: The Algebraic Geometry Method in Combinatorics

Lovász’s Theorem on the $\theta$-function (1979): Independence number $\alpha(G) \leq \theta(G) \leq \bar{\chi}(G)$—introducing a new parameter computable in polynomial time (SDP). Proof of Shannon’s theorem on the capacity of the pentagon channel. The method of semidefinite programming (SDP) is now standard in theoretical computer science.

Error-Correcting Codes: Constructions

Linear code $[n, k, d]$: $n$—codeword length, $k$—dimension (message size), $d$—minimum Hamming distance. Corrects $\lfloor (d-1)/2 \rfloor$ errors. Hamming bound: the total "ball" of correctable errors $\leq 2^{n-k}$. Cyclic codes: ideals of the ring $\mathbb{Z}_2[x] / (x^n - 1)$. Generator polynomial $g(x)$. BCH codes: determined by roots of $g(x)$ in field extension; corrects at least $t$ errors if $\deg g \geq 2t$. Reed–Solomon codes—a special case of BCH over $\operatorname{GF}(q)$, used in QR codes, CD/DVDs.

Extremal Combinatorics and Hypergroup Testing

Pólya’s Test: test $n$ items for a defect using group tests. If the number of defectives $d$ is small: $O(d \log n)$ adaptive tests (binary search) suffice. Non-adaptive: $O(d^2 \log n / \log d)$ tests (Kautz–Singleton). Applications in genomics (DNA pooling), network diagnostics.

Numerical Example: Principle of Inclusion-Exclusion

Task: How many numbers from $1$ to $120$ are divisible by $2$, $3$, or $5$?

Step 1: $|A_2| = \lfloor 120/2 \rfloor = 60$; $|A_3| = \lfloor 120/3 \rfloor = 40$; $|A_5| = \lfloor 120/5 \rfloor = 24$.

Step 2: Pairwise intersections: $|A_2 \cap A_3| = \lfloor 120/6 \rfloor = 20$; $|A_2 \cap A_5| = \lfloor 120/10 \rfloor = 12$; $|A_3 \cap A_5| = \lfloor 120/15 \rfloor = 8$.

Step 3: Triple intersection: $|A_2 \cap A_3 \cap A_5| = \lfloor 120/30 \rfloor = 4$.

Step 4: PIE: $|A_2 \cup A_3 \cup A_5| = 60 + 40 + 24 - 20 - 12 - 8 + 4 = 88$. Not divisible by any: $120-88=32$. Check via Euler’s function: $\varphi(30) = 30 \cdot (1-1/2) \cdot (1-1/3) \cdot (1-1/5) = 8$ coprime with $30$ in each cycle of $30$. For $4$ cycles: $4 \cdot 8 = 32$ ✓. Derangements $D(n) = n! \sum_{k=0}^n (-1)^k / k!$: $D(4) = 4! \left(1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24}\right) = 24 \cdot \frac{9}{24} = 9$—PIE for permutations with no fixed points.