TOPICS

# Inclusion-Exclusion Principle

Let denote the cardinal number of set , then it follows immediately that

 (1)

where denotes union, and denotes intersection. The more general statement

 (2)

also holds, and is known as Boole's inequality or one of the Bonferroni inequalities.

This formula can be generalized in the following beautiful manner. Let be a p-system of consisting of sets , ..., , then

 (3)

where the sums are taken over k-subsets of . This formula holds for infinite sets as well as finite sets (Comtet 1974, p. 177).

The principle of inclusion-exclusion was used by Nicholas Bernoulli to solve the recontres problem of finding the number of derangements (Bhatnagar 1995, p. 8).

For example, for the three subsets , , and of , the following table summarizes the terms appearing the sum.

 # term set length 1 2, 3, 7, 9, 10 5 1, 2, 3, 9 4 2, 4, 9, 10 4 2 2, 3, 9 3 2, 9, 10 3 2, 9 2 3 2, 9 2

is therefore equal to , corresponding to the seven elements .

Bayes' Theorem, Bonferroni Inequalities

## Explore with Wolfram|Alpha

More things to try:

## References

Andrews, G. E. Number Theory. Philadelphia, PA: Saunders, pp. 139-140, 1971.Andrews, G. E. q-Series: Their Development and Application in Analysis, Number Theory, Combinatorics, Physics, and Computer Algebra. Providence, RI: Amer. Math. Soc., p. 60, 1986.Bhatnagar, G. Inverse Relations, Generalized Bibasic Series, and Their U(n) Extensions. Ph.D. thesis. Ohio State University, 1995.Comtet, L. Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, pp. 176-177, 1974.da Silva. "Proprietades geraes." J. de l'Ecole Polytechnique, cah. 30.de Quesada, C. A. "Daniel Augusto da Silva e la theoria delle congruenze binomie." Ann. Sci. Acad. Polytech. Porto, Coīmbra 4, 166-192, 1909.Dohmen, K. Improved Bonferroni Inequalities with Applications: Inequalities and Identities of Inclusion-Exclusion Type. Berlin: Springer-Verlag, 2003.Havil, J. Gamma: Exploring Euler's Constant. Princeton, NJ: Princeton University Press, p. 66, 2003.Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed. Reading, MA: Addison-Wesley, pp. 178-179, 1997.Sylvester, J. "Note sur la théorème de Legendre." Comptes Rendus Acad. Sci. Paris 96, 463-465, 1883.

## Referenced on Wolfram|Alpha

Inclusion-Exclusion Principle

## Cite this as:

Weisstein, Eric W. "Inclusion-Exclusion Principle." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Inclusion-ExclusionPrinciple.html