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.
See also
Referenced By
List of combinatorics topics | List of mathematical topics (G-I) | List of mathematical topics (G-Z)
|
