Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Inclusion–exclusion principle

Inclusion–exclusion counts elements in unions of overlapping sets by alternately adding and subtracting sizes of intersections; used in counting, probability, derangements and avoiding double-counting in engineering problems.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

In engineering (networks, reliability, resource allocation) we often must count how many items satisfy at least one of several properties while those properties overlap. The inclusion–exclusion principle gives an exact way to count such elements without double-counting. It also appears in probability, combinatorics (e.g. derangements), and algorithm analysis.

Key ideas

  • Cardinality: for a set A, |A| denotes the number of elements in A (also called the size of A). Cardinality is a non-negative integer; unit: elements (dimensionless count).
  • Union: A ∪ B is the set of elements that are in A or B or both. Defined for any number of sets.
  • Intersection: A ∩ B is the set of elements common to both A and B.
  • Complement: A^c = U \ A, elements of the universe not in A.
  • Disjoint: two sets are disjoint if their intersection is empty, i.e. A ∩ B = ∅.
  • Binomial coefficient: C(n, k) denotes the number of k-element subsets of an n-element set; C(n, k) = n! / (k!(n−k)!), for integers 0 ≤ k ≤ n.

Definition (Inclusion–exclusion for two sets). For finite sets A and B, |A ∪ B| = |A| + |B| − |A ∩ B|. This corrects the double counting of elements in both A and B.

Definition (Inclusion–exclusion for three sets). For finite sets A, B, C, |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

General principle (n sets). For finite sets A1, A2, …, An, |⋃{i=1}^n A_i| = sum{k=1}^n ((−1)^{k+1} · (sum of sizes of all k-fold intersections)). Equivalently, |⋃{i=1}^n A_i| = Σ{i} |A_i| − Σ_{i<j} |A_i ∩ A_j| + Σ_{i<j<k} |A_i ∩ A_j ∩ A_k| − ⋯ + (−1)^{n+1} |A_1 ∩ ⋯ ∩ A_n|.

Assumptions: all sets are finite (cardinalities exist), or a finitely additive measure is used in place of cardinality.

Derivation (combinatorial counting argument). Fix an element x in U. Suppose x belongs to exactly k of the sets among A1,…,An. How many times is x counted on the right-hand side? It appears in each single set count k times; in each pairwise-intersection term it appears C(k,2) times and is subtracted; in each triple intersection it appears C(k,3) times and is added; and so on. The total multiplicity M(k) equals Σ_{i=1}^k (−1)^{i+1} C(k,i). Using the binomial identity Σ_{i=0}^k (−1)^i C(k,i) = 0 for k≥1, we get M(k) = 1 for k≥1. For k=0 (element in none of the sets) it is counted 0 times. Thus each element that lies in at least one set is counted exactly once; summing over elements yields the formula.

Alternate derivation (indicator functions). For each element x define indicator I_j(x)=1 if x∈A_j, else 0. Then the indicator of the union I_union(x) = 1 if Σ_j I_j(x) ≥ 1. Expanding the polynomial Σ_j I_j(x) − Σ_{i<j} I_i(x)I_j(x) + Σ_{i<j<k} I_i I_j I_k − ⋯ yields 1 exactly when any I_j(x)=1 and 0 otherwise. Summing over x gives the inclusion–exclusion count.

Diagram to draw for exam answers: draw a rectangle labeled U (universe). Inside it draw three overlapping circles labelled A, B, C so that all pairwise and the central triple-overlap exist. Number the seven non-empty regions as R1..R7: (A only), (B only), (C only), (A∩B only), (A∩C only), (B∩C only), (A∩B∩C). Label each region with its symbolic description (for example region for A∩B∩C write A∩B∩C). Use this diagram to show how terms add and subtract to count every region exactly once.

Remarks: inclusion–exclusion extends to counts of functions (e.g. derangements) and to probabilities by replacing |·| with P(·).

Formulas

|A ∪ B| = |A| + |B| − |A ∩ B| — |A|, |B|, |A ∩ B| are counts (elements); unit: elements; applies to any two finite sets A,B.

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C| — all symbols are cardinalities; applies to three finite sets.

|⋃_{i=1}^n A_i| = Σ_{k=1}^n ((−1)^{k+1} · Σ_{1≤i_1<…<i_k≤n} |A_{i_1} ∩ … ∩ A_{i_k}|) — each term a count; applies to n finite sets.

Number of derangements of n objects: !n = n! · Σ_{k=0}^n ((−1)^k / k!) — !n is count of permutations with no fixed point; unit: permutations (count); applies for integer n≥0. Number of onto functions (surjections) from an m-element set to an n-element set: S(m → n) = Σ_{k=0}^n (−1)^k · C(n, k) · (n − k)^m — valid for integers m ≥ n ≥ 1 (and 0 when m < n); unit: functions (count). (Equivalently, S(m → n) = n! · S(m, n), where S(m, n) is a Stirling number of the second kind.)

