# Inclusion-and-exclusion principle

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