Úkoly z Kombinatoriky a grafů, 2. série

Veškerá tvrzení precizně zdůvodněte.

(2.1) Dokažte, že posloupnost kombinačních čísel

\binom{n}{0}, \binom{n}{1}, \binom{n}{2}, …, \binom{n}{⌊n/2⌋}

je rostoucí. 4 body

(2.2) Nechť π je náhodná permutace množiny {1, 2, …, n} (vylosovaná tak, že všechny permutace měly stejnou pravděpodobnost). Pevný bod je takové číslo k, že π(k) = k. Určete střední hodnotu počtu pevných bodů v náhodné permutaci, neboli hodnotu

𝔼_{π} [|{k; π(k) = k}|] .

6 bodů