Inclusion-Exclusion Principle

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

 |A union B|=|A|+|B|-|A intersection B|,

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

 | union _(i=1)^NE_i|<=sum_(i=1)^N|E_i|,

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 A={A_i}_(i=1)^p be a p-system of S consisting of sets A_1, ..., A_p, then

 |A_1 union A_2 union ... union A_p|=sum_(1<=i<=p)|A_i|-sum_(1<=i_1<i_2<=p)|A_(i_1) intersection A_(i_2)|+sum_(1<=i_1<i_2<i_3<=p)|A_(i_1) intersection A_(i_2) intersection A_(i_3)|-...+(-1)^(p-1)|A_1 intersection A_2 intersection ... intersection A_p|,

where the sums are taken over k-subsets of A. This formula holds for infinite sets S 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 A_1={2,3,7,9,10}, A_2={1,2,3,9}, and A_3={2,4,9,10} of S={1,2,...,10}, the following table summarizes the terms appearing the sum.

1A_1{2, 3, 7, 9, 10}5
A_2{1, 2, 3, 9}4
A_3{2, 4, 9, 10}4
2A_1 intersection A_2{2, 3, 9}3
A_1 intersection A_3{2, 9, 10}3
A_2 intersection A_3{2, 9}2
3A_1 intersection A_2 intersection A_3{2, 9}2

|A_1 union A_2 union A_3| is therefore equal to (5+4+4)-(3+3+2)+2=7, corresponding to the seven elements A_1 union A_2 union A_3={1,2,3,4,7,9,10}.

See also

Bayes' Theorem, Bonferroni Inequalities

Explore with Wolfram|Alpha


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. 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.

Subject classifications