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 .

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.