Princip inkluze a exkluze

Princip inkluze a exkluze popisuje vztah mezi velikostí sjednocení množin a velikostmi všech možných průniků tohoto sjednocení.

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

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

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

• MATOUŠEK, Jiří; NEŠETŘIL, Jaroslav. Kapitoly z diskrétní matematiky. [s.l.] : Karolinum, 2007 (třetí, upravené a doplněné vydání). ISBN 978-80-246-1411-3. Kapitola 3. Kombinatorické počítání, s. 99-105. (česky) 

Odkazy

Související články

• Kombinatorické principy
• Problém šatnářky

Externí odkazy

(anglicky)  Princip inkluze a exkluze v encyklopedii MathWorld