Princip inkluze a exkluze

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Princip 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 ...) 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 prvků v každé z nich, mínus počet prvků, které jsou v obou.

|A \cup B| = |A| + |B| - |A \cap B| \,.

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ě, 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[editovat | editovat zdroj]


\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 < \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}

č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[editovat | editovat zdroj]

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,...n\}} \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,...n\}} \left( -1 \right)^{\left| I \right|} \left| \bigcap_{ i \in I} A_i \right|,

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

Literatura[editovat | editovat zdroj]

Odkazy[editovat | editovat zdroj]

Související články[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]

Princip inkluze a exkluze v encyklopedii MathWorld (anglicky)