Principle of inclusion and exclusion

The principle of inclusion and exclusion (also the principle of inclusion and exclusion or the inclusion-exclusion method) is a helpful technique for determining the power of a set . It is mainly used in combinatorics , number theory and stochastics .

The principle expresses the cardinality of an original set through the cardinalities of its subsets . These are usually easier to determine. It is named after the procedure in which the size is initially estimated from above using the sum of the sizes of not necessarily disjoint subsets (inclusion), but then an attempt is made to correct this again by subtracting the size of the common intersection of the subsets (exclusion) . ${\displaystyle X}$ ${\displaystyle X}$

The principle

Principle of inclusion and exclusion using the example of three sets

It is a well-known result that for every two finite sets and ${\displaystyle A}$ ${\displaystyle B}$

${\displaystyle |A\cup B|=|A|+|B|-|A\cap B|}$

applies. Here you can already see the principle of inclusion and exclusion. By the cardinality is first of of estimated above. This too high number is then corrected by subtracting . The purpose of this correction is to subtract those elements that are contained in as well as in and were thus initially counted twice. ${\displaystyle |A|+|B|}$ ${\displaystyle |A\cup B|}$ ${\displaystyle |A\cap B|}$ ${\displaystyle A}$ ${\displaystyle B}$

The figure on the right shows that a generalization to three finite sets

${\displaystyle |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|}$

results.

In general, we want the cardinality of the union of finite sets ${\displaystyle n}$

${\displaystyle X=A_{1}\cup A_{2}\cup \dotsb \cup A_{n}}$

determine. As a first approximation, we get the sum of the cardinalities of the . However, this sum can be too large, since we would count elements from the intersection of two sets several times: ${\displaystyle A_{i}}$ ${\displaystyle A_{i}\cap A_{j}}$

${\displaystyle |X|\leq \sum _{1\leq i\leq n}|A_{i}|}$

To correct this, we can now subtract the sum of the cardinalities of the intersections of all pairs of sets by means of exclusion. Then:

${\displaystyle |X|\geq \sum _{1\leq i\leq n}|A_{i}|~-\sum _{1\leq i<j\leq n}|A_{i}\cap A_{j}|}$

For elements of the cut three levels would - although only two times too often counted in the inclusion - by , by and by three times removed again. Correcting this by inclusion, i.e. by adding the sum of the size of all sections from three sets, results in: ${\displaystyle A_{i}\cap A_{j}\cap A_{k}}$ ${\displaystyle |A_{i}\cap A_{j}|}$ ${\displaystyle |A_{i}\cap A_{k}|}$ ${\displaystyle |A_{j}\cap A_{k}|}$

${\displaystyle |X|\leq \sum _{1\leq i\leq 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}|}$

This is followed by exclusion

${\displaystyle |X|\geq \sum _{1\leq i\leq 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}|~-\sum _{1\leq i<j<k<l\leq n}|A_{i}\cap A_{j}\cap A_{k}\cap A_{l}|}$

and so on, where, for example, means that all ordered triples are summed that obey the inequalities . ${\displaystyle \sum _{1\leq i<j<k\leq n}}$ ${\displaystyle (i,j,k)}$ ${\displaystyle 1\leq i<j<k\leq n}$

sentence

The following general statement can be proven.

Given a finite set that can be written as a union of subsets , i. H. . In the following, for an index set, the set denotes the intersection of all subsets identified by the elements of the index set, i.e.: ${\displaystyle X}$ ${\displaystyle n}$ ${\displaystyle A_{1},A_{2},\dotsc ,A_{n}}$ ${\displaystyle X=\bigcup _{i=1}^{n}A_{i}}$ ${\displaystyle I\subseteq \{1,2,\dotsc ,n\}}$ ${\displaystyle A_{I}}$

${\displaystyle A_{I}:=\bigcap _{i\in I}A_{i}}$ with the special case ${\displaystyle A_{\emptyset }=X}$

