A method for calculating the number of objects which do not have any of the given properties , according to the following formula:
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 ). The inclusion-and-exclusion principle yields a formula for calculating the number of objects having exactly properties out of , :
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 . 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):
|||M. Hall jr., "Combinatorial theory" , Wiley (1986)|
|||H.J. Ryser, "Combinatorial mathematics" , Wiley & Math. Assoc. Amer. (1963)|
|||J. Riordan, "An introduction to combinational analysis" , Wiley (1958)|
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