Princip inkluze a exkluze

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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, mínus 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ě, každý soubor konečných množin platí

Alternativní zápisy[editovat | editovat zdroj]

či

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

Důkaz[editovat | editovat zdroj]

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 | editovat zdroj]

Odkazy[editovat | editovat zdroj]

Související články[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]

Princip inkluze a exkluze v encyklopedii MathWorld (anglicky)