MethodMath
Ask
Join
HomeTopicsAskAlerts
Profile

© 2026 MethodMath. Built for mathematical knowledge sharing.

AboutContactGuidelinesPrivacyTermsCookies
Isabella Moreno
Apr 15, 2026

How to use the inclusion-exclusion principle for counting problems?

I am studying combinatorics and I understand the basic inclusion-exclusion principle for two sets:

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A \cup B| = |A| + |B| - |A \cap B|∣A∪B∣=∣A∣+∣B∣−∣A∩B∣

But I need help with:

  1. The general formula for nnn sets
  2. A concrete example: How many integers from 1 to 100 are divisible by 2, 3, or 5?
  3. How to handle problems where we want elements that belong to exactly one set (not just at least one)?

I know the general formula involves alternating sums of intersections, but I get confused with the signs.

1 answers368 views

1 Answer

2
Michael Torres
Michael Torres
Apr 15, 2026
Accepted
The inclusion-exclusion principle is a way to count a union without double-counting overlaps. For three sets, the formula is: $$|A \cup B \cup C|=|A|+|B|+|C|-|A \cap B|-|A \cap C|-|B \cap C|+|A \cap B \cap C|.$$ For $n$ sets, the signs alternate: $$\left|\bigcup_{i=1}^{n} A_i\right| =\sum_i |A_i| -\sum_{i<j}|A_i\cap A_j| +\sum_{i<j<k}|A_i\cap A_j\cap A_k| -\cdots.$$ Now count integers from 1 to 100 divisible by 2, 3, or 5. $$|A_2|=50,\quad |A_3|=33,\quad |A_5|=20.$$ The pairwise overlaps are multiples of the least common multiples: \[ \begin{aligned} |A_2\cap A_3|&=\left\lfloor \frac{100}{6}\right\rfloor=16,\\ |A_2\cap A_5|&=\left\lfloor \frac{100}{10}\right\rfloor=10,\\ |A_3\cap A_5|&=\left\lfloor \frac{100}{15}\right\rfloor=6. \end{aligned} \] The triple overlap is: $$|A_2\cap A_3\cap A_5|=\left\lfloor \frac{100}{30}\right\rfloor=3.$$ So the number divisible by at least one of 2, 3, or 5 is: $$50+33+20-16-10-6+3=74.$$ For "exactly one" of the three sets, subtract the pairwise overlaps twice and add the triple overlap three times: $$|A|+|B|+|C|-2(|A\cap B|+|A\cap C|+|B\cap C|)+3|A\cap B\cap C|.$$ Here that gives: $$103-2(32)+3(3)=48.$$ That last formula works because an element in exactly two sets was counted twice at first and must be removed entirely, while an element in all three sets needs its own correction.
Still unsure? Join to comment or ask a follow-up.
Login or Register to post your answer

Suggested questions

Why does 0 factorial equal 1 instead of 0? Simple proof

31.4k

Can someone explain Hilbert's hotel paradox simply?

23.9k

How many squares are actually in an 8 by 8 chessboard?

22.2k

Does the Banach-Steinhaus theorem hold for non-complete normed spaces?

31k

Do I need Calculus 3 before learning Fourier series?

3478