Inclusion–exclusion Principle

In combinatorics, the inclusion–exclusion principle (also known as the sieve principle) is an equation relating the sizes of two sets and their union. It states that if A and B are two (finite) sets, then

The meaning of the statement is that the number of elements in the union of the two sets is the sum of the elements in each set, respectively, minus the number of elements that are in both. Similarly, for three sets A, B and C,

This can be seen by counting how many times each region in the figure to the right is included in the right hand side.

More generally, for finite sets A1, ..., An, one has the identity

\begin{align} \biggl|\bigcup_{i=1}^n A_i\biggr| & {} =\sum_{i=1}^n\left|A_i\right| -\sum_{i,j\,:\,1 \le i < j \le n}\left|A_i\cap A_j\right| \\ & {}\qquad +\sum_{i,j,k\,:\,1 \le i < j < k \le n}\left|A_i\cap A_j\cap A_k\right|-\ \cdots\ + \left(-1\right)^{n-1} \left|A_1\cap\cdots\cap A_n\right|. \end{align}

This can be compactly written as

\begin{align} \biggl|\bigcup_{i=1}^n A_i\biggr| &= \sum_{k = 1}^{n} (-1)^{k+1} \left( \sum_{1 \leq i_{1} < \cdots < i_{k} \leq n} \left| A_{i_{1}} \cap \cdots \cap A_{i_{k}} \right| \right). \end{align}

The name comes from the idea that the principle is based on over-generous inclusion, followed by compensating exclusion. When n > 2 the exclusion of the pairwise intersections is (possibly) too severe, and the correct formula is as shown with alternating signs.

This formula is attributed to Abraham de Moivre; it is sometimes also named for Daniel da Silva, Joseph Sylvester or Henri Poincaré.

For the case of three sets A, B, C the inclusion–exclusion principle is illustrated in the graphic on the right.

Read more about Inclusion–exclusion Principle:  Proof, Example, In Probability, Diluted Inclusion–exclusion Principle, Other Forms, Applications

Famous quotes containing the word principle:

    “On principle I dislike an oath which requires a man to swear he has not done wrong. It rejects the Christian principle of forgiveness on terms of repentance. I think it is enough if the man does no wrong hereafter.”
    —Abraham Lincoln (1809–1865)