Cesko.wiki Princip inkluze a exkluze
Author
Albert FloresPrincip inkluze a exkluze popisuje vztah mezi velikostí sjednocení nějakých 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 . +more) 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. ::|A \cup B| = |A| + |B| - |A \cap B| \,. +more 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, ::|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| \,.
Obecně, pro každý soubor n konečných množin A_1, A_2,...,A_n platí
\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|
Alternativní zápisy
\begin{align} \left| \bigcup_{i=1}^n A_i \right| & {} = \sum_{i=1}^n \left| A_i \right| - \sum_{1 \leq i_1
či
\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|
kde symbol {X \choose k} značí všechny k-prvkové podmnožiny množiny X.
Důkaz
Označme A = \bigcup_{i=1}^n A_i, a nechť f_i : A \rightarrow \{0,1\} je charakteristická funkce množiny A_i, tz.
f_i(a) = \left\{\begin{matrix} 1, & a \in A_i \\ 0, & \mbox{jinak} \end{matrix}\right.
Pro každé a \in A platí \prod_{i=1}^n (1 - f_i(a)) = 0, použitím vzorce
(1 + x_1)(1 + x_2) \cdots (1 + x_n) = \sum_{I \subseteq \{1,2,...n\}} \left( \prod_{i \in I} x_i \right)
a dosazením x_i = -f_i\,\!(x) dostaneme
\sum_{I \subseteq \{1,2,...n\}} \left(-1\right)^{\left| I \right|} \prod_{i \in I} f_i(a) = 0.
Sečtením těchto rovností pro všechna a \in A, a záměnou pořadí sumace získáme
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,. +moren\}} \left( -1 \right)^{\left| I \right|} \left( \sum_{a \in A} \prod_{i \in I} f_i( A ) \right).
Nyní si stačí uvědomit, že \prod_{i \in I} f_i(a) je charakteristická funkce množiny \bigcap_{i \in I} A_i, takže
\sum_{a \in A} \prod_{i \in I} f_i(a) = \left| \bigcap_{i \in I} A_i \right|
Speciálně pro I = \emptyset je \prod_{ i \in \emptyset} f_i(a) prázdný součin, jenž má podle definice hodnotu 1, takže \sum_{a \in A} \prod_{i \in \emptyset} f_i(a) = \left| A \right|. Proto
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,. +moren\}} \left( -1 \right)^{\left| I \right|} \left| \bigcap_{ i \in I} A_i \right|,.
což je přesně princip inkluze a exkluze.