The Principle of Inclusion-Exclusion

The principle of inclusion-exclusion is an important result of combinatorial calculus which finds applications in various fields, from Number Theory to Probability, Measurement Theory and others. In this article we consider different formulations of the principle, followed by some applications and exercises.

For further information, see for example ^[1] and ^[2].

---

1) Principle of inclusion-exclusion

Given \(n\) sets of finite cardinality \(S_ {1}, S_ {2},\cdots, S_ {n}\), we denote by \(S\) the union of the \(n\) sets, i.e. \(S = S_ {1} \cup S_ {2} \cup \cdots S_ {n}\). It is often necessary to determine the cardinality of the set \(S\), that is the number of distinct elements of \(S\). The inclusion-exclusion principle, expressed in the following theorem, allows to carry out this calculation in a simple way.

Theorem 1.1
The cardinality of the union set \(S\) is given by

\[ | S | = \sum\limits_{k = 1} ^ {n} (-1) ^ {k + 1} \cdot C (k) \]

where \(C (k) = | {S_ {i_ {1}}} \cap \cdots \cap S_ {i_ {k}} |\) with \( 1 \le i_ {1} \lt i_{2} \cdots \lt i_{k} \le n \).

Expanding the compact expression of the theorem we have:

\[ |S_{1} \cup \cdots \cup S_{n}|  =    \\ |S_{1}| + |S_{2}| + \cdots +|S_{n}| \\ – |S_{1} \cap S_{2}| – \cdots -|S_{n-1} \cap S_{n}|   \\  +|S_{1} \cap S_{2} \cap S_{3}| + \cdots + |S_{n-2} \cap S_{n-1} \cap S_{n}|  \\   \vdots   \\ + (-1)^{n-1} |S_{1} \cap S_{2} \cdots \cap S_{n}|\\ \]

The theorem is an extension to the general case of the obvious property in the case of two sets A, B. To calculate the cardinality of the union set \(A \cup B\) we need to add the cardinality of the single sets, but then we need to subtract the number of the common elements, that is the elements belonging to the intersection set. In symbols:

\[ |A \cup B| = |A| + |B| – |A \cap B| \]

In the case of three sets (A, B, C) we have:

\[ \begin{split} |A \cup B \cup C| &=|A| + |B| + |C| \\ & – |A \cap B| – |A \cap C| – |B \cap C| \\ & + |A \cap B \cap C| \end{split} \]

The following graph illustrates the situation in the case of three sets:

An equivalent formulation of the inclusion-exclusion principle is the following:

Theorem 1.2
Let \(S\) be a set of \(N\) elements and \(S_ {1}, S_ {2}, \cdots , S_ {r}\) be arbitrary subsets of \(S\) containing respectively \(N_ {1}, N_ {2}, \cdots , N_ {r}\) elements. For \(1\le i \lt j \lt l \le r\), let \(S_ {ij … l}\) be the intersection set of \(S_ {i}, S_ {j}, \cdots , S_ {l }\) and let \(N_ {ij..l}\) be the number of elements of \(S_ {ij \cdots l}\).
Then the number of elements of \(S\) that do not belong to any of the \(S_ {1}, \cdots , S_ {r}\) is:

\[ T = N – \sum_{1 \le i \le r}N_{i} + \sum_{1 \le i \lt j \le r }N_{ij} – \cdots + (-1)^{r} N_{12 \cdots r} \]

Proof
We denote by \(s\) a generic element of \(S\) which belongs to exactly \(m\) of the sets \(S_ {1}, S_ {2}, \cdots , S_ {r}\). If \(m = 0\) then \(s\) is counted exactly once in the formula, precisely in the first term \(N\). If \(0 \lt m \le r\), then \(s\) is counted once in \(N\), it’s counted \(\binom {m} {1}\) times in the terms \(N_ {i}\), \(\binom {m} {2}\) in terms \(N_ {ij}\), etc. So, since \(\binom {m} {0} = 1\), the contribution to the total \(T\) is:

