View source for Inclusion-and-exclusion principle

<!--
i0504301.png
$#A+1 = 34 n = 0
$#C+1 = 34 : ~/encyclopedia/old_files/data/I050/I.0500430 Inclusion\AAhand\AAhexclusion principle
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

A method for calculating the number  $  N( a _ {1}  ^  \prime  {} \dots a _ {r}  ^  \prime  ) $
of objects which do not have any of the given properties  $  a _ {1} \dots a _ {r} $, 
according to the following formula:

$$ \tag{1 }
N ( a _ {1}  ^  \prime  \dots a _ {r}  ^  \prime  )  = \ 
N - \sum _ {i = 1 } ^ { r }  N ( a _ {i} ) +
$$

$$ 
+ 
\sum _  \begin {array}{c}
{i, j = 1 } \\
 {i < j } 
\end{array} ^ { r }  N ( a _ {i} a _ {j} ) - \dots + (- 1)  ^ {r} N ( a _ {1} \dots a _ {r} ),
$$

where  $  a _ {i}  ^  \prime  $
denotes the absence of property  $  a _ {i} $, 
$  N $
is the total number of objects,  $  N( a _ {i} ) $
is the number of objects having property  $  a _ {i} $, 
$  N( a _ {i} a _ {j} ) $
is the number of objects having both properties  $  a _ {i} $
and  $  a _ {j} $, 
etc. (see [[#References|[3]]]). The inclusion-and-exclusion principle yields a formula for calculating the number of objects having exactly  $  m $
properties out of  $  a _ {1} \dots a _ {r} $, 
$  m = 0 \dots r $:

$$ \tag{2 }
e _ {m}  = \ 
\sum _ {i = 0 } ^ { {r }  - m }
(- 1)  ^ {i}
\left (
\begin{array}{c}
m + i \\
 i 
\end{array}
 \right )
s _ {m+} i ,
$$

where  $  s _ {0} = N $, 
$  s _ {k} = \sum N ( a _ {i _ {1}  } {} \dots a _ {i _ {k}  } ) $, 
and the summation is performed over all  $  k $-
tuples  $  ( i _ {1} \dots i _ {k} ) $
such that  $  i _ {1} \neq \dots \neq i _ {k} $, 
$  k = 1 \dots r $, 
i.e.

$$ 
s _ {1}  =  \sum _ { i } N ( a _ {i} ),\ 
s _ {2}  =  \sum _  \begin {array}{c}
{i, j } \\
 {i \neq j } 
\end{array}

N ( a _ {i} a _ {j} ) \dots
s _ {r}  =  N ( a _ {1} \dots a _ {r} ).
$$

The method for calculating  $  e _ {m} $
according to (2) is also referred to as the inclusion-and-exclusion principle. This principle is used in solving combinatorial and number-theoretic problems [[#References|[1]]]. For instance, given a natural number  $  a $
and natural numbers  $  a _ {1} \dots a _ {N} $
such that  $  ( a _ {i} , a _ {j} ) = 1 $
if  $  i \neq j $, 
the number of natural numbers  $  k $, 
$  0 < k \leq  n $, 
that are not divisible by  $  a _ {i} $, 
$  i = 1 \dots N $, 
is, according to (1):

$$ 
n - \sum _ {1 \leq  i \leq  N }
\left [ {
\frac{n}{a} _ {i} } \right ] +
\sum _ {1 \leq  i \leq  j \leq  N }
\left [ {
\frac{n}{a _ {i} a _ {j} }
 } \right ] - \dots
$$

$$ 
\dots + (- 1)  ^ {N} \left [ {
\frac{n}{a _ {1} \dots a _ {N} }
 } \right ] .
$$

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

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  M. Hall jr.,   "Combinatorial theory" , Wiley  (1986)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  H.J. Ryser,   "Combinatorial mathematics" , Wiley &amp; Math. Assoc. Amer.  (1963)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  J. Riordan,   "An introduction to combinational analysis" , Wiley  (1958)</TD></TR></table>