Combinatorics • Topic 2

Addition Principle

The Addition Principle handles cases where choices are mutually exclusive. It is the basis for "Casework," a standard Olympiad strategy.

Statement

Theorem (Addition Principle)

If a task can be performed by method

A

OR method

B

, and these methods are mutually exclusive (disjoint), then:

Total Ways = (Ways for A) + (Ways for B)

General Form

If we have disjoint sets

S_{1}, S_{2}, \dots, S_{k}

, then:

∣ S_{1} \cup S_{2} \cup \dots \cup S_{k} ∣ = ∣ S_{1} ∣ + ∣ S_{2} ∣ + \dots + ∣ S_{k} ∣

Principle of Inclusion-Exclusion (Intro)

What if the sets are not disjoint? We must subtract the overlap to avoid double counting.

Theorem (PIE for 2 Sets)

∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣

Example

How many integers from 1 to 100 are multiples of 2 or 3?

Proof. Let $A$ be multiples of 2: $⌊ 100/2 ⌋ = 50$ . Let $B$ be multiples of 3: $⌊ 100/3 ⌋ = 33$ . Intersection $A \cap B$ (multiples of 6): $⌊ 100/6 ⌋ = 16$ . Total = $50 + 33 - 16 = 67$ . ∎

Constructive Counting vs. Complementary Counting

Constructive: Divide the problem into disjoint cases (Addition Principle).
Complementary: Count the total possibilities and subtract the "bad" cases.

$Good = Total - Bad$

Tip

Use Complementary Counting when the condition involves "at least one" or "not all".

Practice Problems

Exercise (Problem 1)

How many 3-digit numbers contain the digit 7 at least once?

Exercise (Problem 2)

Find the number of pairs

(x, y)

of distinct integers from

{1, 2, \dots, 10}

such that their sum is even.

Exercise (Problem 3)

How many ways are there to arrange the letters of "MATH" such that "M" is not first?