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.

.

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)