The sum rule from Counting Principles says |A ∪ B| = |A| + |B| when A and B are disjoint. Real problems are rarely that kind. "How many numbers up to 1000 are divisible by 3, 5 or 7?" involves sets that overlap heavily: 15 is divisible by both 3 and 5, so adding the two counts counts it twice.
The Inclusion-Exclusion Principle fixes the overcount systematically: add the sizes of the sets, subtract the pairwise overlaps, add back the triple overlaps, and so on. It gives clean formulas for derangements, onto functions, Euler's totient function and equations with upper bounds, all of which are GATE favourites.
Inclusion-Exclusion: for finite sets A1, …, An, |A1 ∪ … ∪ An| = ∑|Ai| − ∑|Ai ∩ Aj| + ∑|Ai ∩ Aj ∩ Ak| − … + (−1)n+1|A1 ∩ … ∩ An|, where each sum runs over all choices of indices i < j < k ….
Every number in this chapter was confirmed by a program that counts the objects one by one.
Two Sets
|A ∪ B| = |A| + |B| − |A ∩ B|
Why? An element in only A is counted once by |A|. An element in only B is counted once by |B|. An element in both is counted twice by |A| + |B|, so we subtract |A ∩ B| once to fix it.
A B
+--------+-------+--------+
| only A | A ∩ B | only B |
+--------+-------+--------+
|A| + |B| counts the middle region twice.
Example. How many bit strings of length 8 start with 1 or end with 00?
Start with 1: the other 7 bits are free: 27 = 128.
End with 00: the first 6 bits are free: 26 = 64.
Both: first bit and last two bits fixed, 5 free: 25 = 32.
Answer: 128 + 64 − 32 = 160.
Three Sets
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
Check an element that lies in all three sets: it is added 3 times, subtracted 3 times (once for each pair), and added back once. Net: 3 − 3 + 1 = 1. Correct.
Worked example: divisibility
How many integers from 1 to 1000 are divisible by 3, 5 or 7?
Let A, B, C be the multiples of 3, 5, 7. The number of multiples of d up to N is ⌊N/d⌋, and a number is divisible by both 3 and 5 exactly when it is divisible by lcm(3, 5) = 15.
Term | Meaning | Value |
|---|---|---|
|A|, |B|, |C| | ⌊1000/3⌋, ⌊1000/5⌋, ⌊1000/7⌋ | 333 + 200 + 142 = 675 |
Pairs | ⌊1000/15⌋, ⌊1000/21⌋, ⌊1000/35⌋ | 66 + 47 + 28 = 141 |
Triple | ⌊1000/105⌋ | 9 |
|A ∪ B ∪ C| = 675 − 141 + 9 = 543. So 1000 − 543 = 457 numbers are divisible by none of 3, 5, 7.
Worked example: a survey
In a class of 100 students, 45 know C, 40 know Java and 30 know Python. 15 know C and Java, 10 know C and Python, 12 know Java and Python, and 5 know all three.
At least one language: 45 + 40 + 30 − 15 − 10 − 12 + 5 = 83. So 17 know none.
Exactly two languages: each pairwise count includes the 5 who know all three, so (15 − 5) + (10 − 5) + (12 − 5) = 22.
Exactly one language: 83 − 22 − 5 = 56. (Only C: 45 − 15 − 10 + 5 = 25; only Java: 18; only Python: 13; total 56.)
For three sets, a Venn diagram with 7 regions is the safest way to answer "exactly k" questions: fill the centre first, then the pairwise regions, then the single regions.
The General Formula and Its Proof
For n sets the pattern continues: subtract pairs, add triples, subtract quadruples, and so on. The sum over k-fold intersections has C(n, k) terms, so there are 2n − 1 terms in all.
Proof. We show that every element x of the union is counted exactly once on the right-hand side. (An element in none of the sets appears in no term and contributes 0 to both sides.)
Suppose x belongs to exactly m of the sets, with 1 ≤ m ≤ n.
x appears in a k-fold intersection exactly when all k chosen sets are among its m sets. That happens for C(m, k) of the k-fold intersections (and for none if k > m).
So the right-hand side counts x a total of C(m, 1) − C(m, 2) + C(m, 3) − … + (−1)m+1C(m, m) times.
From the binomial theorem in Permutations & Combinations, ∑k=0m (−1)kC(m, k) = (1 − 1)m = 0 for m ≥ 1. Moving the k = 0 term (which is 1) to the other side gives C(m, 1) − C(m, 2) + … + (−1)m+1C(m, m) = 1.
Every element of the union is counted exactly once, so the right-hand side equals |A1 ∪ … ∪ An|. ∎
The complement form (the sieve)
Most applications want the elements with none of the "bad" properties. If all sets live inside a universe U, then by De Morgan's law:
|Ā1 ∩ … ∩ Ān| = |U| − ∑|Ai| + ∑|Ai ∩ Aj| − … + (−1)n|A1 ∩ … ∩ An|
The recipe is always the same: (1) define the bad properties, (2) count the objects having any chosen set of k bad properties (usually this number depends only on k), (3) plug into the alternating sum.
Application 1: Counting Primes (Sieve of Eratosthenes)
A composite number n ≤ 100 has a prime factor ≤ √100 = 10, so it is divisible by 2, 3, 5 or 7. Count the numbers from 1 to 100 divisible by none of them:
Singles: 50 + 33 + 20 + 14 = 117.
Pairs (6, 10, 14, 15, 21, 35): 16 + 10 + 7 + 6 + 4 + 2 = 45.
Triples (30, 42, 70, 105): 3 + 2 + 1 + 0 = 6.
All four (210): 0.
None: 100 − 117 + 45 − 6 + 0 = 22.
These 22 numbers are 1 and the primes from 11 to 97. Remove 1 and add back 2, 3, 5, 7: there are 22 − 1 + 4 = 25 primes up to 100.
Application 2: Euler's Totient Function
φ(n) is the number of integers in {1, 2, …, n} that are coprime to n. If p1, …, pr are the distinct primes dividing n, then φ(n) = n (1 − 1/p1)(1 − 1/p2)…(1 − 1/pr).
Proof. Let Ai be the multiples of pi in {1, …, n}. A number is coprime to n exactly when it is in none of the Ai. Since pi divides n, |Ai| = n/pi exactly, and any intersection of k of them has n/(pipj…) elements. The sieve formula gives
φ(n) = n − ∑ n/pi + ∑ n/(pipj) − … = n (1 − 1/p1)…(1 − 1/pr),
because expanding the product produces exactly these terms with these signs. ∎
Example. 60 = 22 × 3 × 5, so φ(60) = 60 × 1/2 × 2/3 × 4/5 = 16. Similarly φ(100) = 100 × 1/2 × 4/5 = 40 and φ(36) = 36 × 1/2 × 2/3 = 12. The totient function is central to RSA encryption and appears again in Groups.
Application 3: Derangements
A secretary puts n letters into n addressed envelopes at random. In how many ways can no letter reach its correct envelope?
A derangement is a permutation with no fixed point: no element stays in its own position. The number of derangements of n objects is Dn = n! [1 − 1/1! + 1/2! − 1/3! + … + (−1)n/n!].
Derivation. Let Ai be the permutations with element i in its own place (a "bad" property).
Fixing any chosen k elements leaves the other n − k free: (n − k)! permutations.
There are C(n, k) ways to choose which k are fixed.
Sieve: Dn = ∑k=0n (−1)k C(n, k)(n − k)! = ∑k=0n (−1)k n!/k!.
n | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
Dn | 0 | 1 | 2 | 9 | 44 | 265 |
Worked check for n = 4: 24 − 24 + 12 − 4 + 1 = 9. The nine derangements of 1234 are 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321.
The bracket is the start of the series for e−1, so Dn ≈ n!/e. In fact for n ≥ 1, Dn is the integer nearest to n!/e (for n = 6: 720/e ≈ 264.87, so D6 = 265). The chance that a random permutation is a derangement is about 1/e ≈ 0.368, almost independent of n.
Exactly k fixed points. Choose which k stay put, then derange the rest: C(n, k) × Dn−k. With 5 letters, exactly 2 correct: C(5, 2) × D3 = 10 × 2 = 20.
Application 4: Onto Functions
How many functions from a set of m elements onto a set of n elements are there? (Onto, or surjective, means every element of the codomain is hit, as defined in Functions.)
All functions: nm. Bad property Ai: "element i of the codomain is never hit". Functions that miss a chosen set of k codomain elements map into the remaining n − k: (n − k)m of them. Hence:
Number of onto functions from an m-set to an n-set = ∑k=0n (−1)k C(n, k)(n − k)m.
Example. m = 5, n = 3: 35 − 3 × 25 + 3 × 15 − 0 = 243 − 96 + 3 = 150. Interpretation: 5 different tasks given to 3 workers so that each worker gets at least one task.
Link to Stirling numbers. An onto function splits the m elements into n non-empty groups (the preimages) and then labels the groups with the n codomain elements. So onto(m, n) = n! × S(m, n), where S(m, n) is the Stirling number of the second kind from Permutations & Combinations. Here S(5, 3) = 150/6 = 25.
Application 5: Equations with Upper Bounds
How many solutions does x1 + x2 + x3 = 15 have with 0 ≤ xi ≤ 7?
Without upper bounds (stars and bars): C(15 + 2, 2) = C(17, 2) = 136.
Bad property Ai: xi ≥ 8. Substitute xi = yi + 8; the sum becomes 7, giving C(9, 2) = 36 solutions. Three choices of i: 3 × 36 = 108.
Two variables ≥ 8 would need a sum of at least 16 > 15: 0 solutions.
Answer: 136 − 108 + 0 = 28.
This is how questions like "how many 3-digit numbers have digit sum 15?" or "how many ways to roll a sum of 15 with three dice?" are solved.
Checking with Code
The program below implements three inclusion-exclusion formulas and compares each with a brute-force count.
from itertools import combinations, permutations, product
from math import comb, factorial, prod
def count_divisible_by_any(N, divisors):
"""Count 1..N divisible by at least one divisor (pairwise coprime) via inclusion-exclusion."""
total = 0
for k in range(1, len(divisors) + 1):
for group in combinations(divisors, k):
total += (-1) ** (k + 1) * (N // prod(group))
return total
ie = count_divisible_by_any(1000, [3, 5, 7])
brute = sum(1 for x in range(1, 1001) if x % 3 == 0 or x % 5 == 0 or x % 7 == 0)
print("Divisible by 3, 5 or 7:", ie, " brute force:", brute)
def derangements(n):
return sum((-1) ** k * factorial(n) // factorial(k) for k in range(n + 1))
for n in range(1, 7):
brute = sum(1 for p in permutations(range(n)) if all(p[i] != i for i in range(n)))
print(f"D({n}) = {derangements(n):3d} brute force: {brute}")
def onto(m, n):
return sum((-1) ** k * comb(n, k) * (n - k) ** m for k in range(n + 1))
brute = sum(1 for f in product(range(3), repeat=5) if set(f) == {0, 1, 2})
print("Onto functions 5 -> 3:", onto(5, 3), " brute force:", brute)
Output:
Divisible by 3, 5 or 7: 543 brute force: 543
D(1) = 0 brute force: 0
D(2) = 1 brute force: 1
D(3) = 2 brute force: 2
D(4) = 9 brute force: 9
D(5) = 44 brute force: 44
D(6) = 265 brute force: 265
Onto functions 5 -> 3: 150 brute force: 150
The function count_divisible_by_any uses the product of the divisors as the lcm, which is correct only because 3, 5, 7 are pairwise coprime. For divisors like 4 and 6, use lcm(4, 6) = 12, not 24. Note also that the derangement code uses integer arithmetic (n! // k!) instead of the floating-point series, so it stays exact for large n.
Common Mistakes
Wrong signs. The sign of the k-fold intersection term is (−1)k+1 in the union form and (−1)k in the "none" form. Check with a 3-set Venn diagram if unsure.
Using the product instead of the lcm. Numbers divisible by both 4 and 6 are the multiples of 12, not 24.
Confusing "at least one" with "exactly one". For three sets, exactly one = ∑|Ai| − 2∑|Ai ∩ Aj| + 3|A ∩ B ∩ C|.
Forgetting that the pairwise counts include the triple region when computing "exactly two" from survey data.
Stopping too early. Including the intersection terms that turn out to be 0 (like two variables ≥ 8 above) is fine, but you must check they really are 0.
Using nm for onto functions. nm counts all functions; onto functions need the alternating sum. If m < n there are none, and the formula correctly gives 0.
Practice and GATE-Style Questions
Q1. How many integers from 1 to 500 are divisible by 3 or 5 but not by 7?
Divisible by 3 or 5: 166 + 100 − 33 = 233. Among these, divisible by 7 means divisible by 21 or 35: 23 + 14 − ⌊500/105⌋ = 23 + 14 − 4 = 33. Answer: 233 − 33 = 200.
Q2. Find the number of derangements of 6 objects. In how many permutations of 6 objects is at least one object in its original place?
D6 = 720(1 − 1 + 1/2 − 1/6 + 1/24 − 1/120 + 1/720) = 360 − 120 + 30 − 6 + 1 = 265. At least one fixed point: 720 − 265 = 455.
Q3. How many onto functions are there from a 6-element set to a 3-element set?
36 − 3 × 26 + 3 × 16 = 729 − 192 + 3 = 540.
Q4. Compute φ(100) and explain what it counts.
100 = 22 × 52, so φ(100) = 100 × (1 − 1/2)(1 − 1/5) = 40. It is the number of integers from 1 to 100 sharing no common factor with 100, i.e. the odd numbers not ending in 5.
Q5. Prove that for three sets, |A ∪ B ∪ C| ≤ |A| + |B| + |C|, and say when equality holds.
Every element of the union is counted at least once on the right, so the right side is at least the left side. Equality holds exactly when no element is counted twice, that is, when the sets are pairwise disjoint. (This is the union bound, used constantly in probability.)
Q6. How many ways can 4 couples sit in a row of 8 seats so that no couple sits together?
Let Ai be "couple i sits together". Treating k chosen couples as glued blocks gives (8 − k)! × 2k arrangements. So the answer is ∑k=04 (−1)k C(4, k) 2k (8 − k)! = 40320 − 4·2·5040 + 6·4·720 − 4·8·120 + 16·24 = 40320 − 40320 + 17280 − 3840 + 384 = 13824.
Summary
|A ∪ B| = |A| + |B| − |A ∩ B|; for three sets add the singles, subtract the pairs, add the triple.
General form: alternate signs over k-fold intersections. The proof counts an element in m sets: C(m, 1) − C(m, 2) + … = 1.
Sieve form: objects with none of the bad properties = |U| − singles + pairs − ….
Key results: φ(n) = n∏(1 − 1/p); Dn = n!∑(−1)k/k! ≈ n!/e; onto(m, n) = ∑(−1)kC(n, k)(n − k)m = n! S(m, n).
Upper bounds in stars-and-bars problems are removed by counting the violations with inclusion-exclusion.
Overcount, then correct, then correct the correction. Inclusion-exclusion turns messy "none of these" questions into a clean alternating sum.