Inclusion–exclusion principle

hbghlyj

Other forms – inclusion-exclusion principle – Wikipedia
The principle is sometimes stated in the form that says that if$$g(A)=\sum _{S\subseteq A}f(S)$$then$$f(A)=\sum _{S\subseteq A}(-1)^{|A|-|S|}g(S)\tag{$\ast\ast$}$$ The combinatorial and the probabilistic version of the inclusion–exclusion principle are instances of (⁎⁎).

Proof

Take $\underline {m}=\{1,2,\ldots ,m\}$, $f(\underline {m})=0$, and $$ f(S)=\left|\bigcap _{i\in {\underline {m}}\setminus S}A_{i}\setminus \bigcup _{i\in S}A_{i}\right|{\text{ and }}f(S)=\mathbb {P} \left(\bigcap _{i\in {\underline {m}}\setminus S}A_{i}\setminus \bigcup _{i\in S}A_{i}\right)$$ respectively for all sets $S$ with $S\subsetneq \underline {m}$. Then we obtain $$ g(A)=\left|\bigcap _{i\in {\underline {m}}\setminus A}A_{i}\right|,\quad g({\underline {m}})=\left|\bigcup _{i\in {\underline {m}}}A_{i}\right|{\text{ and }}g(A)=\mathbb {P} \left(\bigcap _{i\in {\underline {m}}\setminus A}A_{i}\right),~~g({\underline {m}})=\mathbb {P} \left(\bigcup _{i\in {\underline {m}}}A_{i}\right)$$ respectively for all sets $A$ with $A\subsetneq \underline {m}$. This is because elements $a$ of ${\displaystyle \cap _{i\in {\underline {m}}\setminus A}A_{i}}$ can be contained in other $A_{i}$ ($A_{i}$ with $i\in A$) as well, and the ${\displaystyle \cap \setminus \cup }$-formula runs exactly through all possible extensions of the sets ${\displaystyle \{A_{i}\mid i\in {\underline {m}}\setminus A\}}$ with other $A_{i}$, counting $a$ only for the set that matches the membership behavior of $a$, if $S$ runs through all subsets of $A$ (as in the definition of $g(A)$). Since $f(\underline {m})=0$, we obtain from (⁎⁎) with $A=\underline {m}$ that $$\sum _{{\underline {m}}\supseteq T\supsetneq \varnothing }(-1)^{|T|-1}g({\underline {m}}\setminus T)=\sum _{\varnothing \subseteq S\subsetneq {\underline {m}}}(-1)^{m-|S|-1}g(S)=g({\underline {m}})$$ and by interchanging sides, the combinatorial and the probabilistic version of the inclusion–exclusion principle follow.

If one sees a number $n$ as a set of its prime factors, then (⁎⁎) is a generalization of Möbius inversion formula for square-free natural numbers. Therefore, (⁎⁎) is seen as the Möbius inversion formula for the incidence algebra of the partially ordered set of all subsets of $A$.

For a generalization of the full version of Möbius inversion formula, (⁎⁎) must be generalized to multisets. For multisets instead of sets, (⁎⁎) becomes $$f(A)=\sum _{S\subseteq A}\mu (A-S)g(S)\tag{$\ast\!\ast\!\ast$}$$ where $A - S$ is the multiset for which $(A-S)\uplus S=A$, and

• $μ(S) = 1$ if $S$ is a set (i.e. a multiset without double elements) of even cardinality.
• $μ(S) = −1$ if $S$ is a set (i.e. a multiset without double elements) of odd cardinality.
• $μ(S) = 0$ if $S$ is a proper multiset (i.e. $S$ has double elements).

Notice that ${\displaystyle \mu (A-S)}$ is just the ${\displaystyle (-1)^{|A|-|S|}}$ of (⁎⁎) in case $A - S$ is a set.

Proof of (⁎⁎⁎)

