Wie viele surjektive Funktionen gibt es?

28.04.2013, 21:04	sartari	Auf diesen Beitrag antworten »
Wie viele surjektive Funktionen gibt es? Hallo, eigentlich eine relativ einfache Frage: Wie viele surjektive boolesche Funktionen $\begin{eqnarray} f: \lbrace 0,1\rbrace ^n \rightarrow \lbrace 0,1\rbrace \end{eqnarray}$ gibt es? Da wäre meine Antwort $\begin{eqnarray} 2^{2^n} - 2 \end{eqnarray}$ weil die Zielmenge aus 2 Elementen besteht und es so nur 2 Möglichkeien gibt, dass keine surjektive Funktion entsteht, nämlich dass alle auf 1 abbilden oder auf 0. Jetzt gibt es noch: Wie viele surjektive boolesche Funktionen $\begin{eqnarray} f: \lbrace 0,1\rbrace ^n \rightarrow \lbrace 0,1\rbrace ^2 \end{eqnarray}$ gibt es? Und da schein ich irgendwie ein Brett vor dem Kopf zu haben. Also für n=1 gibt es keine Surjektivität, weil der Definitionsbereich kleiner ist als die Zielmenge oder? Und dann irgendwie so: Ich brauche 4 Elemente aus der Definitionsmenge, $\begin{eqnarray} \binom{2^n}{4} \end{eqnarray}$ (?), die dann jeweils genau einen unterschiedlichen Funktionswert zugeordnet haben. Dann brauch ich noch jeweils die Anordnungsmöglichkeiten innerhalb der Definitionsmenge oder?
28.04.2013, 21:37	sartari	Auf diesen Beitrag antworten »
Ok, kann leider nicht mehr editieren. Ist das einfach so? Aus der Definitionsmenge ohne Zurücklegen und mit Reihenfolge ziehen, also $\begin{eqnarray} \dbinom{2^n}{4} \end{eqnarray}$ ?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »