Zliczanie funkcji

[michals95]

Funkcja \(\displaystyle{ f: \left[ n\right] \rightarrow \left[ m\right]}\) jest zielona, jeśli prawdziwe jest zdanie : \(\displaystyle{ (\forall y \in [m]) (\exists x\in [n]) \ f(x) = y}\). Ile jest funkcji zielonych z \(\displaystyle{ [n]}\) na \(\displaystyle{ [m]}\). Wydaje mi się, że to zadanie da się rozwiązać korzystając z zasady włączeń i wyłączeń, ale nie mam żadnego pomysłu.

[arek1357]

Są to suriekcje i oczywiście \(\displaystyle{ n \ge m}\)

[Medea 2]

Odpowiedź brzmi \(\displaystyle{ \sum_{k=0}^m {m \choose k} (m - k)^n (-1)^k}\) i rzeczywiście wynika z zasady włączeń i wyłączeń.