Santa Claus — modified 2021-11-10 21:39 (420 days ago) — edit — reply
> 1. Kolik je zobrazení $f: [n] \to [n-1]$, které jsou na?
1. Odebereme prvek $i$ z $[n]$. [$n$ možností]
2. Spočítáme počet bijekcí $f: [n] \setminus \{i\} \leftrightarrow [n-1]$ [$(n-1)!$ možností]
3. Poté prvku $i$ přiřadíme nějaký prvek z $[n-1]$, do kterého se zobrazí. [$n-1$ možností]
4. Tento počet ještě vydělíme dvěma, protože každé takové zobrazení naším způsobem připočteme dvěma způsoby:
Pro každé zobrazení budou pro jeden prvek z $[n-1]$ existovat dva prvky z $[n]$, které se do něj zobrazí, přičemž naše $i$, které jsme původně vyřadili, můžou být oba dva.
Takže: $\#= \frac{n\cdot (n-1)!\cdot (n-1)}{2}$
> 2. Kolik je zobrazení $f: [n] \to \{0,1\}$, které jsou na?
Spočítáme počet všech zobrazení a odečteme dvě - ty, které každý prvek zobrazí do stejného prvku.
$\#= 2^n - 2$