The Inclusion-Exclusion Principle

The inclusion-exclusion principle is an important combinatorial way to compute the size of a set or the probability of complex events. It relates the sizes of individual sets with their union.

Statement

The verbal formula

The inclusion-exclusion principle can be expressed as follows:

To compute the size of a union of multiple sets, it is necessary to sum the sizes of these sets separately, and then subtract the sizes of all pairwise intersections of the sets, then add back the size of the intersections of triples of the sets, subtract the size of quadruplesof the sets, and so on, up to the intersection of all sets.

The formulation in terms of sets

The above definition can be expressed mathematically as follows:

| ⋃_{i = 1}^{n} A_{i} | = \sum_{i = 1}^{n} | A_{i} | - \sum_{1 \leq i < j \leq n} | A_{i} \cap A_{j} | + \sum_{1 \leq i < j < k \leq n} | A_{i} \cap A_{j} \cap A_{k} | - \dots + (- 1)^{n - 1} | A_{1} \cap \dots \cap A_{n} |

And in a more compact way:

| ⋃_{i = 1}^{n} A_{i} | = \sum_{\emptyset \neq J \subseteq {1, 2, \dots, n}} (- 1)^{| J | - 1} | ⋂_{j \in J} A_{j} |

The formulation using Venn diagrams

Let the diagram show three sets

A

B

and

C

Then the area of their union

A \cup B \cup C

is equal to the sum of the areas

A

B

and

C

less double-covered areas

A \cap B

A \cap C

B \cap C

, but with the addition of the area covered by three sets

A \cap B \cap C

S (A \cup B \cup C) = S (A) + S (B) + S (C) - S (A \cap B) - S (A \cap C) - S (B \cap C) + S (A \cap B \cap C)

It can also be generalized for an association of

n

sets.

The formulation in terms of probability theory

A_{i}

(i = 1, 2... n)

are events and

P (A_{i})

the probability of an event from

A_{i}

to occur, then the probability of their union (i.e. the probability that at least one of the events occur) is equal to:

\begin{array}{rcl} P (⋃_{i = 1}^{n} A_{i}) & = & \sum_{i = 1}^{n} P (A_{i}) - \sum_{1 \leq i < j \leq n} P (A_{i} \cap A_{j}) + \\ + & \sum_{1 \leq i < j < k \leq n} P (A_{i} \cap A_{j} \cap A_{k}) - \dots + (- 1)^{n - 1} P (A_{1} \cap \dots \cap A_{n}) \end{array}

And in a more compact way:

P (⋃_{i = 1}^{n} A_{i}) = \sum_{\emptyset \neq J \subseteq {1, 2, \dots, n}} (- 1)^{| J | - 1} P (⋂_{j \in J} A_{j})

Proof

For the proof it is convenient to use the mathematical formulation in terms of set theory:

| ⋃_{i = 1}^{n} A_{i} | = \sum_{\emptyset \neq J \subseteq {1, 2, \dots, n}} (- 1)^{| J | - 1} | ⋂_{j \in J} A_{j} |

We want to prove that any element contained in at least one of the sets

A_{i}

will occur in the formula only once (note that elements which are not present in any of the sets

A_{i}

will never be considered on the right part of the formula).

Consider an element

x

occurring in

k \geq 1

sets

A_{i}

. We will show it is counted only once in the formula. Note that:

in terms which $| J | = 1$ , the item $x$ will be counted $+ k$ times;
in terms which $| J | = 2$ , the item $x$ will be counted $- (\binom{k}{2})$ times - because it will be counted in those terms that include two of the $k$ sets containing $x$ ;
in terms which $| J | = 3$ , the item $x$ will be counted $+ (\binom{k}{3})$ times;
$\dots$
in terms which $| J | = k$ , the item $x$ will be counted $(- 1)^{k - 1} \cdot (\binom{k}{k})$ times;
in terms which $| J | > k$ , the item $x$ will be counted zero times;

This leads us to the following sum of binomial coefficients:

T = (\binom{k}{1}) - (\binom{k}{2}) + (\binom{k}{3}) - \dots + (- 1)^{i - 1} \cdot (\binom{k}{i}) + \dots + (- 1)^{k - 1} \cdot (\binom{k}{k})

This expression is very similar to the binomial expansion of

(1 - x)^{k}

(1 - x)^{k} = (\binom{k}{0}) - (\binom{k}{1}) \cdot x + (\binom{k}{2}) \cdot x^{2} - (\binom{k}{3}) \cdot x^{3} + \dots + (- 1)^{k} \cdot (\binom{k}{k}) \cdot x^{k}

When

x = 1

(1 - x)^{k}

looks a lot like

T

. However, the expression has an additional

(\binom{k}{0}) = 1

, and it is multiplied by

- 1

. That leads us to

(1 - 1)^{k} = 1 - T

. Therefore

T = 1 - (1 - 1)^{k} = 1

, what was required to prove. The element is counted only once.

Usage when solving problems

The inclusion-exclusion principle is hard to understand without studying its applications.

First, we will look at three simplest tasks "at paper", illustrating applications of the principle, and then consider more practical problems which are difficult to solve without inclusion-exclusion principle.

Tasks asking to "find the number of ways" are worth of note, as they sometimes lead to polynomial solutions, not necessarily exponential.

A simple task on permutations

Task: count how many permutations of numbers from

0

9

exist such that the first element is greater than

1

and the last one is less than

8

Let's count the number of "bad" permutations, that is, permutations in which the first element is

\leq 1

and/or the last is

\geq 8

We will denote by

X

the set of permutations in which the first element is

\leq 1

and

Y

the set of permutations in which the last element is

\geq 8

. Then the number of "bad" permutations, as on the inclusion-exclusion formula, will be:

| X \cup Y | = | X | + | Y | - | X \cap Y |

After a simple combinatorial calculation, we will get to:

2 \cdot 9! + 2 \cdot 9! - 2 \cdot 2 \cdot 8!

The only thing left is to subtract this number from the total of

10!

to get the number of "good" permutations.

Search This Blog

inclusion_exclusion_principle

theory1