Inclusion-exclusion principle

Inclusion-exclusion principle

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

where |A| denotes the cardinality of the set A.

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

then

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.

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 A is n, then the number of derangements is the nearest integer to

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.

See also