Inclusion–exclusion principle

The inclusion–exclusion principle is a counting technique that extends the addition method. It is used when two or more sets overlap, and we need to avoid counting the same elements more than once.

 

The idea is that we first add the sets together, and then subtract the overlapping elements. If there are more sets, we may need to add and subtract several times.

 

 

Example 1: Books

A bookstore has:

 

• 20 math books
• 15 physics books
• 5 books that count as both

 

If we just add them together:

 

$$ \large 20 + 15 = 35 $$

 

we get too much, because the 5 overlapping books are counted twice. The correct number is:

 

$$ \large 20 + 15 - 5 = 30 $$

 

 

Example 2: Students

There are 40 students taking math, 30 taking physics, and 10 taking both subjects. How many unique students are there?

 

Here we use the formula:

 

$$ \large |M \cup F| = |M| + |F| - |M \cap F| $$

 

In numbers:

 

$$ \large 40 + 30 - 10 = 60 $$

 

 

Formula

For two sets:

 

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

 

For three sets:

 

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

 

In general, we alternate between adding and subtracting, depending on how many sets overlap.

 

 

When can you use the inclusion–exclusion principle?

 

• When two or more sets overlap.
• When you want to find the number of unique elements without double-counting.
• When problems cannot be solved with the addition method alone.

 

 

Summary

The inclusion–exclusion principle is used to correct for overlap between sets. We first add together and then subtract the overlapping elements. With more sets, we alternate between plus and minus depending on how many sets overlap.

 

The principle is an important tool in combinatorics and probability, because it ensures that we count each unique possibility exactly once.