discrete math inclusion exclusion explained

• What is the Inclusion-Exclusion Principle?
• The Basics: Two Sets
• Extending to Three Sets
• The General Inclusion-Exclusion Formula
• Illustrative Examples of the Inclusion-Exclusion Principle
• Applications of the Inclusion-Exclusion Principle
• Common Pitfalls and Tips for Using Inclusion-Exclusion
• Conclusion

Understanding the Inclusion-Exclusion Principle

The inclusion-exclusion principle is a fundamental counting technique in discrete mathematics used to determine the cardinality (the number of elements) of the union of multiple sets. At its core, it addresses the challenge of counting elements that belong to more than one set, preventing overcounting that would occur if we simply added the sizes of individual sets. By systematically adding the sizes of the individual sets, then subtracting the sizes of their pairwise intersections, then adding back the sizes of their triple intersections, and so on, the principle ensures that each element in the union is counted exactly once.

What is the Core Idea Behind Inclusion-Exclusion?

Imagine you have several groups of items, and some items belong to multiple groups. If you want to know the total number of unique items across all groups, simply summing the number of items in each group will lead to errors. Items that appear in two groups will be counted twice, items in three groups will be counted thrice, and so on. The inclusion-exclusion principle provides a systematic method to correct these overcounts. It "includes" the elements by adding the sizes of individual sets, then "excludes" the elements that were counted twice by subtracting the intersections of pairs of sets, and then "includes" elements that were subtracted too many times by adding back intersections of triples of sets, and this pattern continues for larger numbers of sets.

Why is it Important in Discrete Mathematics?

The importance of the inclusion-exclusion principle stems from its ability to solve a wide range of combinatorial problems. It is indispensable when dealing with situations where elements can satisfy multiple criteria simultaneously. Without it, accurately counting the number of objects with certain properties, such as counting numbers divisible by certain primes or counting derangements, would be significantly more difficult or even impossible with simpler methods. Its systematic approach makes complex counting problems tractable.

The Inclusion-Exclusion Principle for Two Sets

The simplest form of the inclusion-exclusion principle involves two sets, say set A and set B. We want to find the total number of elements in either A or B, or both, which is denoted as |A ∪ B|. If we simply add the number of elements in A and the number of elements in B (i.e., |A| + |B|), we will have counted the elements that are common to both A and B (the intersection, |A ∩ B|) twice. Therefore, to correct this, we must subtract the size of the intersection once.

The Formula for Two Sets

The inclusion-exclusion principle for two sets is stated as follows:

|A ∪ B| = |A| + |B| - |A ∩ B|

Here:

• |A ∪ B| represents the number of elements in the union of sets A and B (elements in A, or in B, or in both).
• |A| represents the number of elements in set A.
• |B| represents the number of elements in set B.
• |A ∩ B| represents the number of elements in the intersection of sets A and B (elements that are in both A and B).

An Illustrative Example with Two Sets

Let's consider an example to clarify this. Suppose we have a class of students, and we want to find out how many students play either soccer or basketball, or both. Let set S be the students who play soccer, and set B be the students who play basketball.

Suppose:

• |S| = 20 students play soccer.
• |B| = 15 students play basketball.
• |S ∩ B| = 5 students play both soccer and basketball.

Using the inclusion-exclusion principle:

|S ∪ B| = |S| + |B| - |S ∩ B|

|S ∪ B| = 20 + 15 - 5

|S ∪ B| = 35 - 5

|S ∪ B| = 30

So, 30 students play either soccer or basketball or both. If we had just added |S| and |B|, we would have gotten 35, which incorrectly counts the 5 students who play both sports twice.

The Inclusion-Exclusion Principle for Three Sets

Extending the principle to three sets, say A, B, and C, involves a similar logic. We want to find the size of the union, |A ∪ B ∪ C|. If we simply add |A| + |B| + |C|, we overcount elements that are in the intersections of two sets and also elements that are in the intersection of all three sets.

The Formula for Three Sets

The inclusion-exclusion principle for three sets is given by:

|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|

Let's break down this formula:

