1. (a) [2 body] Definujte, kombinační číslo $\binom{n}{k}$ (včetně potřebných předpokladů ohledně čísel $n$ a $k$)

   (b) [8 bodů] Ukažte, že pro celá čísla $k$, $m$, $n$ splňující $k \le m$ a $k \le n$, platí:

$$\sum_{i = 0}^{k} \binom{m}{i} \binom{n}{k-i} = \binom{m+n}{k}$$

2. Pro $d \in \natnums$ definujeme graf $G_a$ takto: $V(G_a) = (0,1,. ..,d)$, tj. jeho vrcholy jsou všechny posloupnosti $d$ čísel, v nichž se vyskytují pouze čísla $0, 1, ..., d$. Dvě takové posloupnosti tvoří hranu právě tehdy, když se liší ve všech souładnicích. Zde je napriklad obrázek $G_z$:

   (a) [2 body] Definujte pojem barevnost grafu.

   (b) [4 body] Jakou barevnost má $G_2$? Odůvodněte dostatečně obě nerovnosti, tj. najděte nějaké optimální obarvení a dokažte, že nestačí méně barev.

   (c) [6 bodů] Jakou barevnost má $G_d$? Odůvodněte dostatečně obě nerovnosti. Tedy pro důkaz jedné nerovnosti popište přesně nějaké optimální obarvení (tj. když Vám někdo dá nějakou posloupnost délky $d$, ve které jsou jen čísla $0,...,d$, tak byste měli být snadno schopni říct, jakou jí přiřadíte barvu) =4 a odůvodněte, že tato funkce splňuje podmínky obarvení. Abyste odůvodnili druhou nerovnost, tak dokažte, že nestačí méně barev.

3. [4 + 10 bodů] Definujte pojmy šířka a výška částečně uspořádáné množiny $(X, \le)$. Formulujte a dokažte větu o jejich vztahu (Věta o dlouhém a širokém).

4. (a) [2 body] Definujte pojem podmíněná pravděpodobnost

   (b) [4 body] Jaká je střední hodnota počtu šestek při deseti hodech běžnou šestistěnnou kostkou?

   (c) [6 body] Hodím dvěma běžnými šestistěnnými kostkami, černou a bílou. Určete pravděpodobnost, že součet hodů je alespoň sedm za podmínky, že na bílé kostce padlo sudé číslo.

5. (a) [2 body] Definujte pojem bipartitní graf.

   (b) [10 bodů] Určete, pro které hodnoty $n \in N$ existuje bipartitní graf, jehož obě partity mají velikost n, vsechny vrcholy jedné partity maji liché stupně a všechny vrcholy druhé partity mají stupně sudé. (Nápověda: vrcholy jedné partity nemusí mít všechny stejný stupen.) Úplné řešení by mělo obsahovat dvě části:

   • Měli byste formulovat nějakou podmínku, kterou musí $n$ splňovat, a dokázat, že když ji nesplňuje, tak takový graf najít nejde.

   • Potom byste, pro každé $n$, které splňuje Vaši podmínku, měli najít graf $G_n$, který splňuje požadavky popsané výše.