Difference between revisions of "Inclusion-and-exclusion principle"
(Importing text file) |
Ulf Rehmann (talk | contribs) m (tex encoded by computer) |
||
Line 1: | Line 1: | ||
− | + | <!-- | |
+ | 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 | + | 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]]]. | 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) |
Inclusion-and-exclusion principle. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Inclusion-and-exclusion_principle&oldid=16893