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.