Anzahl der Abbildungen - Seite 2

08.10.2011, 21:03	Pascal95	Auf diesen Beitrag antworten »
Ich habe es mal mit m=5; n=2 ausprobiert. Es gilt 32 Abbildungen gesamt, keine Injektionen (weil m>n), 30 Surjektionen, 2 Funktionen, die weder surjektiv noch injektiv sind (1: alles auf 1 abbilden, 2: alles auf 2 abbilden). Edit: Für $\begin{eqnarray} m=n \end{eqnarray}$ ist mir aufgefallen, dass $\begin{eqnarray} \|I\|=\|S\| \end{eqnarray}$ , also die Anzahl der Injektionen gleich der Anzahl an Surjektionen ist (bisher nur eine Vermutung, Beweis ausstehend). Edit 2: Es gilt für $\begin{eqnarray} m=n \end{eqnarray}$ : $\begin{eqnarray} \|I\|=\|S\|=m! \end{eqnarray}$ . Das habe ich für die Injektionen einfach zeigen können, für die Surjektionen habe ich es noch nicht.
09.10.2011, 14:18	Leopold	Auf diesen Beitrag antworten »
Ziehe die Sache anders herum auf. Überlege dir, wann es nur bijektive Abbildungen zwischen endlichen Mengen geben kann. Und zwar ganz elementar. Was kann man in diesem Fall aus der Injektivität (Surjektivität) einer Abbildung folgern?
09.10.2011, 14:25	Pascal95	Auf diesen Beitrag antworten »
Eine notwendige Bedingung für die Existenz von Bijektionen zwischen A und B ist, dass $\begin{eqnarray} m=n \end{eqnarray}$ gilt. Dabei kommt mir gerade der Gedanke, dass es ja genau $\begin{eqnarray} m! \end{eqnarray}$ Bijektionen von $\begin{eqnarray} A \end{eqnarray}$ auf $\begin{eqnarray} A \end{eqnarray}$ mit $\begin{eqnarray} \|A\|=m \end{eqnarray}$ gibt. (auch "Permutationen" genannt) Dann ist jede Surjektion eine Bijektion und jede Injektion eine Bijektion. "Surjektiv" heißt ja, dass jedes Element aus B auch ein Urbild hat, da aber $\begin{eqnarray} \|A\|=\|B\| \end{eqnarray}$ gilt, müssen diese so verteilt werden, dass jedes Urbild aus genau einem Element besteht. Somit sind alle Surjektionen auch Injektionen und damit sind diese Abbildungen Bijektionen!
09.10.2011, 14:35	Leopold	Auf diesen Beitrag antworten »
Und somit ist klar, daß $\begin{eqnarray} \|I\| = \|S\| \end{eqnarray}$ gilt. Da du diese Mächtigkeiten aber auf verschiedene Arten berechnet hast, müssen diese Berechnungen hier dasselbe Ergebnis liefern. Fazit: Du hast eine interessante Formel mit Binomialkoeffizienten und Fakultäten bewiesen. Nämlich welche? Und dann noch der Fall $\begin{eqnarray} n>m \end{eqnarray}$ . Was folgt hier für eine Formel?
09.10.2011, 14:46	Pascal95	Auf diesen Beitrag antworten »
Hmm, welche Formel mit Binomialkoeffizienten und Fakultäten man hier bewiesen hat ? Meinst du diese Hier ?
09.10.2011, 16:34	Leopold	Auf diesen Beitrag antworten »
Ja, das meine ich. Vor allem die letzte Formel in meinem letzten Beitrag dort. Die ist jetzt sozusagen neu bewiesen, ohne lineare Algebra, ganz mit einer kombinatorischen Überlegung. Und alles begann einmal mit der Frage nach der Anzahl der surjektiven Funktionen. Interessant ...
Anzeige

« vorherige Seite 12

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »