Inclusion–exclusion
Adding the sizes of overlapping sets double-counts the overlaps, so you subtract the pairwise intersections — which then removes the triple overlaps once too often, so you add those back. The signs alternate with the size of the intersection, and the same principle counts objects with NONE of a list of properties, which is how derangements are derived.
✓ Unlimited questions · marked criterion by criterion · no card needed
Method: how to approach it
The order below is what examiners expect to see, and each step carries its own marks.
- Define the sets by propertyAᵢ is the set of objects with property i. Getting these definitions precise is most of the work.
- Write the alternating sumSingles minus pairs plus triples minus quadruples, with the k-fold term carrying sign (−1)^(k+1).
- Compute each intersection sizeOften symmetric, so one computation covers all C(n,k) terms of that level.
- Complement for "none of them"Count with none = total − |A₁ ∪ A₂ ∪ …|, which turns the union into an exclusion count.
Worked example
How many integers from 1 to 100 are divisible by 2, 3 or 5?
- Singles: ⌊100/2⌋ = 50, ⌊100/3⌋ = 33, ⌊100/5⌋ = 20. Sum 103.
- Pairs: ⌊100/6⌋ = 16, ⌊100/10⌋ = 10, ⌊100/15⌋ = 6. Sum 32.
- Triple: ⌊100/30⌋ = 3.
- Total: 103 − 32 + 3.
Answer. 74 integers are divisible by at least one of 2, 3 or 5 — so 26 are coprime to 30.
Where marks get dropped
These are the specific errors that cost credit on inclusion–exclusion questions — QED's rubric penalises each of them separately.
- Getting the sign pattern wrong. Triple intersections are ADDED back, and the pattern alternates from there.
- Computing the pairwise intersection with the wrong modulus. Divisible by both 2 and 3 means divisible by lcm(2,3) = 6.
- Forgetting that the principle needs every intersection at every level, not just the ones that look important.
Practise this until it is automatic
Unlimited fresh questions
QED generates new inclusion–exclusion problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.
Marked like an examiner
Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.
Answer in real notation
A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.
Saved to your library
Every question you generate is kept and re-takeable as a timed exam, and your Combinatorics mastery is tracked so you know when this is exam-ready.
Inclusion–exclusion — frequently asked questions
What is the general formula?
|A₁ ∪ … ∪ Aₙ| = Σ|Aᵢ| − Σ|Aᵢ∩Aⱼ| + Σ|Aᵢ∩Aⱼ∩Aₖ| − … with the k-fold terms carrying sign (−1)^(k+1).
How is it used for derangements?
Let Aᵢ be the permutations fixing i. Inclusion–exclusion on the union gives Dₙ = n!Σ(−1)^k/k!, the count of permutations with no fixed point.
Does it work when intersections are empty?
Yes — empty intersections contribute 0, and the formula degenerates to the sum rule for disjoint sets.
The rest of Combinatorics
Counting principles, permutations, combinations. Each subtopic below has its own method, worked example and mark-losing traps.
- 1Sum & product rules
- 2Permutations & combinations
- 3Binomial theorem & Pascal’s triangle
- 4The pigeonhole principle
- 5Inclusion–exclusion
- 6Counting with repetition (stars & bars)
- 7Derangements & counting surjections
- 8Double counting & bijective proofs
- 9Setting up & solving counting recurrences
- 10Generating functions — an introduction
- 11Multinomial coefficients & repeated items
- 12Hockey stick & Vandermonde identities
- 13Catalan numbers & lattice-path counting
Ready to make inclusion–exclusion exam-proof?
Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.
Start practising free →