Kombinatorika

V tejto časti budeme používať symboliku z predchádzajúcej kapitoly. Napríklad $N$ 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 $A_1, ..., A_n$ sú konečné množiny, tak
$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)}$

Dôkaz tvrdenia.

1. Objekt, ktorý nemá ani jednu z vlastností $a_r$ prispieva jednotkou k číslu $N(0)$ aj k číslu $N$, ale vo zvyšných sčítancoch na pravej strane sa nevyskytuje.
2. Ak nejaký objekt má $m$ vlastností, kde $1 \leq m \leq k$, potom prispieva
• jednotkou k číslu N
• $m$ jednotkami k sume $\sum_{r=1}^{k}N\left(a_r\right)$ (lebo prispieva jednotkou k $m$ sčítancom)
• $\binom {m} {2}$ jednotkami k sume $\sum_{1 \leq r \leq s}^{k}N\left(a_ra_s\right)$. (Z $m$ vlastností daného objektu možno vybrať $\binom {m} {2}$dvojíc, preto objekt prispieva k tejto sume $\binom {m} {2}$ jednotkami), atď.
3. Teda objekt s $m>1$ vlastnosťami prispieva k pravej strane rovnosti hodnotou
   $1-m+\binom{m}{2}-\binom{m}{3}+\ldots+\left(-1\right)^{k+1}\binom{m}{k}$
4. Podľa binomickej vety vieme, že táto hodnota (striedavé sčítanie a odčítanie kombinačných čísel $\sum_{i=0}^{n}{{-1}^i\binom{m}{i}=0})$ je rovná nule.
5. Preto celkový príspevok objektu s aspoň jednou vlastnosťou k obidvom stranám rovnosti je rovný nule.