Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

## Princip inkluze a exkluze

Věta (Princip inkluze a exkluze)

Pro každý soubor konečných množin platí

Důkaz

Nechť x je libovolný prvek . Kolikrát přispívá x vlevo a kolikrát vpravo?

Vlevo: jednou - triviální Vpravo: Nechť j ( ) označuje počet množin , do kterých patří . Můžeme množiny přejmenovat aby platilo a . Prvek se tedy objevuje v průniku každé -tice množin (a v žádných jiných). Protože existuje právě -prvkových podmnožin -prvkové množiny, bude se objevovat v průnicích -tic vybraných ze všech prvků. Velikosti -tic jsou přitom započteny se znaménkem , tudíž na pravé straně přispívá veličinou