Inclusion-Exclusion Principle
The inclusion-exclusion principle counts the size of a union of sets by alternately adding and subtracting the sizes of their intersections.
Definition
A counting identity stating that the cardinality of a union of finite sets equals the alternating sum of the cardinalities of all their intersections, taken over every nonempty subcollection.
Scope
This topic presents the inclusion-exclusion formula and its applications to counting objects that avoid a list of forbidden properties: derangements, surjections, Euler's totient, and the number of integers coprime to a given number. It introduces the sieve viewpoint and the Mobius-function generalization over partially ordered sets, which places the principle in a broader algebraic setting.
Core questions
- How many elements satisfy at least one of several overlapping conditions?
- How can one count objects avoiding all of a set of forbidden properties?
- How do derangements and surjection counts follow from the principle?
- How does the Mobius function on a poset generalize inclusion-exclusion?
Key concepts
- Union of overlapping sets
- Sieve method
- Derangements via inclusion-exclusion
- Counting surjections
- Euler's totient function
- Mobius function on posets
Key theories
- Inclusion-exclusion formula
- The cardinality of a union of sets A_1 through A_n equals the sum of single-set sizes minus pairwise intersections plus triple intersections, and so on, correcting systematically for overcounting of shared elements.
- Mobius inversion on posets
- Stanley's poset-theoretic generalization replaces the alternating signs of inclusion-exclusion with the Mobius function of a partially ordered set, unifying the principle with number-theoretic and lattice-theoretic inversion formulas.
Clinical relevance
The sieve idea generalizes to number theory (the sieve of Eratosthenes and analytic sieves), probability (the Bonferroni inequalities bounding union probabilities), and reliability analysis of systems with overlapping failure modes.
History
Stated in essence by de Moivre and Sylvester, the principle was placed within a general theory of Mobius functions on partially ordered sets by Rota in 1964, a landmark of modern combinatorics.
Key figures
- Abraham de Moivre
- Gian-Carlo Rota
Related topics
Seminal works
- stanley2011
Frequently asked questions
- Why are the signs alternating?
- Elements lying in several of the sets are added too many times; subtracting pairwise intersections overcorrects, so triple intersections are added back, producing the alternating pattern that nets each element exactly once.
- What is the connection to the Mobius function?
- Inclusion-exclusion is the special case of Mobius inversion on the Boolean lattice of subsets, where the Mobius function takes values plus or minus one.