Namespaces
Variants
Actions

Difference between revisions of "Inclusion-and-exclusion principle"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
A method for calculating the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i0504301.png" /> of objects which do not have any of the given properties <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i0504302.png" />, according to the following formula:
+
<!--
 +
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.
 +
-->
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i0504303.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i0504304.png" /></td> </tr></table>
+
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:
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i0504305.png" /> denotes the absence of property <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i0504306.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i0504307.png" /> is the total number of objects, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i0504308.png" /> is the number of objects having property <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i0504309.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043010.png" /> is the number of objects having both properties <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043011.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043012.png" />, etc. (see [[#References|[3]]]). The inclusion-and-exclusion principle yields a formula for calculating the number of objects having exactly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043013.png" /> properties out of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043014.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043015.png" />:
+
$$ \tag{1 }
 +
N ( a _ {1}  ^  \prime  \dots a _ {r}  ^  \prime  )  = \
 +
N - \sum _ {i = 1 } ^ { r }  N ( a _ {i} ) +
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043016.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$
 +
+
 +
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043017.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043018.png" />, and the summation is performed over all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043019.png" />-tuples <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043020.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043021.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043022.png" />, i.e.
+
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 $:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043023.png" /></td> </tr></table>
+
$$ \tag{2 }
 +
e _ {m}  = \
 +
\sum _ {i = 0 } ^ { {r }  - m }
 +
(- 1)  ^ {i}
 +
\left (
 +
\begin{array}{c}
 +
m + i \\
 +
i
 +
\end{array}
 +
\right )
 +
s _ {m+} i ,
 +
$$
  
The method for calculating <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043024.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043025.png" /> and natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043026.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043027.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043028.png" />, the number of natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043029.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043030.png" />, that are not divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043031.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043032.png" />, is, according to (1):
+
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.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043033.png" /></td> </tr></table>
+
$$
 +
s _ {1}  = \sum _ { i } N ( a _ {i} ),\
 +
s _ {2}  = \sum _  \begin {array}{c}
 +
{i, j } \\
 +
{i \neq j }
 +
\end{array}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050430/i05043034.png" /></td> </tr></table>
+
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]]].
 
The inclusion-and-exclusion principle also serves to solve problems of inversion [[#References|[2]]], [[#References|[3]]].

Latest revision as of 22:12, 5 June 2020


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 [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 [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 [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. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Inclusion-and-exclusion_principle&oldid=16893
This article was adapted from an original article by S.A. Rukova (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article