Inclusion-exclusion principle

In combinatorial mathematics, the inclusion-exclusion principle states that if A₁, ..., A_n are finite sets, then

<math>\left|\bigcup_{i=1}^n A_i\right|=\sum_{i=1}^n\left|A_i\right|

-\sum_{i,j\,:\,i\neq j}\left|A_i\cap A_j\right|<math><math>+\sum_{i,j,k\,:\,i\neq j\neq k\neq i}\left|A_i\cap A_j\cap A_k\right|-\ \cdots\cdots\ \pm \left|A_1\cap\cdots\cap A_n\right|<math>

where |A| denotes the cardinality of the set A. For example, taking n = 2, we get a special case of double counting: in words, we can count the size of the union of sets A and B by adding |A| and |B| and then subtracting the size of their intersection. 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 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.

To prove the inclusion-exclusion principle in general, let X be a superset of all A₁, ..., A_n. The formula follows by first proving the identity

<math> 1_{\bigcup_{i=1}^n A_i}=\sum_{i=1}^n 1_{A_i}

-\sum_{i,j\,:\,i\neq j}1_{A_i\cap A_j}<math>

<math>+\sum_{i,j,k\,:\,i\neq j\neq k\neq i}1_{A_i\cap A_j\cap A_k}-\ \cdots\cdots\ \pm 1_{A_1\cap\cdots\cap A_n} <math>

which is shown by manipulating indicator functions, and then summing over all x ∈ X.

The principle is sometimes stated in the form that says that if

<math>g(A)=\sum_{S\,:\,S\subseteq A}f(S)<math>

then

<math>f(A)=\sum_{S\,:\,S\subseteq A}(-1)^{\left|A\right|-\left|S\right|}g(S)<math>

In that form it is seen to be the Möbius inversion formula for the incidence algebra of the partially ordered set of all subsets of A.

The principle includes inequalities, showing that the sum of the first k terms in the formula is alternately an upper bound and a lower bound for the LHS. This can be used in cases where the full formula is too cumbersome.

Perhaps the most 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 (number of elements in) A is n, then the number of derangements is

<math>\left [ \frac {n!}{e} \right ]<math>

where [x] denotes the nearest integer function.

This is also known as the subfactorial of n, written <math>!n<math>. 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.

In many cases where the principle could give an exact formula (in particular, counting prime numbers using the sieve of Eratosthenes), the formula arising doesn't offer useful content because the number of terms in it is excessive. If each term individually can be estimated accurately, the accumulation of errors may imply that the inclusion-exclusion formula isn't directly applicable. In number theory, this difficulty was addressed by Viggo Brun. After a slow start, his ideas were taken up by others, and a large variety of sieve methods developed. These for example may try to find upper bounds for the "sieved" sets, rather than an exact formula.

The inclusion-exclusion principle can also be used in probability where it becomes:

<math>P\left(\bigcup_{i=1}^n A_i\right)=\sum_{i=1}^n P\left(A_i\right)

-\sum_{i,j\,:\,i\neq j}P\left(A_i\cap A_j\right)<math><math>+\sum_{i,j,k\,:\,i\neq j\neq k\neq i}P\left(A_i\cap A_j\cap A_k\right)-\ \cdots\cdots\ \pm P\left(\bigcap_{i=1}^n A_i\right)<math>

See also

• combinatorial principles
• Boole's inequality
• Double counting
• Necklace problemfr:Principe d'inclusion-exclusion de Moivre

it:Principio di inclusione ed esclusione he:עקרון ההכלה וההפרדה