\input /home/pasky/school/fastex/lib.tex

\subchapter{Princip inkluze a exkluze (PIE)}{

%% \n -> prunik, \u -> sjednoceni



\example{

	$$ |A_{1} \cup{} A_{2}| = |A_{1}| + |A_{2}| - |A_{1} \cap{} A_{2}| $$
	$$ |A_{1} \cup{} A_{2} \cup{} A_{3}| = |A_{1}| + |A_{2}| + |A_{3}|
	                          - |A_{1} \cap{} A_{2}|
	                          - |A_{1} \cap{} A_{3}|
	                          - |A_{2} \cap{} A_{3}|
	                          + |A_{1} \cap{} A_{2} \cap{} A_{3}| $$

}

\theorem{}{PIE}{
	Jsou-li $A_{1},A_{2},\ldots{},A_{n}$ konečné množiny:

	$$ |\setjoin{i=1}{n}{A_{i}}|
	       = \sum_{k=1}^{n}{\undernote{(-1)^{k+1}}{\textnote{parita}}
	                        \cdot \sum_{I \in{} \cn{\{1,..,n\}}{k}}{
	                               |\setcommon{i \in{} I}{}{A_{i}}|}
	                         } $$

	(Ve vnořené sumě sčítáme přes všechny $k$-prvkové podmnožiny množiny $1..n$.)


\proof{
	Nechť $x$ je libovolný prvek z $A_{1} \cup{} A_{2} \cup{} \cdots{} \cup{} A_{n}$.
	Pro $n=1$, $n=2$ viz diagramy množin, nakreslit si, kam který prvek přispívá:
	$+1 -1 +1 \cdots{}$
	
	Kolikrát je počítán $x$ vlevo, kolikrát vpravo?
	Vlevo jednou --- triviální.

\scpart{Vpravo}{
	
	 Nechť $j$ označuje počet množin $A_{i}$, do kterých patří $x$.

\example{
	  $$x \in{} A_{1}, \ldots{}, A_{j}$$
	  $$x \notin{} A_{j+1}, \ldots{}, A_{n}$$
}

	Pak platí:
	 $$ \#x = \cn{j}{1} - \cn{j}{2} + \cn{j}{3} - \cdots{} + (-1)^{j-1} \cn{j}{j} $$
	  $$ = \sum_{i=1}^{j}{(-1)^{i-1} \cn{j}{i}} + 1 - 1 $$


	Obracíme znaménko a paritu:

	$$ = 1 - \sum_{i=0}^{j}{(-1)^i \cn{j}{i}} $$
	$$ = 1 - (-1 + 1)^j $$
	$$ = 1 $$
	\qed


}

}


\example{

	$$ |X| = \{1, \ldots, n\},\ |Y| = \{1, \ldots, l\},\ n \ge{} l $$

	Kolik existuje zobrazení z $X$ {\bf{}na} $Y$?

	Všech zobrazení z $X$ do $Y$ je $l^n$.
	Nechceme počítat ta, ve kterých se na nějaký prvek $Y$ nezobrazuje žádný prvek z $X$:
	$$\existss{y \in{} Y}:\ \forall{x \in{} X},\ f(x) \ne y.$$

	Pro všechna $i = 1,\ldots,l$ platí:

		$$ A_{i} = \{j\colon X \to{} Y\ |\ \forall{x \in{} X},\ f(x) \ne i \} = \{ j\colon X \to{} Y-\{i\} \} $$
		$$ |A_{i}| = (l-1)^n $$

	Pro $i_{1} \not = i_{2}$:

		$$ A_{i_{1}} \cap{} A_{i_{2}} = \{ f\colon X \to{} Y-\{i_{1}, i_{2}\} \} $$
		$$ |A_{i_{1}} \cap{} A_{i_{2}}| = (l-2)^n $$

	Pro $\displaystyle{\{ i_{1}, \ldots, i_{k} \} \in{} \cn{\{1, \ldots, l\}}{k}}$:

		$$ A_{i_{1}} \cap{} \cdots \cap{} A_{i_{k}} = \{ f\colon X \to{} Y-\{i_{1},\ldots,i_{k}\} \} $$
		$$ \{A_{i_{1}} \cap{} \cdots \cap{} A_{i_{k}}\} = (l-k)^n $$

	Počet zobrazení z $X$ na $Y$ je:

		$$ l^n - |\setjoin{i=1}{l}{A_{i}}| = $$
		        $$ = l^n - \Bigg(\cn{l}{1}(l-1)^n - \cn{l}{2}(l-2)^n + \cn{l}{3}(l-3)^n - \cdots + $$
		        $$  + (-1)^{l-2}\cn{l}{l-1}(l-(l-1)^n) + (-1)^{l-1}\cn{l}{l}(l-l)^n\Bigg) = $$
		        $$ = \sum_{k=0}^{l-1}{(-1)^k\cn{l}{k}(l-k)^n} $$

}

}

}

\bend