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
či
kde symbol
značí všechny k–prvkové podmnožiny množiny X.
Důkaz
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
Odkazy
Související články
- Kombinatorické principy
- Problém šatnářky
Externí odkazy
Princip inkluze a exkluze v encyklopedii MathWorld (anglicky)
Portály: Matematika