TOPICS

Inclusion-Exclusion Principle

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

(1)

where union denotesunion, and denotesintersection. The more general statement

(2)

also holds, and is known as Boole's inequality or one of theBonferroniinequalities.

This formula can be generalized in the following beautiful manner. Let $A={A_i}_(i=1)^p$ be ap-system of 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|,

(3)

where the sums are taken overk-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 ofderangements (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.

#	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

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

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īmbra4, 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. Paris96, 463-465, 1883.

Referenced on Wolfram|Alpha

Inclusion-Exclusion Principle

Cite this as:

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

Movatterモバイル変換

Inclusion-Exclusion Principle

See also

Explore with Wolfram|Alpha

References

Referenced on Wolfram|Alpha

Cite this as:

Subject classifications