Princip inkluze a exkluze

matematický vztah popisující velikost sjednocení množin

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.

.

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,

.

Obecně, pro každý soubor konečných množin platí

Alternativní zápisy

editovat

 

či

 

kde symbol   značí všechny k–prvkové podmnožiny množiny X.

Označme  , a nechť   je charakteristická funkce množiny  , tz.

 

Pro každé   platí  , použitím vzorce

 

a dosazením   dostaneme

 

Sečtením těchto rovností pro všechna  , a záměnou pořadí sumace získáme

 

Nyní si stačí uvědomit, že   je charakteristická funkce množiny  , takže

 

Speciálně pro   je   prázdný součin, jenž má podle definice hodnotu 1, takže  . Proto

 

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

Literatura

editovat

Související články

editovat

Externí odkazy

editovat

Princip inkluze a exkluze v encyklopedii MathWorld (anglicky)