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.
![N N](https://lms.umb.sk/filter/tex/pix.php/a4b1432432038fbb6d340407982580cb.png)
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
![A_1, ..., A_n A_1, ..., A_n](https://lms.umb.sk/filter/tex/pix.php/181b68df9c78992f386971dc70a43779.png)
![N(0)=N- \sum{N(a_i)} + \sum{N(a_ra_s)} - \sum{N(a_ra_sa_t)} + \cdot \cdot \cdot(-1)^{n} \sum{N(a_ra \cdot \cdot \cdot a_n)} N(0)=N- \sum{N(a_i)} + \sum{N(a_ra_s)} - \sum{N(a_ra_sa_t)} + \cdot \cdot \cdot(-1)^{n} \sum{N(a_ra \cdot \cdot \cdot a_n)}](https://lms.umb.sk/filter/tex/pix.php/8afe05598b5d770216ec66a2f69e64fc.png)
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.