\[
\binom{m}{0} – \binom{m}{1} + \binom{m}{2} – \cdots + (-1)^{m}\binom{m}{m}= (1-1)^{m}=0
\]

for Newton’s binomial theorem.
A third equivalent statement can be given in terms of probability. Instead of sets we have events, which are nothing but possible sets of results.

Theorem 1.3
Let \(n\) events \(E_ {1}, E_ {2}, \cdots, E_ {n}\) be given. Then the probability that at least one of the \(n\) events occurs is:

\[ \begin{align} P\{E_{1} \cup E_{2} \cup \cdots \cup E_{n}\} = & \sum_{1 \le i \le n} P\{E_{i}\} \\ & – \sum_{1 \le i_{1} \lt i_{2} \le n}P\{E_{i_{1}} \cap E_{i_{2}}\} \\ & + \sum_{1 \le i_{1} \lt i_{2} \lt i_{3} \le n} P\{E_{i_{1}} \cap E_{i_{2}} \cap E_{i_{3}}\} \\ & \quad \vdots \\ & + (-1)^{n+1}P\{E_{1}\cap E_{2}\cap \cdots \cap E_{n}\} \end{align} \]

Exercise
A dice is thrown \(n\) times. Determine the probability that all six faces appear.

Solution
The probability of the event \(E\) is :

\[ P(E)= \dfrac{6^{n} – 6 \cdot 5^{n} +15 \cdot 4^{n} – 20 \cdot 3^{n} +15 \cdot 2^{n} – 6}{6^{n}} \]

Let us now look at some applications of the inclusion-exclusion principle.

---

2) Chromatic polynomial of a graph

A graph \(G\) consists of a pair of sets \((V, E)\), where \(V\) is a set of nodes or vertices, and \(E\) is a set of arcs or edges, each edge being defined by a pair of vertices. Two vertices are adjacent if there exists an edge to which they are both incident.
A graph is said to be simple if it doesn’t have multiple arcs between two vertices and has no loops, or edges joining a given vertex with itself. A graph is connected if, for each pair of vertices \((u, v)\), there is a path that connects them. An unconnected graph consists of a finite number of connected components.
Given a set \(Q\) of colors, a coloring of a graph is an assignment of colors to each of the vertices. The coloring is called proper if no two adjacent vertices share a common color.

Theorem 2.1
For each graph \(G = (V, E)\), it’s possible to define a polynomial \(P (x)\) such that, for any natural number \(q\), \(P (q)\) represents the number of proper colorings of the graph \(G\) with \(q\) colors.

Proof
Let us denote with \(X\) the set of all the colorings, proper and not. Then we have \(| X | = q ^ {n}\), where \(n\) is the number of vertices.
For each side \(l\) of the graph, we denote by \(A_ {l}\) the set of possible colorings for which the vertices of the side \(l\) have the same color. The proper colourings are those that are not contained in any of the sets \(A_ {l}\).
Given a set \(I \subseteq E\), we count the colors contained in \(A_ {I}\). If we consider the graph \((V, I)\), then a coloring in \(A_ {I}\) assigns the same color to all vertices in the same connected component of the graph; so if the number of the connected components is \(c (I)\), we have \(| A_ {I} | = q^{c(I)}\).
We now apply the principle of inclusion-exclusion; the number of proper colourings is

\[ P_{X}(q) = \sum_{I \subseteq E} (-1)^{|I|}q^{c(I)} \]

It’s a polynomial in the variable \(q\); the main term is \( q ^ n\) and is relative to the the case \(I = \emptyset)\), when \(I\) is the empty set.
The polynomial \(P_ {X}\) is called the chromatic polynomial of the graph \(G = (V, E)\).

Esercise 2.1
Compute the chromatic polynomial in the following cases:

Solution
Triangle: \(P(q)= q (q-1) (q-2)\)
Square: \(P (q) = q ^ {4} -4q ^ {3} + 6q ^ {2} -3q\)
Square with diagonals: \(P (q) = q ^ {4} -6q ^ {3} + 11q ^ {2} -6q\)

