Kombinatorika
Princíp zapojenia a vypojenia
Základný vzťah
V tejto časti budeme používať symboliku z predchádzajúcej kapitoly. Napríklad označuje počet všetkých objektov skúmanej množiny.
Tvrdenie
V kombinatorike princíp zapojenia a vypojenia alebo princíp exklúzie a inklúzie hovorí, že ak sú konečné množiny, tak
V kombinatorike princíp zapojenia a vypojenia alebo princíp exklúzie a inklúzie hovorí, že ak sú konečné množiny, tak
Dôkaz tvrdenia.
- Objekt, ktorý nemá ani jednu z vlastností prispieva jednotkou k číslu aj k číslu , ale vo zvyšných sčítancoch na pravej strane sa nevyskytuje.
- Ak nejaký objekt má vlastností, kde , potom prispieva
- jednotkou k číslu N
- jednotkami k sume (lebo prispieva jednotkou k sčítancom)
- jednotkami k sume . (Z vlastností daného objektu možno vybrať dvojíc, preto objekt prispieva k tejto sume jednotkami), atď.
- Teda objekt s vlastnosťami prispieva k pravej strane rovnosti hodnotou
- Podľa binomickej vety vieme, že táto hodnota (striedavé sčítanie a odčítanie kombinačných čísel je rovná nule.
- Preto celkový príspevok objektu s aspoň jednou vlastnosťou k obidvom stranám rovnosti je rovný nule.