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.

${\displaystyle |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,

${\displaystyle |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 ${\displaystyle n}$ konečných množin ${\displaystyle A_{1},A_{2},...,A_{n}}$ platí

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

${\displaystyle {\begin{aligned}\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{aligned}}}$

či

${\displaystyle \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 ${\displaystyle {X \choose k}}$ značí všechny k–prvkové podmnožiny množiny X.

Důkaz

Označme ${\displaystyle A=\bigcup _{i=1}^{n}A_{i}}$, a nechť ${\displaystyle f_{i}:A\rightarrow \{0,1\}}$ je charakteristická funkce množiny ${\displaystyle A_{i}}$, tz.

${\displaystyle f_{i}(a)=\left\{{\begin{matrix}1,&a\in A_{i}\\0,&{\mbox{jinak}}\end{matrix}}\right.}$

Pro každé ${\displaystyle a\in A}$ platí ${\displaystyle \prod _{i=1}^{n}(1-f_{i}(a))=0}$, použitím vzorce

${\displaystyle (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 ${\displaystyle x_{i}=-f_{i}\,\!(x)}$ dostaneme

${\displaystyle \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 ${\displaystyle a\in A}$, a záměnou pořadí sumace získáme

${\displaystyle 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 ${\displaystyle \prod _{i\in I}f_{i}(a)}$ je charakteristická funkce množiny ${\displaystyle \bigcap _{i\in I}A_{i}}$, takže

${\displaystyle \sum _{a\in A}\prod _{i\in I}f_{i}(a)=\left|\bigcap _{i\in I}A_{i}\right|}$

Speciálně pro ${\displaystyle I=\emptyset }$ je ${\displaystyle \prod _{i\in \emptyset }f_{i}(a)}$ prázdný součin, jenž má podle definice hodnotu 1, takže ${\displaystyle \sum _{a\in A}\prod _{i\in \emptyset }f_{i}(a)=\left|A\right|}$. Proto

${\displaystyle 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. 

Odkazy

Související články

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

Externí odkazy

Princip inkluze a exkluze v encyklopedii MathWorld (anglicky)