Inclusion-Exclusion
The inclusion-exclusion principle counts elements in overlapping sets without double-counting.
Principle
For two sets \(A\) and \(B\):
\[ |A \cup B| = |A| + |B| - |A \cap B| \]
For three sets: \(|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|\).
Example
20 students take Math, 15 take Physics, 5 take both. How many take at least one?
\[ |M \cup P| = 20 + 15 - 5 = 30 \]
Applications
Used in probability (e.g., event unions), combinatorics (e.g., derangements), and database queries.