Quant Academy Math · Probability · Quant Finance
Phase 19 - Lesson 19.5

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.

⏱ 60 min● Intermediate🔗 Prereqs: 19.1–19.3; comfort with induction
↖ Phase 19 hub
Builds on: 19.3 gives modular inverses, which is how you compute binomials mod \(p\).
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.

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

Intuition
Counting has exactly two honest moves: build a bijection to something you already know how to count, or count with signs to repair deliberate overcounting. Formulas like \(\binom nk\) are just bijections that have been given names. When a count feels hard, the question is never ‘what formula applies?’ but ‘what am I secretly listing, and what am I listing it twice?’

The four basic selections

Select \(k\) from \(n\)Order mattersOrder 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.

Theorem - Pascal’s recurrence
\[\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k},\qquad \binom n0=\binom nn=1.\] (19.8)
Proof
Combinatorial (not algebraic): fix element \(n\). Every \(k\)-subset either contains it - and then the other \(k-1\) elements form a \((k-1)\)-subset of the remaining \(n-1\), giving \(\binom{n-1}{k-1}\) - or it does not, giving \(\binom{n-1}{k}\). The two cases are disjoint and exhaustive. This proof also is the algorithm: it is the DP recurrence for Pascal’s triangle (19.7).

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)\):

\[\binom nk\bmod p \;=\; f[n]\cdot f^{-1}[k]\cdot f^{-1}[n-k]\ \bmod p,\qquad f^{-1}[i-1]=f^{-1}[i]\cdot i \bmod p.\] (19.9)

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

Theorem - Inclusion–exclusion
For finite sets \(A_1,\dots,A_n\),
\[\Big|\bigcup_{i=1}^n A_i\Big|=\sum_{\emptyset\ne S\subseteq[n]}(-1)^{|S|+1}\Big|\bigcap_{i\in S}A_i\Big|.\] (19.10)
Proof
Count the contribution of an element \(x\) lying in exactly \(m\ge1\) of the sets. On the right it is counted once for each nonempty \(S\) among those \(m\) sets, with sign: \(\sum_{j=1}^{m}(-1)^{j+1}\binom mj = 1-\sum_{j=0}^m(-1)^j\binom mj = 1-(1-1)^m=1\) by the binomial theorem. So every element of the union is counted exactly once. □
Worked Example - Two applications
1
(i) Multiples below 1000. How many \(n\lt 1000\) are divisible by 3 or 5? \(|A_3|=\lfloor999/3\rfloor=333\), \(|A_5|=\lfloor999/5\rfloor=199\), \(|A_3\cap A_5|=|A_{15}|=\lfloor999/15\rfloor=66\).
2
By (19.10), \(|A_3\cup A_5|=333+199-66=466\). (Their sum, the classic warm-up, is \(3\cdot\tfrac{333\cdot334}{2}+5\cdot\tfrac{199\cdot200}{2}-15\cdot\tfrac{66\cdot67}{2}=166833+99500-33165=233168\).)
3
(ii) Derangements. Let \(A_i\) be the permutations fixing \(i\). Then \(|\bigcap_{i\in S}A_i|=(n-|S|)!\), and there are \(\binom{n}{j}\) sets \(S\) of size \(j\).
4
So the number of permutations with at least one fixed point is \(\sum_{j\ge1}(-1)^{j+1}\binom nj (n-j)!\), and subtracting from \(n!\): \(D_n=\sum_{j=0}^n(-1)^j\binom nj (n-j)!=n!\sum_{j=0}^n\frac{(-1)^j}{j!}\).
5
Numerically \(D_4=9\), \(D_5=44\), and \(D_n/n!\to e^{-1}\approx0.3679\) - the probability a random permutation has no fixed point converges to \(1/e\).
6
Sanity check \(D_4\): \(4!(1-1+\tfrac12-\tfrac16+\tfrac1{24})=24\cdot\tfrac{9}{24}=9\). ✓

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).

Common Mistakes to Avoid
  • 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.
Quant Practitioner Tips
  • 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

Q1 Medium
How many ways are there to choose 3 scoops from 5 flavours, repetition allowed, order irrelevant?
\(5^3=125\)
\(\binom 53=10\)
\(\binom{5+3-1}{3}=35\)
\(5\cdot4\cdot3=60\)
Q2 Medium
Why can’t you compute \(\binom{n}{k}\bmod p\) by dividing the reduced factorials?
Because factorials are too big
Because division is not an operation in \(\Z/p\Z\); you must multiply by modular inverses
Because \(p\) might not be prime
Because Pascal’s rule forbids it
Q3 Hard
Inclusion–exclusion counts an element lying in exactly \(m\ge1\) of the sets:
m times
Once, because \(\sum_{j\ge1}(-1)^{j+1}\binom mj=1\)
\(2^m\) times
Zero times

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?

▶ Show full solution

(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\).

After the reveal, answer for yourself: In (b) the signed sum and the product formula gave the same answer. Which one generalises to ‘coprime to n’ for a 100-digit n, and why?

Lesson Summary

Counting reduces to bijections and to signed corrections. The four basic selections, Pascal’s recurrence \(\binom nk=\binom{n-1}{k-1}+\binom{n-1}{k}\), and stars and bars cover most direct counts; factorials with Fermat inverses give \(\binom nk\bmod p\) in \(O(1)\) per query. Inclusion–exclusion repairs overcounting with alternating signs, yielding derangements (\(D_n\approx n!/e\)) and, over prime divisors, the totient formula itself.

Retrieval Practice

Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.

▶ Show retrieval prompts & answers
Q: State Pascal’s recurrence and its combinatorial proof in one sentence.
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.
Q: How do you compute \(\binom nk \bmod p\) in \(O(1)\) per query?
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

Confidence / mastery rating
Personal notes

Source References

This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.

← 19.4Next: 19.6 →