Princip inkluze a exkluze
Uvažujme následující situaci. Je dána konečná množina Q objektů, u nichž rozlišujeme konečný počet jistých vlastností, indexovaných prvky nějaké konečné množiny I. Každý z objektů množiny Q může mít některé ze zmíněných vlastností a jiné mít nemusí. Problém, který zkoumáme, spočívá v tom, jak určit, kolik je objektů nemajících žádnou z uvedených vlastností. Jestliže pro každé i E I označíme Aj množinu všech těch objektů z Q, které mají vlastnost s indexem i, pak jde o to, jak zjistit, kolik prvků má množina A(0) = Q — Aj. Této otázky se týká následující věta.
Pro libovolnou konečnou množinu M značíme \M\ počet prvků množiny M.
Věta. Buď Q konečná množina. Mějme konečnou indexovou množinu I a mějme konečný soubor množin Aj, kde i E I, jež jsou všechny podmnožinami množiny Q. To znamená, že A j C Q pro každé i E I. Potom pro množinu A(0) = Q —       Aj platí
Poznámka. Poněvadž Aj C Q pro i E I, v souladu s tím, co bylo uvedeno v úvodní kapitole o množinách, zde klademe
Důkaz. Postupujeme indukcí vzhledem k počtu prvků indexové množiny /. Je-li 7 = 0, pak A(0) = Q a dokazovaná rovnost plyne z rovnosti v předchozí poznámce. Předpokládejme tedy, že 7^0. Zvolme pevně index i El. Pak máme
i#)i=EHfL n ^ •
K Cl i€K
i<=I-{£}
1
= (q - U á) -a*n {q - U Á)
i€l-{£} i€l-{£}
= (Q- U a) -        U (^n^)).
Přitom zřejmě
[m- U (^n^)) c (q- (J 4).
Podle indukčního předpokladu aplikovaného na soubor podmnožin Aj, kde i E I — {£}, množiny Q pak máme
Q- (J a
t€J-{*}
= E M)1*1-
KCI-{£}
a podle téhož indukčního předpokladu aplikovaného na soubor podmnožin Ai H Aj, kde i El — {£}, množiny Ai dále máme
At - (J (A/ n 4)
t€J-{*}
Ä"CJ-{*}
P| {At n Ať)
n a
= E t-1)1^"1
{£}CKCI
Z těchto rovností a z předchozích množinových vztahů potom plyne
\A(0)\= E
Ä"CJ-{*}
= E (-d
1*1
1*1
KCI-{£}
= E (-d
i€K
- E (-d
l*|-i
{^CifC/
n a
i€K
+ E (-1)
1*1
{£}CKCI
n a
1*1 .
n a
2
Jiné ověření vztahu v předchozí větě by bylo možno vést prostřednictvím výpočtu, kolikrát je jeden každý objekt z Q započítán v sumě napravo. Přitom se rozliší objekty, které žádnou z uvažovaných vlastností nemají, od objektů ostatních a aplikuje se druhý z důsledků binomické věty uvedených v předchozí kapitole.
Vztah dokázaný v předchozí větě je možno názorněji přepsat ve tvaru
Tento vztah kvůli střídání znamének bývá právě označován termínem princip inkluze a exkluze. Jeho význam spočívá v tom, že převádí obtížný problém určit počet objektů na levé straně uvedené rovnosti na obvykle snazší problémy určit jednotlivé počty objektů na pravé straně této rovnosti. Použití principu inkluze a exkluze bude ilustrováno v následujících příkladech.
Příklad. Nechť n, k G N U {0} splňují k < n. Nechť S, resp. U jsou konečné množiny mající n, resp. k prvků. Je třeba určit, kolik existuje surjektivních zobrazení g : S —»• U.
Řešení. Jako základní množinu Q vezmeme množinu všech možných zobrazení / : S —>• U. Indexovou množinu / položíme rovnu U. Pro každý prvek w G U budeme u zobrazení / : S —>• U sledovat vlastnost spočívající v tom, že prvek w se neobjeví v obraze f (S). To tedy znamená, že pro každé w E U máme Aw = {f : S -)> U\ w (£ f (S)}. Množinu A(0) pak tvoří ta zobrazení g : S —»• U', pro něž g (S) = U, tedy právě surjektivní
Q-\jAi
\q\ -     + \aí^aj
i£l {i,j}CI
3
zobrazení. Podle principu inkluze a exkluze pak máme
|A(0)|=£(-1)|V|
vcu
n a
Množina Hwev ^w Přitom pozůstává ze všech těch zobrazení / : S —> U, pro něž f (S) C U — V, tedy ze všech možných zobrazení množiny S do množiny U — V. Podle tvrzení o počtu variací s opakováním tak dostáváme
f] a
(k-\v\y
Dosazením do předchozí rovnosti odtud plyne, že
iA(o)i = x)(-i)|v'-(*-mr-
vcu
Vidíme, že jednotliví sčítanci v poslední sumě nezávisí zcela na V, ale pouze na |V|. Přitom pro každé j G {0,1,..., k} podle tvrzení o počtu kombinací platí, že počet těch sčítanců, v nichž |V| = j, čili počet těch podmnožin VCU, pro něž |V| = j, je roven číslu Je tedy možné předchozí sumu částečně sečíst, čímž nakonec vychází
wo)i = E(-1)i--í"
i=o V7/
Nechť n G N. Permutace množiny {1,2, ...,n}, tedy variace n-té třídy v množině {1,2, ...,n}, můžeme způsobem popsaným v předchozí kapitole chápat také jako prostá zobrazení, a tudíž jako bijekce a : {1, 2,..., n} —> {1, 2,..., n}. Řekneme, že číslo i G {1, 2,..., n} je pevný bod takto zadané permutace cr, platí-li, že a (i) = i.
Příklad. Nechť n G N. Je třeba určit, kolik existuje permutací množiny {1, 2,..., n}, které nemají ani jeden pevný bod.
4
Řešení. Jako základní množinu Q vezmeme množinu všech možných permutací a : {1, 2,..., n} —> {1, 2,..., n}. Tato množina se obvykle značí symbolem Sn. Jako indexovou množinu / vezmeme množinu {1, 2,..., n}. Pro každé číslo i G {1, 2,..., n} budeme u zmíněných permutací a sledovat vlastnost spočívající v tom, že číslo i je pevným bodem permutace a. To znamená, že pro každé i G {1, 2,..., n} máme Aj = {a G Sn \ a(i) = i}. Množina A(0) potom pozůstává právě z těch permutací a G Sn, které nemají žádný pevný bod. Podle principu inkluze a exkluze pak máme
n a,
i€K
\m\= E
KC{l,2,...,n}
Přitom množinu f]iGK Aj tvoří právě ty permutace a G Sn, pro něž každé číslo z K je pevným bodem. Jedná se tedy vlastně o permutace množiny {1, 2,..., n} — K. To ovšem znamená, že máme
n *
i€K
(n- \K\)\
Dosazením tohoto poznatku do předchozí rovnosti dostáváme \A(0)\=    E    (-V1"1 • (n - \K\)\.
KC{l,2,...,n]
Jednotliví sčítanci v této sumě opět nezávisí plně na K, ale pouze na \K\. Přitom pro každé í G {0,1, 2,..., n} je počet těch sčítanců, v nichž \K\ = £, roven ("). Je tedy možno uvedenou sumu částečně sečíst, čímž vychází
\A(0)\ =E(-l)'-Q-(^)!
n
= £(-d'
1=0
takže dostáváme
n (-iY WI=»!lM-
£=0
Rozepíšeme-li tento vztah podrobněji, nakonec obdržíme
1
—> -   pro   n —> oo
e
To znamená, že při velkých číslech n se pravděpodobnost, že náhodně vybraná permutace množiny {1, 2,..., n} nebude mít žádný pevný bod, blíží k hodnotě - .
6