Princip inkluze a exkluze
Nejprve z doposud získaných poznatků o Móbiových inverzních formulích pro obecné lokálně konečné částečně uspořádané množiny odvodíme následující speciální větu pro množinu 2S všech podmnožin nějaké neprázdné konečné množiny S částečně uspořádanou množinovou inkluzí.
Věta
Buď S neprázdná konečná množina. Buď K těleso charakteristiky 0. Pak pro libovolné dvě funkce f,g:2s^K platí rovnosti
g(T) =   ^2   f{y)   pro všechny podmnožiny T C S
TCYCS
právě tehdy když platí rovnosti
f(T) =   ^2  (—l)'y ^šiX)   Pro všechny podmnožiny T C S.
TCYCS
Tato věta plyne z duální verze věty o Móbiových inverzních formulích aplikované na částečně uspořádanou množinu 2S a z dříve odvozeného faktu, že hodnota Móbiovy funkce n2s částečně uspořádané množiny 2S na libovolných podmnožinách 7~, Y C S splňujících T C Y je rovna ^(T, Y) = (—l)ly_TL □
Dokážeme následující větu, kterou lze považovat za obecnou variantu poznatku nesoucího název princip inkluze a exkluze.
Věta
Buď Q konečná množina. Necht {Aj : / G /} je neprázdný konečný systém podmnožin množiny Q, což znamená, že I je neprázdná konečná množina a a' ^ Q P^o všechna i E I. Položme A; = Q — A; pro všechna i E I. Pak pro libovolnou podmnožinu JC / platí
O/n n a-
E (-1)
K-J\
n a
ieJ
iei-j
JCKCI
Dodejme pro určitost, že | j A; = Q.
/G0
Důkaz.
Je evidentní, že pro libovolnou podmnožinu JC / platí
í>= u íí>n n
i€J JCKCI V/eK /e/-K
A-
přičemž průnik vlevo je disjunktním sjednocením průniků vpravo. Odtud plyne rovnost
n a
ieJ
E
JCKCI
pAn H A
ieK iei-K
Definujme nyní funkce f,g na množině 21 předpisy
f(j)
n A n n a
/g J iei—j
g(-l)
n a-
pro všechny podmnožiny J C /
Pak předchozí vztah lze přepsat jako formuli
g(J) =  ^2 pro všechny podmnožiny J C /
JCKCI
Podle předchozí věty potom ovšem platí také inverzní formule
f(J) = (—l)\K~J\g(K)   pro všechny podmnožiny J C /
JCKCI
Tato poslední formule pak po dosazení nazpět dává rovnost
o* n n a-
E (-1)
JCKCI
n a
která platí pro libovolnou podmnožinu J C /
□
Vůbec nejčastější interpretace situace popsané v předchozí větě je tato: Je dána konečná množina Q objektů, které mohou mít konečně mnoho vlastností v-n kde / G /. Označme pro každé / G / symbolem A; množinu všech těch objektů z Q, které mají vlastnost v,. Pak pro danou podmnožinu J C / je H/eJ^' ^ H/e/--/^' množinou všech těch objektů z Q, které mají právě vlastnosti v-, pro / G J.
Vztah v předchozí větě potom vyjadřuje počet těchto objektů prostřednictvím počtů objektů v podmnožinách f)ieKAj, kde JCKC/, což jsou množiny objektů majících alespoň vlastnosti v-, pro / G K. Počty takovýchto objektů obvykle bývají snáze zjistitelné.
Nejčastěji uváděnou variantou principu inkluze a exkluze bývá vztah pro počet těch objektů z Q, které nemají žádnou z vlastností v-, pro / G /.
Buď Q konečná množina. Nechi {A; : / G /} je neprázdný konečný systém podmnožin množiny Q. Označme symbolem A(0) množinu objektů níe/(<? - a) = Q - U;e; a- Pak platí
4(o)| =
K1
n a
fc/e p| Aj = Q.
/G0
Zůstaňmme ještě chvíli u posledního důsledku. Rozepišme podrobněji formuli uvedenou v tomto důsledku. Vezměme nejprve za K prázdnou množinu, potom vezměme za K všechny jednoprvkové podmnožiny množiny /, pak vezměme za K všechny dvouprvkové podmnožiny množiny /, a tak pokračujme dále, až nakonec vezmeme za K celou množinu /. Takto formule v posledním důsledku nabude tvaru
|>4(0)| = |<?| -5^|A-| +       lA-nvA/l-   Y  |A-n/lin/l/c| + ---
iei
VJ,k}CI
+ (-1)
iei
Střídání znamének v této formuli vysvětluje použití termínu princip inkluze a exkluze.
Obecnějším vztahem, než je vztah uvedený v předchozím důsledku, je vztah udávající počet těch objektů z Q, které mají právě r vlastností mezi vlastnostmi v;, kde / G /, pro nějaké r splňující 0 ^ r ^ 1/
Důsledek.
Buď Q konečná množina. Necht {A; : i e 1} je neprázadný konečný systém podmnožin množiny Q. Položme A; = Q — A; pro všechna / G /. Pro libovolné celé číslo r splňující O ^ r ^ |/| označme symbolem A(r) množinu objektů
u JQi (f)ieJ a n d;e/-jÄ) ■ Pak Platí
A(r)\= E^'-'Cr1)
KC/
r^\K\
n a
Důkaz.
S použitím obecného tvaru principu inkluze a exkluze uvedeného ve druhé z předchozích dvou vět postupně vychází
\A(r)\ = E
JC/
O'n n a-
E E (-d
_-nlx-J|
JC/ JCKCI
n a
E E(-d
K-J\
KCI JCK
r<\K\  \J\ = r
n a
ieK
E
KC/
K
(-1)
|K|-r
n a
Poslední rovnost plyne z kombinatorického významu binomických koeficientů,
v tomto případě určujícího počet r-prvkových podmnožin množiny K. □
j