Inclusion-exclusion principle
In
combinatorics, the
inclusion-exclusion principle states that if
A1, ...,
An 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.