Mathematical Preliminaries: The inclusion- exclusion principle

The Inclusion-Exclusion Principle

The Inclusion-Exclusion Principle is a crucial counting technique in combinatorics. It is used to calculate the number of elements in the union of multiple sets.
The principle helps to avoid the problem of double counting when adding the counts of multiple sets.

The principle states that for any two finite sets, the size of their union is the sum of their individual sizes, but minus the size of their intersection.
In mathematical terms, if you have two sets A and B, then |A ∪ B| = |A| + |B| - |A ∩ B|.
If one extends this concept to three sets, it becomes: |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|.

The Inclusion-Exclusion Principle is widely employed across different fields of mathematics, such as in probability theory and the determination of the Euler characteristic in topology.
The principle is specifically used when one wants to count the number of elements in the union of overlapping sets.
The principle helps to correct the problem of double counting, where one counts the same element twice when calculating the size of the union of overlapping sets.

Suppose one wants to know the number of integers between 1 and 100 that are divisible by 5 or 7. Using the Inclusion-Exclusion Principle, one would add the number of integers divisible by 5 (i.e., 20) to those divisible by 7 (i.e.,14), and then subtract those that are divisible by both 5 and 7 (i.e., 2). The result would be 20 + 14 - 2 = 32.
Another example would be finding how many numbers from 1 to 100 are divisible by 2, 3, or 5. Applying the principle, you would add the amounts divisible by these individual numbers, subtract quantities divisible by all pairs of numbers, and finally add numbers divisible by all three. By doing the calculations, one would find the solution is 50 + 33 + 20 - 16 - 10 - 6 + 3 = 74.