---

3) The number of surjective functions

Given a set \(A\) of \(m\) elements and a set \(B\) of \(n\) elements, it’s evident that the total number of functions from \(A\) to \(B\) is equal to \(n ^ {m}\).
A function \(f: A \rightarrow B\) is called surjective if:

\[ \forall {b} \in B \quad \exists a \in A : f(a)=b \]

Exercise
Determine the total number of surjective functions between sets A and B, if \(m \ge n\).

Hint
Apply the principle of inclusion-exclusion, excluding from the total of functions \(n ​​^ {m}\) those that assume a number of different values ​​less than \(n\).

Solution
The cardinality of the set \(Z\) of the surjective functions between \(A\) and \(B\) is:

\[ |Z| = n^{m} – \binom{n}{1}(n-1)^{m} + \binom{n}{2} (n-2)^{m} – \cdots + (-1)^{n-1}\binom{n}{n-1}m \]

---

4) Other exercises

Exercise 4.1
Determine the number of solutions of the equation \(x + y + z = 15\), where \(x, y, z\) are non-negative integers with the condition that \(z \le 3\).

Solution
If we neglect for a moment the constraint on \(z\), it’s a problem about finding the combinations with repetition of objects taken in groups of \(15\).
Recall that the number of combinations with repetition of \(n\) objects taken in groups of \(k\) is given by the following formula:

\[ C_{n,k}^{r} = \binom{n+k-1}{k} \]

In our case

\[ C_{3,15}^{r} = \binom{17}{2} = \binom{17}{15} \]

Since we must exclude solutions with \(z \ge 4\), first we calculate, with the same method, the solutions of the equation without constraints \(x + y + (4+ z_ {0}) = 15\), that is \(x + y + z_ {0} = 11 \). Then we compute the difference between the two results and we get that there are \(58\) possible solutions of the constrained equation.

Exercise 4.2
Given the number \(165\), determine the number of integers from \(1\) to \(165\) that have common non-trivial divisors (other than \(1\)) with \(165\).

Solution
The factorization of \(165\) is \(165=3 \cdot 5 \cdot 11\). Applying the inclusion-exclusion principle we find that the number searched is \(85\).

Exercise 4.3
How many positive integers less than \(1000\) are there that are not divisible by 5 or even by 11?

Solution
Let \(A\) be the set of numbers \(\lt 1000\), multiples of \(5\). Let \(B\) be the set of numbers \(<1000\) multiples of \(11\). We have \(| A | = \lfloor \frac {999} {5} \rfloor = 199\), \(| B | = \lfloor \frac {999} {11} \rfloor = 90\). The set \(A \cap B\) contains the numbers \(<1000\) such that they are multiples of \(5 \cdot 11 = 55\); then \(| A \cap B | = \lfloor \frac {999} {55} \rfloor = 18\). For the principle of inclusion-exclusion: \(| A \cup B | = 199 + 90-18\). To answer the problem it’s enough to do \(999- (199 + 90-18) = 728\).

Exercise 4.4
In a group of 100 people, 70 have a Mercedes and 50 have a Fiat. What can you say about the number of people who own both a Mercedes and a Fiat?

Solution
We indicate the groups of Mercedes and Fiat owners with \(A\) and \(B\). By hypothesis we have: \(| A | = 70 \quad | B | = 50\). For the inclusion-exclusion principle we have:
\(| A \cup B| = | A | + | B | – | A \cap B |\).
Now \(| A \cup B |\) cannot be greater than \(100\).
So we can deduce that

\[ 100 \ge 70 + 50 – | A \cap B \]

and therefore

\[ A \cap B | \ge 70 + 50-100 = 20 \]

So, in this case, we are unable to give a single answer but we can be sure that there are at least \(20\) people who own both types of cars.

---

Bibliography

^[1]William Feller – An introduction to Probability Theory and its applications, Vol. I (Wiley)

^[2]S. Lipschutz – Theory and problems of Discrete Mathematics (McGraw-Hill)