Principal of inclusion/exclusion and union of overlapping sets

The Principle of Inclusion-Exclusion (PIE) is a counting technique used to find the size of the union of multiple overlapping sets. It corrects for overcounting by systematically adding and subtracting the sizes of intersections.

---

🧠 Principle of Inclusion-Exclusion (PIE)

Let $A_1, A_2, \dots, A_n$ be sets. The number of elements in their union is:

✅ PIE Formula:

For 2 sets:

$$|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2|$$

For 3 sets:

$$|A_1 \cup A_2 \cup A_3| = |A_1| + |A_2| + |A_3| - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_2 \cap A_3| + |A_1 \cap A_2 \cap A_3|$$

For $n$ sets:

$$\left|\bigcup_{i=1}^{n} A_i \right| = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1} |A_1 \cap A_2 \cap \dots \cap A_n|$$

---

📘 Why Use PIE?

When elements belong to multiple sets, naive addition counts them multiple times. PIE ensures each element is counted exactly once in the union.

---

🔢 Examples

🔸 Example 1: Two Sets

Let:

• $|A| = 30$

• $|B| = 25$

• $|A \cap B| = 10$

Question: How many are in $A \cup B$?

Solution:

$$|A \cup B| = |A| + |B| - |A \cap B| = 30 + 25 - 10 = 45$$

---

🔸 Example 2: Three Sets

Let:

• $|A| = 20$, $|B| = 25$, $|C| = 15$

• $|A \cap B| = 5$, $|A \cap C| = 4$, $|B \cap C| = 6$

• $|A \cap B \cap C| = 2$

Question: How many are in $A \cup B \cup C$?

Solution:

$$\begin{align*} |A \cup B \cup C| &= |A| + |B| + |C| \\ &\quad - |A \cap B| - |A \cap C| - |B \cap C| \\ &\quad + |A \cap B \cap C| \\ &= 20 + 25 + 15 - 5 - 4 - 6 + 2 = 47 \end{align*}$$

---

🧮 Example 3: Real-Life Application

In a survey:

• 40 people like coffee (C)

• 30 like tea (T)

• 20 like juice (J)

• 15 like both coffee and tea

• 10 like both coffee and juice

• 5 like both tea and juice

• 3 like all three

Find: How many like at least one of the three drinks?

Solution:

$$|C \cup T \cup J| = 40 + 30 + 20 - 15 - 10 - 5 + 3 = 63$$

---

Now, let's see for 3 sets why does this work.
A is made up of 4 parts:
(1) A' = Elements which are exclusive to A and not shared with B,C.
(2) AB' = Elements which are common ONLY in A,B and NOT C
(3) AC' = Elements which are common ONLY in A,C and NOT B
(4) ABC' = Elements which are common in all three of A,B,C which is A∩B∩C.
Now

A∩B = AB' + ABC'
A∩C = AC' + ABC'

B and C are composed similarly.

Now if simply add all elements of A,B,C in a naive way:
A + B + C =
A' + AB' + AC' + ABC' +
B' + AB' + BC' + ABC' +
C' + BC' + AC' + ABC'

So, these are portions coming twice AB', AC', BC'.
To fix that we subtract 

A∩B = AB' + ABC'
A∩C = AC' + ABC'
B∩C = BC' + ABC'

Now the sum becomes:

A' + AB' + AC' + BC' + B' + C'.
Notice that ABC' is vanished.
So we need to add it back.
And that's how we get PIE and union of overlapping sets.