Combinatorics: Counting, Binomials, and Inclusion–Exclusion
Bijections, the twelvefold basics, Pascal’s recurrence, binomials mod a prime, and inclusion–exclusion as the counting analogue of a signed sum.
Leads to: 19.6 turns counts into generating functions; 19.7 counts with DP; 19.11 counts partitions. The Euler Lab’s Combinatorics path drills every identity here.
Learning Objectives
Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.
- Derive the counts for ordered/unordered selection with and without repetition, and state the bijection each rests on.
- Prove Pascal’s recurrence combinatorially and use it to build a binomial table in \(O(n^2)\).
- Compute \(\binom{n}{k}\bmod p\) in \(O(1)\) after an \(O(n)\) factorial precomputation.
- State and prove inclusion–exclusion and apply it to derangements and to counting multiples.
- Implement exact and modular binomial coefficients and validate them against a Pascal table.
Key Vocabulary
- Bijection principle
- Two finite sets have the same size iff a bijection exists between them. Every clean counting proof is secretly a bijection.
- Binomial coefficient
- \(\binom nk=\frac{n!}{k!(n-k)!}\): the number of \(k\)-subsets of an \(n\)-set; also the coefficient of \(x^k\) in \((1+x)^n\).
- Stars and bars
- The number of ways to write \(n\) as an ordered sum of \(k\) non-negative integers is \(\binom{n+k-1}{k-1}\).
- Inclusion–exclusion
- | union | = sum of sizes − pairwise intersections + triple intersections − …; the signed correction for overcounting.
- Derangement
- A permutation with no fixed point; \(D_n=n!\sum_{k=0}^n(-1)^k/k!\approx n!/e\).
- Multinomial coefficient
- \(\binom{n}{k_1,\dots,k_r}=\frac{n!}{k_1!\cdots k_r!}\): arrangements of a multiset; the count of ways to split \(n\) labelled items into labelled groups of given sizes.
Intuition & Motivation
The four basic selections
| Select \(k\) from \(n\) | Order matters | Order does not |
|---|---|---|
| No repetition | \(n^{\underline{k}}=\frac{n!}{(n-k)!}\) | \(\binom nk=\frac{n!}{k!(n-k)!}\) |
| With repetition | \(n^k\) | \(\binom{n+k-1}{k}\) (stars and bars) |
Each entry is a bijection. \(n^k\) counts functions \([k]\to[n]\). \(\binom nk\) divides the ordered count by the \(k!\) orders of each chosen set - a \(k!\)-to-1 map, so the fibres have constant size and division is legitimate. Stars and bars maps a multiset of size \(k\) to a binary string of \(k\) stars and \(n-1\) bars; the bijection is what makes the formula obvious rather than magic.
Binomials modulo a prime
Direct division fails mod \(p\) (there is no division), so use inverses. Precompute \(f[i]=i!\bmod p\) for \(i\le n\), then a single modpow gives \(f^{-1}[n]=(n!)^{-1}\) by Fermat, and a backward pass gives all the other inverse factorials in \(O(n)\):
Total cost: \(O(n)\) precomputation, \(O(1)\) per query. This is the standard rig for any problem that asks for a huge count mod \(10^9+7\).
Inclusion–exclusion
Coding workbench
Lattice-path counting (\(\binom{2n}{n}\) routes across an \(n\times n\) grid), digit-arrangement counts, and ‘how many numbers below \(N\) avoid property X’ questions dominate the Euler Lab’s Combinatorics path. Nearly all of them are a bijection plus (19.8), (19.9) or (19.10).
- Computing \(\binom nk\) as factorial(n)//(factorial(k)*factorial(n-k)) for \(n\sim10^6\): you build a multi-million-digit integer to get a modest answer. Use the multiplicative loop.
- Dividing mod \(p\). \(\binom nk \bmod p\) is NOT \((n!\bmod p)/(k!\bmod p)\) - multiply by inverses (19.9).
- Applying stars and bars when the parts must be positive: then the count is \(\binom{n-1}{k-1}\), not \(\binom{n+k-1}{k-1}\). Substitute \(x_i=y_i+1\) to see why.
- Using inclusion–exclusion with \(n\) large: the sum has \(2^n-1\) terms. Above \(n\approx25\) you need structure (multiplicativity, Möbius, DP) instead.
- Confusing ‘at least one’ with ‘exactly one’ - the signed sum (19.10) computes the union (at least one). Exactly-\(m\) needs the Bonferroni/sieve form with \(\binom{j}{m}\) weights.
- Symmetry \(\binom nk=\binom n{n-k}\) halves your loop and, in fixed-width languages, halves your overflow risk.
- Prefer a bijection proof to an algebraic one: it usually hands you the algorithm for free (Pascal’s proof IS the DP).
- Inclusion–exclusion over prime divisors of \(n\) is exactly the totient formula \(\varphi(n)=n\prod(1-1/p)\) - and over squarefree divisors it is the Möbius function. They are the same theorem wearing different clothes.
- Durrett’s treatment of the matching problem is the probabilistic face of derangements: \(\Prob(\text{no fixed point})\to e^{-1}\).
Practice this in the Euler Lab
Computational problems that exercise exactly this technique. Each opens in the Euler Lab with a Python workbench, a progressive hint ladder, and answer checking. Tier A/B run at full scale in the browser.
Warm-up:
#9 Special Pythagorean Triplet (1%, tier A) #49 Prime Permutations (3%, tier A) #53 Combinatoric Selections (3%, tier A) #29 Distinct Powers (5%, tier A)
Applied:
#336 Maximix Arrangements (16%, tier B) #265 Binary Circles (17%, tier B) #345 Matrix Sum (17%, tier B)
Challenge:
#161 Triominoes (41%, tier C) #182 RSA Encryption (41%, tier C)
222 Project Euler problems in total are mapped to this lesson. Open the Euler Lab to filter them all.
Knowledge Check
Practical Exercise
(a) Prove the hockey-stick identity \(\sum_{i=k}^{n}\binom ik=\binom{n+1}{k+1}\) both by induction and by a bijection. (b) Use inclusion–exclusion to count the integers in \([1,10^6]\) coprime to 30, and check it against \(\varphi\)-style reasoning. (c) How many distinct arrangements are there of the letters of MISSISSIPPI?
(a) Induction on \(n\). Base \(n=k\): \(\binom kk=1=\binom{k+1}{k+1}\). Step: \(\sum_{i=k}^{n+1}\binom ik=\binom{n+1}{k+1}+\binom{n+1}{k}=\binom{n+2}{k+1}\) by Pascal (19.8). Bijection. Count the \((k+1)\)-subsets of \(\{1,\dots,n+1\}\) by their LARGEST element. If the largest is \(i+1\), the remaining \(k\) elements form a \(k\)-subset of \(\{1,\dots,i\}\): \(\binom ik\) of them. Summing over \(i=k..n\) gives the identity, and the classes are disjoint and exhaustive.
(b) \(30=2\cdot3\cdot5\). Let \(A_p\) be the multiples of \(p\) in \([1,N]\), \(N=10^6\). \(|A_2|=500000,\ |A_3|=333333,\ |A_5|=200000\); \(|A_6|=166666,\ |A_{10}|=100000,\ |A_{15}|=66666\); \(|A_{30}|=33333\). Union \(=1033333-333332+33333=733334\)... carefully: \((500000+333333+200000)-(166666+100000+66666)+33333=1033333-333332+33333=733334\). Coprime count \(=10^6-733334=266666\).
Cross-check: the density of integers coprime to 30 is \(\prod_{p\mid30}(1-1/p)=\tfrac12\cdot\tfrac23\cdot\tfrac45=\tfrac{4}{15}\), and \(10^6\cdot4/15=266666.67\); since \(10^6=33333\cdot30+10\), the exact count is \(33333\cdot8+|\{1,7\}\text{ among the last }10|=266664+2=266666\). ✓ The two methods agree - inclusion–exclusion over the prime divisors IS the totient product.
(c) MISSISSIPPI has 11 letters: M×1, I×4, S×4, P×2. The multinomial count is \(\frac{11!}{1!\,4!\,4!\,2!}=\frac{39916800}{1\cdot24\cdot24\cdot2}=\frac{39916800}{1152}=34650\).
Lesson Summary
Retrieval Practice
Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.
A: \(\binom nk=\binom{n-1}{k-1}+\binom{n-1}{k}\): split the \(k\)-subsets according to whether they contain a fixed distinguished element.
A: Precompute \(i!\bmod p\) for all \(i\le n\); invert \(n!\) once by Fermat (\((n!)^{p-2}\)); walk the inverse factorials backwards with \(f^{-1}[i-1]=f^{-1}[i]\cdot i\). Then multiply three table entries.
Completion Checklist
- I can explain the core ideas in my own words
- I worked the derivations/examples by hand
- I completed the interactive workbench(es)
- I passed the knowledge check