Substitute $$g(S)=\sum _{T\subseteq S}f(T)$$ on the right hand side of (⁎⁎⁎). Notice that $f(A)$ appears once on both sides of (⁎⁎⁎). So we must show that for all $T$ with $T\subsetneq A$, the terms $f(T)$ cancel out on the right hand side of (⁎⁎⁎). For that purpose, take a fixed $T$ such that $T\subsetneq A$ and take an arbitrary fixed $a\in A$ such that ${\displaystyle a\notin T}$.

Notice that $A - S$ must be a set for each positive or negative appearance of $f(T)$ on the right hand side of (⁎⁎⁎) that is obtained by way of the multiset $S$ such that $T\subseteq S\subseteq A$. Now each appearance of $f(T)$ on the right hand side of (⁎⁎⁎) that is obtained by way of $S$ such that $A - S$ is a set that contains $a$ cancels out with the one that is obtained by way of the corresponding $S$ such that $A - S$ is a set that does not contain $a$. This gives the desired result.

hbghlyj

The inclusion–exclusion principle is widely used and only a few of its applications can be mentioned here.

Counting derangements

Main article: Derangement

A well-known application of the inclusion–exclusion principle is to the combinatorial problem of counting all derangements of a finite set. A derangement of a set $A$ is a bijection from $A$ into itself that has no fixed points. Via the inclusion–exclusion principle one can show that if the cardinality of $A$ is $n$, then the number of derangements is $[n! / e]$ where $[x]$ denotes the nearest integer to $x$; a detailed proof is available here and also see the examples section above.

The first occurrence of the problem of counting the number of derangements is in an early book on games of chance: Essai d'analyse sur les jeux de hazard by P. R. de Montmort (1678 – 1719) and was known as either Montmort's problem or by the name he gave it, problème des rencontres. The problem is also known as the hatcheck problem.

The number of derangements is also known as the subfactorial of $n$, written $!n$. It follows that if all bijections are assigned the same probability then the probability that a random bijection is a derangement quickly approaches $1/e$ as $n$ grows.

Counting intersections

The principle of inclusion–exclusion, combined with De Morgan's law, can be used to count the cardinality of the intersection of sets as well. Let ${\displaystyle {\overline {A_{k}}}}$ represent the complement of $A_k$ with respect to some universal set $A$ such that ${\displaystyle A_{k}\subseteq A}$ for each $k$. Then we have $$\bigcap _{i=1}^{n}A_{i}={\overline {\bigcup _{i=1}^{n}{\overline {A_{i}}}}}$$ thereby turning the problem of finding an intersection into the problem of finding a union.

Graph coloring

The inclusion exclusion principle forms the basis of algorithms for a number of NP-hard graph partitioning problems, such as graph coloring.

A well known application of the principle is the construction of the chromatic polynomial of a graph.

Bipartite graph perfect matchings

The number of perfect matchings of a bipartite graph can be calculated using the principle.

Number of onto functions

Given finite sets $A$ and $B$, how many surjective functions (onto functions) are there from $A$ to $B$? Without any loss of generality we may take $A = \{1, ..., k\}$ and $B = \{1, ..., n\}$, since only the cardinalities of the sets matter. By using $S$ as the set of all functions from $A$ to $B$, and defining, for each $i$ in $B$, the property $P_i$ as "the function misses the element $i$ in $B$" ($i$ is not in the image of the function), the principle of inclusion–exclusion gives the number of onto functions between $A$ and $B$ as: $$\sum _{{j=0}}^{{n}}{\binom {n}{j}}(-1)^{j}(n-j)^{k}.$$

Permutations with forbidden positions