Then:

${\displaystyle |X|=\sum _{\emptyset \not =I\subseteq \{1,\dotsc ,n\}}\left(-1\right)^{|I|+1}|A_{I}|}$

In other words: If one considers all possible cuts (except for the empty cut ), the cardinality is equal to the sum of the cardinality of all cuts of an odd number of subsets (inclusion) minus the sum of the cardinality of all cuts of an even number of subsets (exclusion ), formal: ${\displaystyle A_{I}}$ ${\displaystyle A_{\emptyset }}$ ${\displaystyle X}$

${\displaystyle |X|=\sum _{{I\subseteq \{1,\dotsc ,n\},} \atop {|I|~{\text{ungerade}}}}|A_{I}|-\sum _{{\emptyset \not =I\subseteq \{1,\dotsc ,n\},} \atop {|I|~{\text{gerade}}}}|A_{I}|}$

application

The sieving formula by Poincaré and Sylvester , also called the addition theorem for probabilities , provides an application of the principle :

The following applies to the probability of any event from a probability space : ${\displaystyle A_{i}}$ ${\displaystyle (\Omega ,\Sigma ,P)}$

${\displaystyle P\left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{k=1}^{n}\left((-1)^{k+1}\!\!\sum _{I\subseteq \{1,\dotsc ,n\}, \atop |I|=k}\!\!\!\!P\left(\bigcap _{i\in I}A_{i}\right)\right)}$

Because of the additivity of measures , the heuristic proof given above for the principle of inclusion and exclusion, which was carried out using the means of elementary set theory, can be transferred directly to probabilities.

For example, for three events , and always ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$

${\displaystyle {P(A\cup B\cup C)=P(A)+P(B)+P(C)-P(A\cap B)-P(A\cap C)-P(B\cap C)+P(A\cap B\cap C)}}$.

In general, this statement also applies to finite content on rings .

example

→ Main article : Fixed point free permutation

In the pre-Christmas tradition of elves, a group gives each other presents. Everyone gives gifts to exactly one person and in turn is given gifts by exactly one person. It is determined randomly by lot who receives which gift. Ideally, each should receive someone else's gift. However, it can happen that someone accidentally receives their own gift. For the person concerned, the surprise would be over. But how likely is this to happen to a group of people? ${\displaystyle n}$

Expressed mathematically, one would like to determine the probability of event A: = "At least one person receives their own gift". This is equivalent to the fact that at least one of the events A _i  : = “Person i receives their own gift” applies to, where the number is the number of people who take part in the elf. The right term of the sieve formula ${\displaystyle i\in \{1,\dotsc ,n\}}$ ${\displaystyle n}$

${\displaystyle P\left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{k=1}^{n}\left((-1)^{k+1}\!\!\sum _{I\subseteq \{1,\dotsc ,n\}, \atop |I|=k}\!\!\!\!P\left(\bigcap _{i\in I}A_{i}\right)\right)}$

can be simplified too

${\displaystyle {nP(A_{1})-{\binom {n}{2}}P(A_{1}\cap A_{2})+{\binom {n}{3}}P(A_{1}\cap A_{2}\cap A_{3})-{\binom {n}{4}}P(A_{1}\cap A_{2}\cap A_{3}\cap A_{4})}}$

${\displaystyle {+{\binom {n}{5}}P(A_{1}\cap A_{2}\cap A_{3}\cap A_{4}\cap A_{5})-\dotsb +\dotsb +(-1)^{n+1}P(A_{1}\cap \dotsb \cap A_{n})}}$,

since in this example the probabilities of all intersections with the same number of subsets are the same. The probability that certain people will each draw their own gifts is ${\displaystyle k}$

${\displaystyle P(A_{1}\cap A_{2}\cap A_{3}\cap \dotsb \cap A_{k})={\frac {1}{n\cdot (n-1)\cdot (n-2)\cdot \dotsm \cdot (n-k+1)}}}$.