• First, we sum the sizes of the individual sets: |A| + |B| + |C|.
• Then, we subtract the sizes of the pairwise intersections: -|A ∩ B| - |A ∩ C| - |B ∩ C|. This corrects for elements counted twice. However, this step also undercounts elements that are in all three sets because they were added three times and then subtracted three times (once for each pairwise intersection).
• Finally, we add back the size of the intersection of all three sets: +|A ∩ B ∩ C|. This ensures that elements present in all three sets are counted exactly once.

An Illustrative Example with Three Sets

Let's consider a scenario with students studying different languages. Let A be the set of students studying French, B be the set of students studying Spanish, and C be the set of students studying German.

Suppose we have the following numbers:

• |A| = 25 students study French.
• |B| = 20 students study Spanish.
• |C| = 18 students study German.
• |A ∩ B| = 10 students study French and Spanish.
• |A ∩ C| = 8 students study French and German.
• |B ∩ C| = 7 students study Spanish and German.
• |A ∩ B ∩ C| = 3 students study all three languages.

Using the inclusion-exclusion principle:

|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|

|A ∪ B ∪ C| = 25 + 20 + 18 - 10 - 8 - 7 + 3

|A ∪ B ∪ C| = 63 - 25 + 3

|A ∪ B ∪ C| = 38 + 3

|A ∪ B ∪ C| = 41

Therefore, 41 students study at least one of the three languages.

The General Inclusion-Exclusion Formula

The inclusion-exclusion principle can be generalized to any finite number of sets. For a collection of $n$ sets, $A_1, A_2, \dots, A_n$, the size of their union is given by a formula that involves summing the sizes of all possible intersections of these sets, with alternating signs.

The Formal Mathematical Statement

The general formula for the inclusion-exclusion principle is:

