Inclusion-Exclusion Principle

Q: What happens when the sets do not overlap?

Then $|A \cap B| = 0$, the overlap is empty, and the formula reduces to $|A| + |B|$, the ordinary sum. For example, a chess club of 30 and a choir of 25 with no shared members gives 55 people in total.

In one sentence: Inclusion-exclusion counts how many items belong to at least one group by adding the groups and then removing the overlaps that were counted twice.

$|A \cup B| = |A| + |B| - |A \cap B|$

Read it out loud: “The size of A union B equals the size of A, plus the size of B, minus the size of A intersect B. The vertical bars mean count how many items are in the set. The union sign means either set or both, and the intersection sign means the items that are in both sets.”

Before you start

The ideas and signs this page uses, explained from zero. For powers of ten, Greek letters and other notation in general, see Math basics.

Sets and their members: A set is a collection of items, such as the members of a chess club. Each item in a set is called a member or an element, and each member is counted once. The capital letters $A$ and $B$ are names for sets. If a chess club has 30 members, then set $A$ has 30 members.
Vertical bars, $|A|$: $|A|$ is read ‘the size of A’, and it means the number of items in set $A$ . For a club with 30 members, $|A| = 30$ . In this formula the bars mean count, not absolute value, which is a different use of the same symbol that you may see elsewhere.
Union $\cup$ and intersection $\cap$: $A \cup B$ , the union, holds every item that is in $A$ or in $B$ , or in both. It means ‘or’. $A \cap B$ , the intersection, holds only the items that are in both $A$ and $B$ . It means ‘and’. The union is the total of the two groups, and the intersection is their shared part.
Venn diagrams: A Venn diagram draws each set as a circle. Two overlapping circles labeled $A$ and $B$ have three regions: items inside only $A$ , items inside only $B$ , and items in the shared overlap. Items outside both circles are in neither set. Drawing a Venn diagram shows which items are counted twice.
Double counting: Double counting happens when one item is added to a total more than once. If a student belongs to both the chess club and the choir, adding the two club sizes counts that student twice. Inclusion-exclusion is the method for fixing this mistake.

What each symbol means

Symbol	Meaning
$\|A \cup B\|$	The number of items in either set $A$ or set $B$ , or in both, with each item counted once. The vertical bars mean the count of the set. The result is a plain count of people, items or cards, so it has no unit.
$\|A\|$	The number of items in set $A$ , a whole number such as 30 for a chess club with 30 members. The bars mean count. It has no unit, because it counts people or things.
$\|B\|$	The number of items in set $B$ , a whole number such as 25 for a choir with 25 singers. It counts members, so it has no unit, and it is read ‘the size of B’.
$\|A \cap B\|$	The number of items that are in both $A$ and $B$ , such as 10 students who are in both the chess club and the choir. Those items were counted in $\|A\|$ and again in $\|B\|$ , so they are subtracted once. It has no unit.

The formula piece by piece

$|A|$: The count of set $A$ alone. For the chess club, $|A| = 30$ students. This is the first count that goes into the total, and every member of $A$ is included in it.
$|B|$: The count of set $B$ alone. For the choir, $|B| = 25$ students. Adding this count to the first one gives a total where any student in both clubs is counted twice.
$|A \cap B|$: The count of the overlap, the items that are in both sets. Those items were added once in $|A|$ and once in $|B|$ , so they appear twice in the sum. In the school example, 10 students are in both the chess club and the choir.
$|A \cup B| = |A| + |B| - |A \cap B|$: In one plain sentence: the number of items in either set $A$ or set $B$ , with each item counted once, equals the size of $A$ plus the size of $B$ minus the size of the overlap between them.
$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$: The same rule for three sets, a standard form to know. Add the three single counts, subtract the three pairwise overlaps, and then add back the triple overlap, which is the set of items that belong to all three sets.

What the formula is doing, and why

What goes in and what comes out. You put in the sizes of the sets and the size of their overlap. You get out the number of items that are in at least one set, with each item counted exactly once. The bars mean count, and the answer has no unit, because it counts people, items or cards.

Why subtract the overlap? Adding $|A|$ and $|B|$ counts every item in both sets twice, once for each set. So the overlap $|A \cap B|$ is subtracted once to fix that. After the subtraction, each shared item is counted exactly one time. The result is the number of items in $A$ or $B$ .

Three sets. The same idea works for three sets: $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ Adding the three sizes counts each item once for every set it is in. Subtracting the three pairwise overlaps removes the extra counts. But an item in all three sets was added 3 times and subtracted 3 times, so it now counts as zero. The triple overlap is added back once to fix that.

