Inclusion–exclusion principle

The principle of inclusion and exclusion (also principle of inclusion and exclusion or Einschluss-/Ausschluss-Verfahren ) is a useful technique for determining the cardinality of a set. It takes place mainly in combinatorics and number theory application.

The principle expresses this, perform the cardinality of an original amount by the cardinalities of its subsets. These are usually easier to determine. Name decisive factor is the procedure in which first by the sum of the sizes not necessarily disjoint subsets, the size of is estimated from above ( inclusion), but then tries to correct this again by subtracting the size of the common intersection of the subsets ( exclusion ).

The principle

It is a known result that for any two finite sets and

Applies. Here one can already recognize the principle of inclusion and exclusion. By cardinality is first estimated by from above. This loss is then corrected by. The purpose of this correction is to subtract the elements again contained both within and in and were thus initially counted twice.

Based on the adjacent figure it can be seen that a generalization to three finite sets

Results.

In general, we want the cardinality of the union of finite sets

Determine. As a first approximation we obtained by inclusion of the sum of the cardinalities. However, this sum is too large in most cases, since we'd elements from the intersection of two sets several times include so

In order we can correct this now by exclusion, the sum over the cardinality of all pairwise intersections even removed. But then applies

Elements because of the cut of three volumes would - though only twice too often counted in the inclusion - by deducted through and through three times again. This is now to be corrected by inclusion, ie by adding the sum of the sizes of all sections of three quantities, leads to

This is followed by exclusion

And so on, which means for example that is summed over all 3- tuples that satisfy the inequality.

Set

It can prove the following general statement. Given a finite set, which can be written as a union of subsets, ie. Denote below on an index set the amount so, where corresponds to the average of all the elements of the index set of designated subsets. Then we have

In other words, considering all possible cuts (except the empty intersection ), this corresponds to the cardinality of the sum of the cardinality of all sections of an odd number of subsets ( inclusion) minus the sum of the cardinality of all sections of an even number of subsets ( exclusion ), formally:

Application

An application of the principle provides the Siebformel of Poincaré and Sylvester and the addition theorem for probabilities:

For the probability of arbitrary events of a probability space is considered:

Due to the property of measures to be additive, can the above mentioned heuristic proof of the principle of inclusion and exclusion, which was conducted with funds from the elementary set theory, applied directly to probabilities.

For example, for three events, and always