Inclusion Exclusion

$$\begin{array}{rl}|S_1\cup S_2\cup \cdots \cup S_n|=& \sum _{1\le i\le n}|S_i|\\ -& \sum _{1\le i<j\le n}|S_i\cap S_j|\\ +& \sum _{1\le i<j<k\le n}|S_i\cap S_j\cap S_k|\\ -& \cdots +(-1{)}^{n+1}|S_1\cap S_2\cap \cdots \cap S_n|\end{array}$$

---

Examples

1. Total Number of Strings

How many $n$-length strings are there over an alphabet of size $X$?

$$X^n\text{(Power Rule)}$$

---

2. Strings Where Each Character Is Used at Least Once

Let the alphabet be $\{a,b,c\}$ and string length be 12.
We want to count strings where each character appears at least once.

This is equivalent to:

$$\sum _{k=0}^x\left(\genfrac{}{}{0ex}{}{x}{k}\right)(x-k{)}^n(-1{)}^k$$

For $x=3$ and $n=12$:

$$\sum _{k=0}^3\left(\genfrac{}{}{0ex}{}{3}{k}\right)(3-k{)}^{12}(-1{)}^k$$

---

Set Interpretation

Let:

• $A$: strings where a is used at least once
• $B$: strings where b is used at least once
• $C$: strings where c is used at least once

We want:

$$|A\cap B\cap C|$$

Using Demorgan’s Law:

$$\begin{array}{rl}|\overline{A\cap B\cap C}|& =|\overline{A}\cup \overline{B}\cup \overline{C}|\\ |A\cap B\cap C|& =|\text{ALL}|-|\overline{A}\cup \overline{B}\cup \overline{C}|\end{array}$$

Expanding:

$$\begin{array}{rl}|\text{ALL}|-[& |\overline{A}|+|\overline{B}|+|\overline{C}|\\ & -|\overline{A}\cap \overline{B}|-|\overline{A}\cap \overline{C}|-|\overline{B}\cap \overline{C}|\\ & +|\overline{A}\cap \overline{B}\cap \overline{C}|]\end{array}$$

Where:

• $\overline{A}$ = strings without a
• $\overline{B}$ = strings without b
• $\overline{C}$ = strings without c

Final result:

$$\sum _{k=0}^3\left(\genfrac{}{}{0ex}{}{3}{k}\right)(3-k{)}^{12}(-1{)}^k$$

See Set Theory for more information