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ě, 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{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

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

Odkazy

Související články

Externí odkazy

Princip inkluze a exkluze v encyklopedii MathWorld (anglicky)