Principle of Inclusion-Exclusion

Combinatorics Progress

Completed0/11

0 completed0 in progress

Thr Principle of Inclusion-Exclusion, also known as PIE and its applications in contests.

Author: Jaden Park

Introduction

The principle of inclusion-exclusion is based on a straightforwards idea: to find the total number of elements in several sets, you start by adding the sizes of those sets. However, if the sets overlap, elements that appear in multiple sets are counted more than once. To correct this, PIE subtracts the sizes of pairwise intersections. Yet, this adjustment leads to elements in the intersections of three sets being excluded entirely, so their counts are added back in, and so on.

Formula

The PIE formula for three sets $A, B,$ and $C$ can be expressed as:

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

The formula can be generalized to $n$ sets as:

|A_1 \cup A_2 \cup \cdots \cup A_n| = \sum_{k=1}^n (-1)^{k+1} \left(\sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n} |A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_k}|\right)

Here are some examples that cover this formula.

Example

How many integers between $1$ and $1000$ are relatively prime to $2, 3,$ and $5$ ?

Relative Prime - when two numbers have are no common factors other than 1.

Solution

The total number of integers from $1$ to $1000$ is $1000.$

1. Multiples of $2$ : The largest multiple of $2$ less than or equal to $1000$ is $1000,$ so there are $\lfloor\frac{1000}{2}\rfloor = 500$ multiples of $2.$

2. Multiples of $3$ : Similarly, there are $\lfloor\frac{1000}{3}\rfloor = 333$ multiples of $3.$

3. Multiples of $5$ : Therer are $\lfloor\frac{1000}{5}\rfloor = 200$ multiples of $5.$

However, some numbers are multiples of more than one of these numbers, and we've counted them multiple times. So, we need to subtract these.

1. Multiples of $2$ and $3$ : There are $\lfloor\frac{1000}{6}\rfloor = 166$ multiples of $6.$

2. Multiples of $2$ and $5$ : There are $\lfloor\frac{1000}{10}\rfloor = 100$ multiples $10.$

3. Multiples of $3$ and $5$ : There are $\lfloor\frac{1000}{15}\rfloor = 66$ multiples of $15.$

4. Multiples of $2, 3,$ and $5$ : There are $\lfloor\frac{1000}{30}\rfloor = 33$ multiples of $30.$

Using PIE, we get

1000 - 500 - 333 - 200 + 166 + 100 + 66 - 33 = 266

Therefore, there are $266$ integers between $1$ and $1000$ that are relatively prime to $2, 3,$ and $5.$

Final Notes and Tips

Make sure not to overcount or undercount. Would recommend understanding the idea behind the formula, but not memorizing (it's pretty rare to get $< 3$ sets on a real problem).

Distinguishability

Pigeon Hole Principle

Combinatorics Progress

Counting

Principles

Miscellaneous

Introduction

Formula

Example

Solution

Final Notes and Tips

Introduction

Formula

Example

Solution

Final Notes and Tips