The signs alternate. Add the single sets, subtract the pairs, add the triples, and so on for more sets. Each extra set adds more overlaps to count, so the method is most useful when the overlaps are easy to count.

When should you use it? Use it for questions that ask how many items have at least one property. Counting each property on its own and then correcting the overlaps is often easier than counting the mixed cases one at a time. If the sets do not overlap, the overlap is zero and the formula is the plain sum of the two counts.

An everyday picture

Think of two guest lists for a party, one for a chess club and one for a choir. Some people are on both lists. Adding the two list lengths counts those people twice. Subtract the people who are on both lists, and you have the number of different people who came from at least one list.

Worked example: Students in three school activities

A school has 60 students. Let $A$ be the chess club with 30 students, $B$ the choir with 25 students, and $C$ the robotics team with 20 students. The overlaps are: 10 students are in both $A$ and $B$ , 8 are in both $A$ and $C$ , 6 are in both $B$ and $C$ , and 4 are in all three. We want $|A \cup B \cup C|$ , the number of students in at least one activity.

Add the three single counts. Add the sizes of the three activities: $|A| + |B| + |C| = 30 + 25 + 20 = 75$ . This counts every student once for each activity they belong to, so the 4 students in all three are counted three times.
Subtract the pairwise overlaps. The overlaps for pairs are 10, 8 and 6, and together they add to 24. Subtracting them gives $75 - 24 = 51$ . This removes one count from each overlap, so a student in exactly two activities now counts once. A student in all three has been removed three times and now counts zero times.
Add back the triple overlap. The 4 students in all three activities now count zero times, so add them back once: $51 + 4 = 55$ . So $|A \cup B \cup C| = 55$ , the number of students in at least one activity.
Find the students in no activity. The school has 60 students, and 55 of them are in at least one activity. So $60 - 55 = 5$ students are in none of the three activities.
Check by counting the regions. Students in all three: 4. In exactly two activities: chess and choir only $10 - 4 = 6$ , chess and robotics only $8 - 4 = 4$ , choir and robotics only $6 - 4 = 2$ . In exactly one activity: chess only $30 - (6 + 4 + 4) = 16$ , choir only $25 - (6 + 4 + 2) = 13$ , robotics only $20 - (4 + 2 + 4) = 10$ . Adding all seven regions gives $16 + 13 + 10 + 6 + 4 + 2 + 4 = 55$ , which matches.

Answer: 55 students are in at least one activity, and 5 students are in none. The 4 students in all three activities are counted exactly once in the final total.

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Forgetting to subtract the overlap. Adding $|A| + |B|$ alone counts shared items twice, so the union comes out too big.
Stopping after the pairs when there are three sets. The triple overlap must be added back, or the students in all three activities disappear from the count.
Confusing $\cup$ and $\cap$ . The union $\cup$ means “or”, and the intersection $\cap$ means “and”. Mixing them up gives a count for a different question.
Assuming the sets do not overlap. If they do, you must subtract. The plain sum is only right when every overlap is zero.

Where you will meet it

Counting the whole numbers from 1 to 100 that are divisible by 2 or by 5. A number is divisible by 2 if it is even. There are 50 multiples of 2 and 20 multiples of 5, and 10 multiples of both, so $50 + 20 - 10 = 60$ numbers qualify.
Probability, which is a number from 0 (never) to 1 (always). The chance that $A$ or $B$ happens is $P(A) + P(B) - P(A \text{ and } B)$ , the same formula with chances in place of counts.
Counting derangements, which are arrangements where no item stays in its original place, such as a shuffle of cards where no card ends up in its old position.
Counting passwords or codes that meet at least one rule, such as containing a digit or a capital letter.

Questions people ask

Why do we subtract the overlap instead of counting each set once?

Counting each set once gives the wrong total when sets share members. An item in both sets gets added twice, once for each set. Subtracting the overlap once leaves each item counted exactly one time.

Does the formula always subtract?

For two sets, the overlap is always subtracted. For three sets the signs alternate: add the singles, subtract the pairs, then add back the triple overlap. The same pattern continues for more sets.

What happens when the sets do not overlap?

Then $|A \cap B| = 0$ , the overlap is empty, and the formula reduces to $|A| + |B|$ , the ordinary sum. For example, a chess club of 30 and a choir of 25 with no shared members gives 55 people in total.

De Morgan's Laws: De Morgan’s laws say that a NOT in front of a group of AND or OR conditions flips the group: AND becomes OR, and OR becomes AND.
Combinations: A combination counts the different groups you can pick from a set of items when the order of the picks does not matter.
Pigeonhole Principle: If you put more things than boxes into the boxes, at least one box must hold two or more things.