Princip inkluze a exkluze

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 počtu prvků v každé z nich, minus 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ě, 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 _{\mathrm{\varnothing }\ne I\subseteq \{1,2.,...,n\}}{(-1)}^{\left|I\right|-1}\left|\bigcap _{i\in I}{A}_i\right|$

Alternativní zápisy

$\begin{array}{cc}\left|\bigcup _{i=1}^n{A}_i\right|& =\sum _{i=1}^n\left|A_i\right|-\sum _{1\le i_1<i_2\le n}|A_{i_1}\cap A_{i_2}|+\\ & +\sum _{1\le i_1<i_2<i_3<\dots \le n}|A_{i_1}\cap A_{i_2}\cap A_{i_3}|-\\ & -\cdots +{(-1)}^{n-1}|A_1\cap A_2\cap \dots \cap A_n|\end{array}$

či

$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _{k=1}^n{(-1)}^{k-1}\sum _{I\in (\genfrac{}{}{0ex}{}{\{1,2,...,n\}}{k})}\left|\bigcap _{i\in I}{A}_i\right|$

kde symbol $(\genfrac{}{}{0ex}{}{X}{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\to \{0,1\}$ je charakteristická funkce množiny $A_i$, tz.

$f_i(a)=\{\begin{array}{cc}1,& a\in A_i\\ 0,& \text{jinak}\end{array}$

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\}}{(-1)}^{\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}(\sum _{I\subseteq \{1,2,...n\}}{(-1)}^{\left|I\right|}\prod _{i\in I}{f}_i(a))=\sum _{I\subseteq \{1,2,...n\}}{(-1)}^{\left|I\right|}(\sum _{a\in A}\prod _{i\in I}{f}_i(A)).$

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=\mathrm{\varnothing }$ je $\prod _{i\in \mathrm{\varnothing }}{f}_i(a)$ prázdný součin, jenž má podle definice hodnotu 1, takže $\sum _{a\in A}\prod _{i\in \mathrm{\varnothing }}{f}_i(a)=\left|A\right|$. Proto

$0=\sum _{I\subseteq \{1,2,...n\}}{(-1)}^{\left|I\right|}(\sum _{a\in A}\prod _{i\in I}{f}_i(A))=\left|A\right|+\sum _{\mathrm{\varnothing }\ne I\subseteq \{1,2,...n\}}{(-1)}^{\left|I\right|}\left|\bigcap _{i\in I}{A}_i\right|,$

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

Literatura

• Šablona:Citace monografie

Odkazy

Související články

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