Počet ekvivalencí s daným počtem tříd
Úloha číslo: 4425
Řešení
Budeme počítat ekvivalence s \(k\) označenými třídami, nakonec výsledek vydělíme \(k!\).
Ekvivalence s \(k\) označenými třídami odpovídají funkcím z \(\{1,\ldots,n\}\) do \(\{1,\ldots,k\}\), které jsou surjektivní (na). Od počtu všech funkcí \(k^n\) odečteme počet těch, které nejsou surjektivní, a ten spočítáme pomocí principu inkluze a exkluze.
Označme \(F\) množinu všech nesurjektivních funkcí (tedy takových, v jejichž oboru hodnot chybí nějaký prvek z \(\{1,\ldots,k\}\)). Tato množina je sjednocením množin \(F_i\) funkcí, v jejichž oboru hodnot chybí číslo \(i\).
Snadno dokážeme, že \(|F_i|=(k-1)^n\). Obdobně \(|F_i\cap F_j|=(k-2)^n\) pro \(i\ne j\). Obecně průnik \(t\)-tice množin má \((k-t)^n\) prvků.
Podle principu inkluze a exkluze máme: \[ |F| = \sum_{t=1}^n (-1)^{n+1} {n\choose t} (k-t)^n. \] Z toho pro počet surjektivních funkcí: \[ k^n - |F| = \sum_{t=0}^n (-1)^t {n\choose t} (k-t)^n. \]
Nezapomeneme na závěrečné vydělení \(k!\).
Odpověď
\[ {1\over k!}\cdot \sum_{t=0}^n (-1)^t {n\choose t} (k-t)^n \]
