#surjektiver Funktionen, Inklusion/Exklusion

17.01.2016, 10:42	Crymson	Auf diesen Beitrag antworten »
#surjektiver Funktionen, Inklusion/Exklusion Hallo Ich stehe vor der Aufgabe, die Formel für die Anzahl der surjektiven Funktionen einer Menge {1,...,n} in die Menge {1,...,k} mit n $\begin{eqnarray} \geq \end{eqnarray}$ k zu beweisen: $\begin{eqnarray} \sum\limits_{i=0}^{k} (-1)^{i} \begin{pmatrix} k \\i \end{pmatrix} (k-i)^{n} \end{eqnarray}$ Als Hinweis soll ich das Inklusions-Exklusionsprinzip verwenden. Gut, sei also A... Menge aller Funktionen von {1,...n} -> {1,..,k} und $\begin{eqnarray} A_{i} \end{eqnarray}$ ... Menge aller dieser Funktionen mit $\begin{eqnarray} i \notin f(\{1,...,n\}) \end{eqnarray}$ mit i aus {1,..,k}:=I die gesuchte Anzahl wäre dann $\begin{eqnarray} \|A- \bigcup\limits_{i=1}^{k} A_{i}\| = \|A\| - \sum\limits_{I\subseteq\{1,...,k\};I\neq\{\}}(-1)^{\|I\|-1} \|\bigcap\limits_{i\in I}A_{i}\| \end{eqnarray}$ Die Anzahl aller Funktionen minus der nicht surjektiven, $\begin{eqnarray} \|A\| = k^{n} \end{eqnarray}$ somit kann ich schreiben: $\begin{eqnarray} k^{n} - \sum\limits_{i=1}^{k} (-1)^{i-1} \|\bigcap\limits_{i \in I} A_{i}\| \end{eqnarray}$ wenn das so stimmt? sieht es ja schon einmal ganz gut aus. Nur weiß ich jetzt nicht weiter, wie ich den Durchschnitt zu interpretieren/aufzulösen habe? Wie gehts jetzt weiter?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »