Namespaces
Variants
Actions

Inclusion-and-exclusion principle

From Encyclopedia of Mathematics
Jump to: navigation, search

A method for calculating the number of objects which do not have any of the given properties , according to the following formula:

(1)

where denotes the absence of property , is the total number of objects, is the number of objects having property , is the number of objects having both properties and , etc. (see [3]). The inclusion-and-exclusion principle yields a formula for calculating the number of objects having exactly properties out of , :

(2)

where , , and the summation is performed over all -tuples such that , , i.e.

The method for calculating according to (2) is also referred to as the inclusion-and-exclusion principle. This principle is used in solving combinatorial and number-theoretic problems [1]. For instance, given a natural number and natural numbers such that if , the number of natural numbers , , that are not divisible by , , is, according to (1):

The inclusion-and-exclusion principle also serves to solve problems of inversion [2], [3].

References

[1] M. Hall jr., "Combinatorial theory" , Wiley (1986)
[2] H.J. Ryser, "Combinatorial mathematics" , Wiley & Math. Assoc. Amer. (1963)
[3] J. Riordan, "An introduction to combinational analysis" , Wiley (1958)
How to Cite This Entry:
Inclusion-and-exclusion principle. S.A. Rukova (originator), Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Inclusion-and-exclusion_principle&oldid=16893
This text originally appeared in Encyclopedia of Mathematics - ISBN 1402006098