A permutation of the set $S = \{1, ..., n\}$ where each element of $S$ is restricted to not being in certain positions (here the permutation is considered as an ordering of the elements of $S$) is called a permutation with forbidden positions. For example, with $S = \{1,2,3,4\}$, the permutations with the restriction that the element 1 can not be in positions 1 or 3, and the element 2 can not be in position 4 are: 2134, 2143, 3124, 4123, 2341, 2431, 3241, 3421, 4231 and 4321. By letting $A_i$ be the set of positions that the element $i$ is not allowed to be in, and the property $P_i$ to be the property that a permutation puts element $i$ into a position in $A_i$, the principle of inclusion–exclusion can be used to count the number of permutations which satisfy all the restrictions. In the given example, there are $12 = 2(3!)$ permutations with property $P_1$, $6 = 3!$ permutations with property $P_2$ and no permutations have properties $P_3$ or $P_4$ as there are no restrictions for these two elements. The number of permutations satisfying the restrictions is thus: $$4! − (12 + 6 + 0 + 0) + (4) = 24 − 18 + 4 = 10.$$ The final $4$ in this computation is the number of permutations having both properties $P_1$ and $P_2$. There are no other non-zero contributions to the formula.

Stirling numbers of the second kind

Main article: Stirling numbers of the second kind

The Stirling numbers of the second kind, $S(n,k)$ count the number of partitions of a set of $n$ elements into $k$ non-empty subsets (indistinguishable boxes). An explicit formula for them can be obtained by applying the principle of inclusion–exclusion to a very closely related problem, namely, counting the number of partitions of an $n$-set into $k$ non-empty but distinguishable boxes (ordered non-empty subsets). Using the universal set consisting of all partitions of the $n$-set into $k$ (possibly empty) distinguishable boxes, $A_1, A_2, …, A_k$, and the properties $P_i$ meaning that the partition has box $A_i$ empty, the principle of inclusion–exclusion gives an answer for the related result. Dividing by $k!$ to remove the artificial ordering gives the Stirling number of the second kind: $$S(n,k)={\frac {1}{k!}}\sum _{t=0}^{k}(-1)^{t}{\binom {k}{t}}(k-t)^{n}.$$

Rook polynomials

Main article: Rook polynomial

