Principle of Inclusion-Exclusion

Principle of Inclusion-Exclusion

The Principle of Inclusion-Exclusion (PIE) is a fundamental combinatorial method used to count the number of elements in the union of multiple sets when those sets may overlap. It provides a way to account for the overlap between sets and ensure that elements are counted the correct number of times.

The principle is especially useful in situations where you want to find the total number of elements in the union of several sets, but some elements are counted more than once due to overlaps between the sets.

Basic Idea

The general idea behind the inclusion-exclusion principle is:

1. Start by including all elements from the sets you are interested in (counting every element in each set).
2. Subtract the overlap between pairs of sets to avoid counting those elements multiple times.
3. Add back the overlap between triples of sets (since elements from three sets were subtracted too much in step 2).
4. Continue this process, alternating adding and subtracting, for all possible overlaps among the sets.

General Formula

For two sets $A$ and $B$, the principle of inclusion-exclusion can be stated as:

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

Where:

• $|A \cup B|$ is the number of elements in the union of sets $A$ and $B$.
• $|A|$ is the number of elements in set $A$.
• $|B|$ is the number of elements in set $B$.
• $|A \cap B|$ is the number of elements in the intersection of sets $A$ and $B$ (i.e., elements common to both sets).

This formula ensures that elements in $A \cap B$ are not counted twice.

For three sets $A$, $B$, and $C$, the formula is extended as:

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

Where:

• The first three terms count the elements in each of the sets.
• The next three terms subtract the overlaps of pairs of sets (because these elements were counted twice).
• The last term adds back the intersection of all three sets (because these elements were subtracted too many times).

For $n$ sets, the general formula for the principle of inclusion-exclusion is:

$$|A_1 \cup A_2 \cup \dots \cup A_n| = \sum_{i=1}^{n} |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \dots + (-1)^{n+1} |A_1 \cap A_2 \cap \dots \cap A_n|$$

Where the summations alternate between adding and subtracting the sizes of intersections of increasing numbers of sets.

Steps for Applying Inclusion-Exclusion

1. Identify the sets you are working with and what you want to count.
2. Start with the size of each individual set, summing them up.
3. Subtract the size of pairwise intersections to account for elements that have been counted twice.
4. Add the size of triple intersections, as these elements were subtracted too much in the previous step.
5. Continue the process for intersections of higher numbers of sets, alternating between subtracting and adding the sizes of the intersections.
6. Finally, you will have the correct count for the union of the sets.

Example 1: Counting the Number of Students in a Class

Suppose in a class of 30 students:

• 15 students play basketball.
• 12 students play soccer.
• 10 students play both basketball and soccer.

How many students play either basketball or soccer?

Let:

• $A$ be the set of students who play basketball.
• $B$ be the set of students who play soccer.

We are interested in the number of students in $A \cup B$, which represents students who play basketball or soccer. Using the inclusion-exclusion principle:

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

Substituting the given values:

$$|A \cup B| = 15 + 12 - 10 = 17$$

So, 17 students play either basketball or soccer.

Example 2: Generalizing to Three Sets

Consider a situation where:

• There are 50 people at a party.
• 30 people drink coffee.
• 20 people drink tea.
• 10 people drink both coffee and tea.
• 5 people drink coffee, tea, and juice.

We want to know how many people drink either coffee, tea, or juice.

Let:

• $A$ be the set of people who drink coffee.
• $B$ be the set of people who drink tea.
• $C$ be the set of people who drink juice.

We want to find $|A \cup B \cup C|$, the total number of people who drink coffee, tea, or juice.

Using the inclusion-exclusion principle for three sets:

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

Substituting the given values:

• $|A| = 30$, $|B| = 20$, $|C| = 50$
• $|A \cap B| = 10$ (people who drink both coffee and tea)
• $|B \cap C| = 0$ (no one drinks both tea and juice)
• $|A \cap C| = 0$ (no one drinks both coffee and juice)
• $|A \cap B \cap C| = 5$ (people who drink coffee, tea, and juice)

Now we compute:

$$|A \cup B \cup C| = 30 + 20 + 50 - 10 - 0 - 0 + 5 = 95$$

Thus, 95 people drink either coffee, tea, or juice.

Applications of Inclusion-Exclusion

The principle of inclusion-exclusion is widely used in many areas, including:

1. Counting Problems: Calculating the number of elements in the union of several sets.
2. Probability Theory: Computing the probability of the union of events, particularly when events are not mutually exclusive.
3. Set Theory: Understanding the relationships between multiple sets and their intersections.
4. Graph Theory: Counting paths, cycles, or other structures in graphs with multiple conditions.
5. Algorithm Analysis: Determining the complexity of algorithms that involve multiple subproblems or components.

Conclusion

The Principle of Inclusion-Exclusion is a powerful combinatorial tool used to correctly count the elements in the union of multiple sets by considering the overlaps between them. It ensures that elements are not counted multiple times and provides an efficient way to compute set sizes in complex problems involving intersections of sets.