5. cvičení

Již minule jsme si ukázali, že bez podmínky na neprázdnost množin je odpovědí $5\cdot 4^{n-1}$.

Nyní použijeme princip inkluze a exkluze. Víme, že obecně počet způsobů, jak rozdělit $n$ prvků do $k$ množin s daným omezením je $k\cdot (k-1)^{n-1}$. Máme-li tedy 5 množin, prvky do $k$ množin můžeme rozdělit ${5\choose k}k(k-1)^{n-1}$ způsoby, kde kombinační číslo na začátku říká kolika způsoby si můžeme vybrat $k$ množin, které budeme plnit. Nyní již přímo použijeme princip inkluze a exkluze: Podíváme se, kolika způsoby můžeme naplnit 5 množin, odečteme od toho počet způsobů, kterými můžeme naplnit 4 množiny, přičteme způsoby na plnění 3 množin a tak dále. Nakonec tedy dostáváme $$\sum_{i=1}^{5}(-1)^{i+1}\cdot{5 \choose i}\cdot i\cdot (i-1)^{n-1} = 1\cdot 5\cdot 4^{n-1} - 5\cdot 4\cdot 3^{n-1} + 10\cdot 3\cdot 2^{n-1} - 10\cdot 2\cdot 1 ^{n-1} +5 \cdot 1\cdot 0^{n-1}.$$ Poznámka stranou: Princip Inkluze a Exkluze zní $$\left|\bigcup _{i\in M} A_i \right|= \sum_{i\in {\mathcal P}(M)}(-1)^{|i|+1}\cdot\left|\bigcap_{j \in i}A_j\right|.$$ Ve slovech tedy máme množinu $M$ množin $A_i$, a zajímá nás počet prvků ve sjednocení všech $A_i$. Ten se rovná součtu průniků velikostí všech jejích podmnožin, kde velikosti liše velkých podmožin přičítáme normálně a sudě velkých se záporným znaménkem (takže vlastně odčítáme). Člověk by se mohl v našem případě ptát, co je vlastně množina $M$ a co jsou jednotlivá $A_i$? Odpověď je, že jsme princip inkluze a exkluze použili nějak tak mimochodem, náš výsledek není sejdnocením množiny $M$. Množina $\cup A_i$ bude v tomto případě množina všech rozdělení, kde všech pět množin $A,B,C,D,E$ využito není (tedy alespoň jedna zůstane nevyužitá. Jednotlivých množin $A_i$ máme pět, a každá z nich odpovídá případu, kdy jedna pevná z množin $A,B,C,D,E$ zůstane nevyužita. My jsme potřebovali spočíst $\cup A_i$, abychom věděli, co vlastně máme od hodnoty $5\cdot 4^{n-1}$, se kterou jsme začínali, odečíst. Takové použití principu inkluze a exkluze je však velmi časté (ve skutečnosti častější než možnost tento princip aplikovat "přímo".