A rook polynomial is the generating function of the number of ways to place non-attacking rooks on a board $B$ that looks like a subset of the squares of a checkerboard; that is, no two rooks may be in the same row or column. The board $B$ is any subset of the squares of a rectangular board with $n$ rows and m columns; we think of it as the squares in which one is allowed to put a rook. The coefficient, $r_k(B)$ of $x_k$ in the rook polynomial $RB(x)$ is the number of ways $k$ rooks, none of which attacks another, can be arranged in the squares of $B$. For any board $B$, there is a complementary board $B'$ consisting of the squares of the rectangular board that are not in $B$. This complementary board also has a rook polynomial ${\displaystyle R_{B'}(x)}$ with coefficients ${\displaystyle r_{k}(B').}$ It is sometimes convenient to be able to calculate the highest coefficient of a rook polynomial in terms of the coefficients of the rook polynomial of the complementary board. Without loss of generality we can assume that $n ≤ m$, so this coefficient is $r_n(B)$. The number of ways to place $n$ non-attacking rooks on the complete $n × m$ "checkerboard" (without regard as to whether the rooks are placed in the squares of the board $B$) is given by the falling factorial: $$(m)_{n}=m(m-1)(m-2)\cdots (m-n+1).$$ Letting $P_i$ be the property that an assignment of $n$ non-attacking rooks on the complete board has a rook in column $i$ which is not in a square of the board $B$, then by the principle of inclusion–exclusion we have: $$r_{n}(B)=\sum _{t=0}^{n}(-1)^{t}(m-t)_{n-t}r_{t}(B').$$

Euler's phi function

Main article: Euler's totient function

Euler's totient or phi function, $φ(n)$ is an arithmetic function that counts the number of positive integers less than or equal to $n$ that are relatively prime to $n$. That is, if $n$ is a positive integer, then $φ(n)$ is the number of integers $k$ in the range $1 ≤ k ≤ n$ which have no common factor with $n$ other than 1. The principle of inclusion–exclusion is used to obtain a formula for $φ(n)$. Let $S$ be the set $\{1, …, n\}$ and define the property $P_i$ to be that a number in $S$ is divisible by the prime number $p_i$, for $1 ≤ i ≤ r$, where the prime factorization of $$n=p_{1}^{{a_{1}}}p_{2}^{{a_{2}}}\cdots p_{r}^{{a_{r}}}.$$ Then, $$ \varphi (n)=n-\sum _{i=1}^{r}{\frac {n}{p_{i}}}+\sum _{1\leqslant i< j\leqslant r}{\frac {n}{p_{i}p_{j}}}-\cdots =n\prod _{i=1}^{r}\left(1-{\frac {1}{p_{i}}}\right).$$

hbghlyj

The number of perfect matchings of a bipartite graph can be calculated using the principle.

lesson20-2.pdf (Number of perfect matchings)

hbghlyj

The classical rooks problem immediately gives the value of $r_8$, the coefficient in front of the highest order term of the rook polynomial. Indeed, its result is that 8 non-attacking rooks can be arranged on an $8 × 8$ chessboard in $r_8 = 8! = 40320$ ways.

Let us generalize this problem by considering an $m × n$ board, that is, a board with $m$ ranks (rows) and $n$ files (columns). The problem becomes: In how many ways can one arrange $k$ rooks on an $m × n$ board in such a way that they do not attack each other?

It is clear that for the problem to be solvable, $k$ must be less or equal to the smaller of the numbers $m$ and $n$; otherwise one cannot avoid placing a pair of rooks on a rank or on a file. Let this condition be fulfilled. Then the arrangement of rooks can be carried out in two steps. First, choose the set of $k$ ranks on which to place the rooks. Since the number of ranks is $m$, of which $k$ must be chosen, this choice can be done in ${\binom {m}{k}}$ ways. Similarly, the set of $k$ files on which to place the rooks can be chosen in ${\binom {n}{k}}$ ways. Because the choice of files does not depend on the choice of ranks, according to the products rule there are ${\binom {m}{k}}{\binom {n}{k}}$ ways to choose the square on which to place the rook.

However, the task is not yet finished because $k$ ranks and $k$ files intersect in $k^2$ squares. By deleting unused ranks and files and compacting the remaining ranks and files together, one obtains a new board of $k$ ranks and $k$ files. It was already shown that on such board $k$ rooks can be arranged in $k!$ ways (so that they do not attack each other). Therefore, the total number of possible non-attacking rooks arrangements is:$$r_{k}={\binom {m}{k}}{\binom {n}{k}}k!={\frac {n!m!}{k!(n-k)!(m-k)!}}.$$For instance, 3 rooks can be placed on a conventional chessboard (8×8) in $\textstyle {{\frac {8!8!}{3!5!5!}}}=18,816$ ways. For $k = m = n$, the above formula gives $r_k = n!$ that corresponds to the result obtained for the classical rooks problem.

The rook polynomial with explicit coefficients is now:$$R_{{m,n}}(x)=\sum _{{k=0}}^{{\min(m,n)}}{\binom {m}{k}}{\binom {n}{k}}k!x^{k}=\sum _{{k=0}}^{{\min(m,n)}}{\frac {n!m!}{k!(n-k)!(m-k)!}}x^{k}.$$If the limitation "rooks must not attack each other" is removed, one must choose any $k$ squares from $m × n$ squares. This can be done in:$${\binom {mn}{k}}={\frac {(mn)!}{k!(mn-k)!}}$$ ways.

If the $k$ rooks differ in some way from each other, e.g., they are labelled or numbered, all the results obtained so far must be multiplied by $k!$, the number of permutations of $k$ rooks.


Connection to matrix permanents
For incomplete square $n × n$ boards, (i.e. rooks are not allowed to be played on some arbitrary subset of the board's squares) computing the number of ways to place $n$ rooks on the board is equivalent to computing the permanent of a 0–1 matrix.

en.wikipedia.org/wiki/Rook_polynomial

Czhang271828

An exercise from Stanley's Enumerative Combinatorics:

Explain why the Principle of Inclusion-Exclusion has the numerical value
\[
8.53973422267356706546\cdots.
\]