$$ \left| \bigcup_{i=1}^{n} A_i \right| = \sum_{i} |A_i| - \sum_{i

In simpler terms, this means:

• Sum the sizes of all individual sets.
• Subtract the sum of the sizes of all pairwise intersections (intersections of 2 sets).
• Add the sum of the sizes of all triple intersections (intersections of 3 sets).
• Continue this process, alternating between subtracting and adding, until you reach the intersection of all $n$ sets. The last term will have a sign of $(-1)^{n-1}$.

The summation notation can be interpreted as follows:

• The first sum, $\sum_{i} |A_i|$, includes all terms of the form $|A_i|$.
• The second sum, $\sum_{i
• The third sum, $\sum_{i
• This continues until the final term, which is the intersection of all sets $A_1 \cap A_2 \cap \dots \cap A_n$.

Understanding the Pattern of Signs

The alternating signs are crucial. An element that belongs to $k$ sets will be:

• Included in the first sum $k$ times.
• Included in the second sum (pairwise intersections) $\binom{k}{2}$ times.
• Included in the third sum (triple intersections) $\binom{k}{3}$ times.
• And so on.

The formula ensures that when summed, an element belonging to exactly $k$ sets will be counted exactly once. For an element in $k$ sets, its contribution to the sum is:

$$ \binom{k}{1} - \binom{k}{2} + \binom{k}{3} - \dots + (-1)^{k-1} \binom{k}{k} $$

This sum is known to be equal to $1 - (1 - 1)^k = 1 - 0^k$. For $k \ge 1$, this value is 1. If $k=0$ (element not in any set), the sum is 0. This confirms the principle's correctness.

Illustrative Examples of the Inclusion-Exclusion Principle

Let's work through a few more detailed examples to solidify understanding of how the inclusion-exclusion principle is applied in practice.

Example: Numbers Divisible by Certain Integers

Consider the task of finding the number of integers between 1 and 100 (inclusive) that are divisible by 2, 3, or 5.

Let A be the set of numbers divisible by 2.

Let B be the set of numbers divisible by 3.

Let C be the set of numbers divisible by 5.

We need to calculate:

• |A| = floor(100/2) = 50
• |B| = floor(100/3) = 33
• |C| = floor(100/5) = 20

Now, the pairwise intersections:

• |A ∩ B| = numbers divisible by 2 and 3 (i.e., by lcm(2,3) = 6) = floor(100/6) = 16
• |A ∩ C| = numbers divisible by 2 and 5 (i.e., by lcm(2,5) = 10) = floor(100/10) = 10
• |B ∩ C| = numbers divisible by 3 and 5 (i.e., by lcm(3,5) = 15) = floor(100/15) = 6

Finally, the intersection of all three:

• |A ∩ B ∩ C| = numbers divisible by 2, 3, and 5 (i.e., by lcm(2,3,5) = 30) = floor(100/30) = 3

Applying the inclusion-exclusion principle:

|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|

|A ∪ B ∪ C| = 50 + 33 + 20 - 16 - 10 - 6 + 3

|A ∪ B ∪ C| = 103 - 32 + 3

|A ∪ B ∪ C| = 71 + 3

|A ∪ B ∪ C| = 74

Thus, there are 74 numbers between 1 and 100 divisible by 2, 3, or 5.

Example: Counting Strings with Forbidden Patterns

Suppose we want to count the number of binary strings of length 4 that do not contain "00".

The total number of binary strings of length 4 is $2^4 = 16$.

Let U be the set of all binary strings of length 4, so |U| = 16.

Let A be the set of strings containing "00" starting at position 1 (i.e., "00xx").

Let B be the set of strings containing "00" starting at position 2 (i.e., "x00x").

Let C be the set of strings containing "00" starting at position 3 (i.e., "xx00").

We want to find the number of strings that do not contain "00", which is |U| - |A ∪ B ∪ C|.

Calculate the sizes of the sets and their intersections:

• |A|: Strings are "00xx". The last two bits can be anything. So, |A| = $2^2 = 4$.
• |B|: Strings are "x00x". The first and last bits can be anything. So, |B| = $2^2 = 4$.
• |C|: Strings are "xx00". The first two bits can be anything. So, |C| = $2^2 = 4$.

Pairwise intersections:

• |A ∩ B|: Strings contain "00" at pos 1 and "00" at pos 2. This means "000x". So, |A ∩ B| = $2^1 = 2$.
• |A ∩ C|: Strings contain "00" at pos 1 and "00" at pos 3. This means "00x00". This is impossible for length 4. However, if the pattern could overlap, we'd consider it. For "00" at pos 1 and "00" at pos 3, it's "0000". So, |A ∩ C| = 1 ("0000").
• |B ∩ C|: Strings contain "00" at pos 2 and "00" at pos 3. This means "x000". So, |B ∩ C| = $2^1 = 2$.

Triple intersection:

• |A ∩ B ∩ C|: Strings contain "00" at pos 1, pos 2, and pos 3. This implies "0000". So, |A ∩ B ∩ C| = 1.

Applying inclusion-exclusion for |A ∪ B ∪ C|:

|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|

|A ∪ B ∪ C| = 4 + 4 + 4 - 2 - 1 - 2 + 1

|A ∪ B ∪ C| = 12 - 5 + 1

|A ∪ B ∪ C| = 7 + 1

|A ∪ B ∪ C| = 8

The number of strings that do contain "00" is 8. The number of strings that do not contain "00" is |U| - |A ∪ B ∪ C| = 16 - 8 = 8.

Let's verify: The strings without "00" are: 0101, 0100 (no), 0110, 0111, 1010, 1011, 1101, 1110, 1111. There are indeed 8 such strings. The strings with "00" are: 0000, 0001, 0010, 0011, 1000, 1001, 1100, 0100.

Applications of the Inclusion-Exclusion Principle

The inclusion-exclusion principle is a versatile tool with applications spanning various fields, from theoretical mathematics to practical computer science and probability.

Combinatorics and Counting Problems

This is the primary domain where the inclusion-exclusion principle shines. It is used to solve problems involving counting arrangements, permutations, and combinations where multiple conditions or properties must be considered. A classic example is counting derangements, which are permutations of elements such that no element appears in its original position. The inclusion-exclusion principle is fundamental to deriving the formula for the number of derangements.

Probability Theory

In probability, the inclusion-exclusion principle is used to calculate the probability of the union of events. If $P(A_i)$ is the probability of event $A_i$, then the probability of at least one of the events occurring is:

$$ P\left(\bigcup_{i=1}^{n} A_i\right) = \sum_{i} P(A_i) - \sum_{i

This is directly analogous to the counting version, with probabilities replacing cardinalities.

Computer Science Algorithms

The principle finds applications in computer science, particularly in areas like algorithm analysis, network routing, and the design of data structures. For instance, in graph theory, it might be used to count the number of graphs with certain properties. In string matching algorithms, it can be used to count occurrences of patterns or to analyze the complexity of tasks involving multiple patterns.

Number Theory

As seen in the example of counting numbers divisible by certain integers, the inclusion-exclusion principle is a powerful tool in number theory for problems related to divisibility, prime factorization, and the distribution of numbers with specific properties. It's a key component in proving results like the Prime Number Theorem's preliminary steps or counting numbers coprime to a given number (Euler's totient function can be derived using it).

Common Pitfalls and Tips for Using Inclusion-Exclusion

While powerful, the inclusion-exclusion principle can be tricky to apply correctly. Awareness of common pitfalls can help prevent errors.

Pitfall 1: Incorrectly Identifying Sets and Intersections

A frequent mistake is misinterpreting the problem statement and defining the sets incorrectly. It's essential to clearly define what each set represents and precisely identify the elements that constitute the intersections at various levels (pairwise, triple, etc.).

Tip: Draw Venn diagrams, especially for problems involving 2 or 3 sets. This visual aid can help clarify the relationships between sets and their overlapping regions. For more than three sets, consider a systematic approach to listing all possible intersections.

Pitfall 2: Errors in Calculating Intersection Sizes

For problems involving divisibility, ensuring the correct use of the least common multiple (LCM) for intersections is crucial. For other types of problems, carefully determine the conditions that must be met for an element to be in a specific intersection.

Tip: Double-check the LCM calculations. When dealing with multiple properties, consider how the properties combine. For example, if a property is "divisible by 4" and another is "divisible by 6," the intersection is "divisible by lcm(4,6) = 12."

Pitfall 3: Forgetting Alternating Signs or Missing Terms

The alternating signs (+, -, +, -, ...) are fundamental. Forgetting to switch the sign or missing an entire level of intersection (e.g., forgetting the triple intersection in a three-set problem) will lead to an incorrect result.

Tip: Follow the pattern religiously: Sum singles, subtract doubles, add triples, subtract quadruples, and so on. Write out the formula for the specific number of sets you are using before plugging in values.

Pitfall 4: Overlapping Definitions in Complex Scenarios

In more complex scenarios, the "elements" being counted might be more abstract, like strings, permutations, or graph structures. Defining what constitutes an "overlap" or "intersection" in these cases requires careful thought.

Tip: Clearly define your universe of elements and the properties that define your sets. If a property is "contains substring X" and another is "contains substring Y," the intersection involves elements containing both X and Y. Consider potential overlaps between these substrings themselves.

Tip: Start with a simpler problem

If a problem seems overwhelming, try to break it down into smaller, more manageable parts. Sometimes, solving a similar problem with fewer sets can provide insight into how to approach the more complex version.

Conclusion

The inclusion-exclusion principle stands as a cornerstone in discrete mathematics, offering an elegant and systematic method for counting the elements in the union of sets. By carefully adding the cardinalities of individual sets and then iteratively subtracting the cardinalities of pairwise intersections, adding triple intersections, and so on, we can accurately account for all elements without overcounting. This principle is not merely theoretical; its applications are widespread, proving invaluable in combinatorics, probability theory, computer science, and number theory.

Mastering the discrete math inclusion exclusion explained concept empowers individuals to tackle complex counting problems that would otherwise be intractable. Whether calculating the number of integers with specific divisibility properties, determining the probability of multiple events occurring, or analyzing algorithmic efficiency, the inclusion-exclusion principle provides a robust framework. By understanding its formulas, common pitfalls, and practical applications, one can confidently apply this fundamental counting technique to a wide array of challenging mathematical and computational tasks.