Zliczanie funkcji

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
michals95
Użytkownik
Użytkownik
Posty: 32
Rejestracja: 15 sty 2015, o 22:38
Płeć: Mężczyzna
Lokalizacja: W-wa
Podziękował: 5 razy
Pomógł: 1 raz

Zliczanie funkcji

Post autor: 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.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5747
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 130 razy
Pomógł: 526 razy

Zliczanie funkcji

Post autor: arek1357 »

Są to suriekcje i oczywiście \(\displaystyle{ n \ge m}\)
Awatar użytkownika
Medea 2
Użytkownik
Użytkownik
Posty: 2491
Rejestracja: 30 lis 2014, o 11:03
Płeć: Kobieta
Podziękował: 23 razy
Pomógł: 479 razy

Zliczanie funkcji

Post autor: 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ń.
ODPOWIEDZ