Zobrazení zdroje stránky Princip inkluze a exkluze

'''Princip inkluze a exkluze''' popisuje vztah mezi velikostí [[sjednocení]] nějakých [[množina|množin]] a velikostmi všech možných [[průnik]]ů těchto množin.

Představme si úlohu, máme čísla 1 až 1000, kolik z nich je dělitelných dvěma nebo třemi? (jsou to 2, 3, 4, 6, 8, 9, 10 ...) Můžeme vzít sudá čísla (500) a přičíst k ním násobky trojky (333), ale pozor – čísla 6 nebo 12 jsme započítali dvakrát!

Princip inkluze a exkluze nám říká, že počet prvků ve sjednocení dvou množin je součet počtu prvků v každé z nich, minus počet prvků, které jsou v obou.
::<math>|A \cup B| = |A| + |B| - |A \cap B| \,</math>.
Tedy výsledek = počet čísel dělitelných dvěma (500) + počet čísel dělitelných třemi (333) – počet čísel dělitelných šesti (166) = 667.

Podobně pro 3 množiny ''A'', ''B'' a ''C'',
::<math>|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| \,</math>.

Obecně, pro každý soubor <math>n</math> konečných množin <math>A_1, A_2,...,A_n</math> platí

<math>
\left| \bigcup_{i=1}^n A_i \right| = \sum_{ \emptyset \neq I \subseteq \{ 1,2.,...,n \} } \left( -1 \right)^{\left| I \right| - 1} \left| \bigcap_{i \in I} A_i \right|
</math>

== Alternativní zápisy ==
<math>
\begin{align}
\left| \bigcup_{i=1}^n A_i \right| & {} = \sum_{i=1}^n \left| A_i \right| - \sum_{1 \leq i_1 < i_2 \leq n } \left| A_{i_1} \cap A_{i_2} \right| + \\
& {} + \sum_{1 \leq i_1 < i_2 < i_3 < \ldots \leq n } \left| A_{i_1} \cap A_{i_2} \cap A_{i_3} \right| - \\
& {} - \cdots + \left( -1 \right)^{n-1} \left| A_1 \cap A_2 \cap \ldots \cap A_n \right| 
\end{align}
</math>

či

<math>
\left| \bigcup_{i=1}^n A_i \right| = \sum_{k=1}^n \left( -1 \right)^{k-1} \sum_{I \in {\{ 1,2,...,n \} \choose k}} \left| \bigcap_{i \in I} A_i \right|
</math>

kde symbol <math>{X \choose k}</math> značí všechny ''k''–prvkové [[podmnožina|podmnožiny]] množiny ''X''.

== Důkaz ==
Označme <math>A = \bigcup_{i=1}^n A_i</math>, a nechť <math>f_i : A \rightarrow \{0,1\}</math> je [[charakteristická funkce]] množiny <math>A_i</math>, tz.

<math>
f_i(a) = \left\{\begin{matrix} 1, & a \in A_i \\ 0, & 
         \mbox{jinak} \end{matrix}\right. 
</math>

Pro každé <math>a \in A</math> platí <math>\prod_{i=1}^n (1 - f_i(a)) = 0</math>, použitím vzorce

<math>
(1 + x_1)(1 + x_2) \cdots (1 + x_n) = \sum_{I \subseteq \{1,2,...n\}} \left( \prod_{i \in I} x_i \right)
</math>

a dosazením <math>x_i = -f_i\,\!(x)</math> dostaneme

<math>\sum_{I \subseteq \{1,2,...n\}} \left(-1\right)^{\left| I \right|} \prod_{i \in I} f_i(a) = 0.</math>

Sečtením těchto rovností pro všechna <math>a \in A</math>, a záměnou pořadí [[sumace]] získáme

<math>0 = \sum_{a \in A} \left( \sum_{ I \subseteq \{1,2,...n\}} \left( -1 \right)^{\left| I \right|} \prod_{i \in I} f_i(a) \right) = \sum_{ I \subseteq \{1,2,...n\}} \left( -1 \right)^{\left| I \right|} \left( \sum_{a \in A} \prod_{i \in I} f_i( A ) \right).
</math>

Nyní si stačí uvědomit, že <math>\prod_{i \in I} f_i(a)</math> je charakteristická funkce množiny <math>\bigcap_{i \in I} A_i</math>, takže

<math>
\sum_{a \in A} \prod_{i \in I} f_i(a) = \left| \bigcap_{i \in I} A_i \right|
</math>

Speciálně pro <math> I = \emptyset</math> je <math>\prod_{ i \in \emptyset} f_i(a)</math> prázdný [[Násobení|součin]], jenž má podle definice hodnotu 1, takže <math>\sum_{a \in A} \prod_{i \in \emptyset} f_i(a) = \left| A \right|</math>. Proto

<math>
0 = \sum_{ I \subseteq \{1,2,...n\}} \left( -1 \right)^{\left| I \right|} \left( \sum_{a \in A} \prod_{i \in I} f_i( A ) \right) = \left| A \right| + \sum_{\emptyset \neq I \subseteq \{1,2,...n\}} \left( -1 \right)^{\left| I \right|} \left| \bigcap_{ i \in I} A_i \right|,</math>

což je přesně princip inkluze a exkluze.

== Literatura ==
* {{Citace monografie
 | příjmení = Matoušek
 | jméno = Jiří
 | odkaz na autora = Jiří Matoušek
 | příjmení2 = Nešetřil
 | jméno2 = Jaroslav
 | odkaz na autora2 = Jaroslav Nešetřil
 | titul = Kapitoly z diskrétní matematiky
 | vydavatel = [[Nakladatelství Karolinum|Karolinum]]
 | místo = 
 | rok = 2007 (třetí, upravené a doplněné vydání)
 | isbn = 978-80-246-1411-3
 | kapitola = 3. Kombinatorické počítání
 | strany = 99–105
 | jazyk = česky
}}

== Odkazy ==

=== Související články ===
* [[Kombinatorické principy]]
* [[Problém šatnářky]]

=== Externí odkazy ===
{{MathWorld|id=Inclusion-ExclusionPrinciple}}
{{Autoritní data}}

{{Portály|Matematika}}

[[Kategorie:Kombinatorika]]