P(⋃_{i=1}^n E_i) = Σ P(E_i) − Σ P(E_i ∩ E_j) + Σ P(E_i ∩ E_j ∩ E_k) − … — probabilities replace cardinalities; applies when probabilities of intersections are known.

Worked examples

Example 1 — two-set basic (university short question) Question: In a class of 100 students, 40 know C, 30 know D, and 10 know both. How many students know at least one of C or D? Solution steps:

  1. Let A = students who know C, B = students who know D. Given |A|=40, |B|=30, |A ∩ B|=10, universe size 100.
  2. Use formula |A ∪ B| = |A| + |B| − |A ∩ B|.
  3. Substitute: |A ∪ B| = 40 + 30 − 10 = 60. Answer: 60 students know at least one of C or D.

Example 2 — three sets: numbers 1..100 divisible by 2,3 or 5 (typical exam) Question: Count integers from 1 to 100 divisible by 2 or 3 or 5. Solution steps:

  1. Let A = divisible by 2, B = divisible by 3, C = divisible by 5. We need |A ∪ B ∪ C|.
  2. Compute single counts: |A|=⌊100/2⌋=50, |B|=⌊100/3⌋=33, |C|=⌊100/5⌋=20.
  3. Pairwise intersections: divisible by lcm(2,3)=6 ⇒ |A∩B|=⌊100/6⌋=16; lcm(2,5)=10 ⇒ |A∩C|=10; lcm(3,5)=15 ⇒ |B∩C|=6.
  4. Triple intersection: lcm(2,3,5)=30 ⇒ |A∩B∩C|=⌊100/30⌋=3.
  5. Apply inclusion–exclusion: |A ∪ B ∪ C| = 50 + 33 + 20 − (16 + 10 + 6) + 3 = 103 − 32 + 3 = 74. Answer: 74 integers.

Example 3 — derangements (longer model answer) Question: How many permutations of 5 distinct books have none in its original position? Solution steps:

  1. Let n=5. A derangement has no fixed points. Use inclusion–exclusion on positions: count permutations that fix at least one book and subtract from total.
  2. Formula: !n = n! − C(n,1)(n−1)! + C(n,2)(n−2)! − C(n,3)(n−3)! + C(n,4)(n−4)! − C(n,5)(n−5)!.
  3. For n=5: !5 = 5! − C(5,1)4! + C(5,2)3! − C(5,3)2! + C(5,4)1! − C(5,5)0!.
  4. Compute: 5!=120; C(5,1)4!=5·24=120; C(5,2)3!=10·6=60; C(5,3)2!=10·2=20; C(5,4)1!=5·1=5; C(5,5)0!=1·1=1.
  5. Sum with alternating signs: 120 − 120 + 60 − 20 + 5 − 1 = 44. Answer: 44 derangements.

Common mistakes

  • For three sets, subtracting only the triple intersection instead of adding it back (wrong sign for the triple term).
  • Treating events as disjoint when they are not; always check intersections explicitly.
  • In derangement problems, mixing up inclusion–exclusion with simpler factorial manipulations and giving non-integer results when not simplified correctly.
  • When applying to probabilities, forgetting that probabilities of intersections must be used (not products unless independence is known).

For your exam

Typical question types:

  • Definitions and statement of the inclusion–exclusion principle (two-set, three-set, general n-set).
  • Short proofs: derive the two-set or three-set formula, or prove the general formula by induction or indicator functions.
  • Numerical problems: compute union size given counts and intersection sizes (like divisibility problems, survey problems).
  • Combinatorial applications: derangements, counting surjections, counting onto functions, or counting arrangements avoiding forbidden positions.
  • Probability applications: compute P(⋃ E_i) given probabilities of intersections.

What to include for full marks:

  • Clear definitions of terms used (union, intersection, cardinality, universe).
  • Correct formula quoted and conditions stated (finite sets).
  • For derivation questions: show the combinatorial argument for why each element is counted exactly once or supply a correct indicator-function derivation.
  • For applied problems: list sets clearly, compute single counts, pairwise, triple counts, then apply formula with correct signs. Show intermediate arithmetic.
  • If a diagram helps, draw the Venn diagram rectangle and circles, label regions and show how terms cover them.

Quick check

  1. For finite sets A and B, express |A ∪ B| in terms of |A|, |B| and |A ∩ B|.
  2. How many integers from 1..60 are divisible by 2 or 3? (Use inclusion–exclusion.)
  3. What is !4 (number of derangements of 4 objects)? Answers: 1. |A ∪ B| = |A| + |B| − |A ∩ B|. 2. |A|=30, |B|=20, |A∩B|=10 ⇒ 30+20−10 = 40. 3. !4 = 9.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?