With the help of the definition of the binomial coefficient one obtains

${\displaystyle {P(A_{1}\cup \dotsb \cup A_{n})=n\cdot {\frac {1}{n}}-{\frac {n(n-1)}{1\cdot 2}}\cdot {\frac {1}{n(n-1)}}+{\frac {n(n-1)(n-2)}{1\cdot 2\cdot 3}}\cdot {\frac {1}{n(n-1)(n-2)}}}}$

${\displaystyle {-{\frac {n(n-1)(n-2)(n-3)}{1\cdot 2\cdot 3\cdot 4}}\cdot {\frac {1}{n(n-1)(n-2)(n-3)}}+{\frac {n(n-1)(n-2)(n-3)(n-4)}{1\cdot 2\cdot 3\cdot 4\cdot 5}}\cdot {\frac {1}{n(n-1)(n-2)(n-3)(n-4)}}}}$

${\displaystyle {-\dotsb +\dotsb -\dotsb +\dotsb +(-1)^{n+1}\cdot {\frac {1}{1\cdot 2\cdot 3\cdot \dotsm \cdot n}}}}$.

After shortening the fractions it results

${\displaystyle {P(A_{1}\cup \dotsb \cup A_{n})=1-{\frac {1}{1\cdot 2}}+{\frac {1}{1\cdot 2\cdot 3}}-{\frac {1}{1\cdot 2\cdot 3\cdot 4}}+{\frac {1}{1\cdot 2\cdot 3\cdot 4\cdot 5}}-\dotsb +\dotsb -\dotsb +\dotsb +(-1)^{n+1}\cdot {\frac {1}{1\cdot 2\cdot 3\cdot \dotsm \cdot n}}}}$.

With the sums notation this can be abbreviated as express. ${\displaystyle P(A_{1}\cup \dotsb \cup A_{n})=1-\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}}$

With large groups, quite a few summands have to be added and the factorial quickly becomes extremely large. In this case it is useful to form the limit of this sum for : ${\displaystyle k!}$ ${\displaystyle n\to \infty }$

${\displaystyle \lim _{n\to \infty }\left(1-\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}\right)=1-\sum _{k=0}^{\infty }{\frac {(-1)^{k}}{k!}}=1-e^{-1}=1-{\frac {1}{e}}\approx 63{,}2\,\%}$

The series is the evaluation of the Taylor series with the expansion point of the natural exponential function at the point , which is why the solution is simplified to the whole . This value can be viewed as an approximation for large . In large groups, the probability is roughly that at least one person will receive their own gift. ${\displaystyle 0}$ ${\displaystyle x=-1}$ ${\displaystyle 1-{\frac {1}{e}}}$ ${\displaystyle n}$ ${\displaystyle 63{,}2\,\%}$

See also

• Bonferroni inequality
• Drawer principle

Web links

Wikiversity: A lecture on the sieve formula as part of a course on discrete mathematics  - course materials

literature

• Norbert Henze : Stochastics for beginners. An introduction to the fascinating world of chance. Springer Spectrum, 10th edition, Wiesbaden 2016, pp. 70–76.
• Klaus Dohmen: Improved Bonferroni Inequalities via Abstract Tubes - Inequalities and Identities of Inclusion-Exclusion Type. Springer-Verlag, 2003, ISBN 3-540-20025-8 .
• Stasys Jukna: Extremal Combinatorics. Springer, May 2001, ISBN 3-540-66313-4 .

Individual evidence

1. ↑ Correspondingly in slightly different clothing in: Norbert Henze: Stochastik für Einsteiger. An introduction to the fascinating world of chance. Springer Spectrum, 1st edition, Wiesbaden 1997, pp. 74-77.
2. ↑ Stefan Bartz: Self-watering in 2 of 3 games . In: Stochastics in School . No. 33 , 2013 ( stefanbartz.de [PDF; 684 kB ]).