Anzahl der Abbildungen

Neue Frage »

Pascal95 Auf diesen Beitrag antworten »
Anzahl der Abbildungen
Hallo,

ich möchte herausfinden, wie viele Abbildungen es von nach gibt...

Also:
.

Nun ist mir klar, dass jedes Element von genau Möglichkeiten hat, abgebildet zu werden...



Das sind dann Möglichkeiten.


Allerdings wüsste ich gerne, wie viele Injektionen und Surjektionen es gibt.

Da weiß ich gar nicht, wie man anfangen kann...

Vielen Dank !

Wink
Leopold Auf diesen Beitrag antworten »

Sind endliche Mengen?
 
 
Pascal95 Auf diesen Beitrag antworten »

Ja, das dachte ich mir so.
Ibn Batuta Auf diesen Beitrag antworten »

Erstmal Injektivität, das ist einfacher.

Sei und mit (warum?). Nun kannst du die Definition der Injektivität ausnutzen: . Wie viele Möglichkeiten kommen denn da in Frage?


Ibn Batuta
Pascal95 Auf diesen Beitrag antworten »

Hallo.

Für gibt es keine Injektion, da ein Element zwangsläufig mehrfach angenommen werden müsste.

Nun kenne ich ja die Definition, allerdings fällt mir dazu keine logische Überlegung ein, ähnlich der ersten Aufgabe, zu sagen, dass es für das erste Element ... Möglichkeiten gibt, für das zweite gibt es.... u.s.w.

Vielleicht könnte man sich ja überlegen, die Elemente von durchzuzählen, da es hier ja darum geht, dass jedes Element aus nur höchstens einmal angenommen wird verwirrt
Leopold Auf diesen Beitrag antworten »

Ohne Beschränkung der Allgemeinheit sei . Hat die Mächtigkeit , so kann eine Funktion mit einem -Tupel



identifiziert werden. Die Menge all dieser entspricht dann der Menge sämtlicher Funktionen .

Wir betrachten die Ereignisse



Für gilt dann:



Bei der Berechnung der Mächtigkeit von hilft die Siebformel (Formel vom Ein- und Ausschluß). Beachte auch den Zusammenhang mit dieser Formel.
Pascal95 Auf diesen Beitrag antworten »

Eigentlich wollte ich zunächst bei den Injektionen bleiben.

Dazu hatte ich die Idee, dass man vielleicht die Elemente aus B durchzählen sollte, da es hier ja darum geht, dass je zwei Elemente aus B nicht von einem Wert aus A angenommen werden...
Dann gäbe es für das erste Element aus B ja m+1 Möglichkeiten, da es von einem der m Elemente aus A angenommen werden kann, oder von keinem (das darf ja auch sein)...
Leopold Auf diesen Beitrag antworten »

Die Sache mit den Injektionen ist einfach. Es handelt sich um eines der vier Grundprobleme der Kombinatorik (Ziehen mit oder ohne Zurücklegen, mit oder ohne Beachtung der Reihenfolge). Gehe von den Elementen von aus und überlege, was du an Möglichkeiten hast, ihnen der Reihe nach (!) Bilder zuzuweisen.
Pascal95 Auf diesen Beitrag antworten »

Ich würde sagen: Ohne Zurücklegen, aber mit Beachtung der Reihenfolge.
Begründung: Diejenigen, die schon "gezogen" worden sind (also die Bilder), die werden nicht nochmals angenommen -> nicht zurücklegen. Allerdings ist es wichtig, ob f(1)=1 und f(2)=2 oder f(1)=2 und f(2)=1, also die Bilder in einer unterschiedlichen Reihenfolge sind -> mit Beachtung der Reihenfolge.

Das erste Element aus A hat n Möglichkeiten, abgebildet zu werden.
Das zweite Element aus A hat n-1 Möglichkeiten, abgebildet zu werden.
...
Das i-te Element aus A hat n-i+1 Möglichkeiten, abgebildet zu werden.
...
Das m-te Element aus A hat n-m+1=n-(m-1) Möglichkeiten, abgebildet zu werden.

Man sieht ja: Das letzte Element hat nur noch eine Möglichkeit mehr, ist also automatisch bestimmt, wohin es abgebildet werden muss, wenn , also f bijektiv ist.

Daher gibt es Möglichkeiten.

Wenn wir jetzt nicht davon ausgehen, dass , also voraussetzen, dann ist , also gehen wir o.B.d.A. davon aus, es sei .
Nun untersuche ich beide alternativen Schreibweisen für die Produkte:
1. Variante:
Das Produkt geht bis m, also wegen m=n+1 geht es bis n+1. Dann ist der letzte Faktor n-(m-1)=n-(n+1-1)=n-n=0. Damit ist das ganze Produkt gleich Null.
2. Variante (eigentlich nur Indexshift):
Das Produkt geht bis m-1, also wegen m=n+1; m-1=n geht es bis n. Dann ist der letzte Faktor n-(m-1)=n-n=0. Damit ist das ganze Produkt gleich Null.

Habe nebenbei die Tippfehler ausgebessert Augenzwinkern
Ibn Batuta Auf diesen Beitrag antworten »

Stimmt auch. Beispiel hierfür ist und .

Es gibt insgesamt injektive Abbildungen .


Ibn Batuta
Pascal95 Auf diesen Beitrag antworten »

Ok, das freut mich.

Danke euch beiden für die Unterstützung smile

Der Weg zum Ergebnis ist mir selbst noch wichtiger als das Ergebnis als solches.

Streng genommen müssten wir nicht voraussetzen, aber wir würden bemerken, dass im Falle ein Faktor gleich Null wäre und damit das ganze Produkt gleich Null wäre. ==> keine Injektionen (ist ja dann auch richtig).
TommyAngelo Auf diesen Beitrag antworten »

Gut erkannt, aber ich glaube, du hast in deinem vorletzten Beitrag (mit dem Produkt) m und n vertauscht. Man könnte es für auch so schreiben:



Hast du dich schon an die Anzahl der Surjektionen herangewagt?
Pascal95 Auf diesen Beitrag antworten »

Hallo,

ja, das stimmt. Ich habe mich leider verschrieben, dies aber verbessert. Kannst du vielleicht mal drüberschauen, ob das jetzt stimmt Augenzwinkern

Nebenbei habe ich noch etwas hinzugefügt:
Zitat:
Original von Pascal95
Wenn wir jetzt nicht davon ausgehen, dass , also voraussetzen, dann ist , also gehen wir o.B.d.A. davon aus, es sei .
Nun untersuche ich beide alternativen Schreibweisen für die Produkte:
1. Variante:
Das Produkt geht bis m, also wegen m=n+1 geht es bis n+1. Dann ist der letzte Faktor n-(m-1)=n-(n+1-1)=n-n=0. Damit ist das ganze Produkt gleich Null.
2. Variante (eigentlich nur Indexshift):
Das Produkt geht bis m-1, also wegen m=n+1; m-1=n geht es bis n. Dann ist der letzte Faktor n-(m-1)=n-n=0. Damit ist das ganze Produkt gleich Null.


Dass man auch , oder eben schreiben kann, ist mir v.a. durch ein Beispiel wie solches von Ibn Batuta klargeworden, einen formalen Beweis kenne ich nicht.
Ibn Batuta Auf diesen Beitrag antworten »

Zitat:
Original von Pascal95
Dass man auch , oder eben schreiben kann, ist mir v.a. durch ein Beispiel wie solches von Ibn Batuta klargeworden, einen formalen Beweis kenne ich nicht.


Man kann es sich auch wie folgt überlegen, dann kommt man auch drauf. Seien und (damit ich nicht durcheinander komme, benenne ich das einfach um) endliche Mengen und eine Abbildung zwischen Mengen.

Die Frage, die sich bei der Injektivität stellt, ist doch, auf wie viele Möglichkeiten sich verschiedene Elemente aus Elementen unter Beachtung der Anordnungsmöglichkeiten auswählen lassen. Das ist ein kombinatorisches Problem, das man leicht lösen kann.

verschiedene Elemente aus Elementen, lässt sich darstellen als . Wenn man a Elemente auswählt, lassen die sich auf -Möglichkeiten anordnen, also hat man insgesamt doch:




Ibn Batuta
Pascal95 Auf diesen Beitrag antworten »

Ok, das ist natürlich einleuchtend. Daher hatte Leopold wohl schon vorher gefragt, welches Problem hier vorlege. Darauf war meine Antwort ja schon:
Zitat:
Original von Pascal95
Ich würde sagen: Ohne Zurücklegen, aber mit Beachtung der Reihenfolge.
Begründung: Diejenigen, die schon "gezogen" worden sind (also die Bilder), die werden nicht nochmals angenommen -> nicht zurücklegen. Allerdings ist es wichtig, ob f(1)=1 und f(2)=2 oder f(1)=2 und f(2)=1, also die Bilder in einer unterschiedlichen Reihenfolge sind -> mit Beachtung der Reihenfolge.



Nun zu den Surjektionen:
Sehe ich das richtig ?
Die Idee ist also, dass ein m-Tupel für eine Funktion von A nach B steht.
Dieses Tupel () enthält Einträge: . Dies gilt, wenn wir wieder o.B.d.A. annehmen, es sei A von der Gestalt .
Betrachten wir z.B. folgendes Beispiel:
Es sei m=3, n=4 und es ist f(1)=1; f(2)=3; f(3)=4, also .
Leopold Auf diesen Beitrag antworten »

So ist es.

Und jetzt muß man diejenigen zählen, bei denen jedes als Koordinate vorkommt (eventuell mehrfach). Sie bilden die Menge (surjektive Funktionen).
Einfacher erscheint es mir, diejenigen zu zählen, bei denen nicht jedes vorkommt, also die nicht-surjektiven Funktionen.
Es könnte nun in nicht vorkommen. Diese fassen wir zu zusammen.
Oder es könnte in nicht vorkommen. Diese fassen wir zu zusammen.
Und so weiter.
repräsentiert somit eine nicht-surjektive Funktion, wenn oder oder ... oder nicht vorkommt. Daher also



Dummerweise sind die nicht unvereinbar. Daher die Sache mit der Siebformel. Glücklicherweise lassen sich jedoch die Mächtigkeiten der und ihrer Schnitte relativ leicht bestimmen. Die Mächtigkeit eines Schnitts hängt nur von der Anzahl der Schnittfaktoren ab, nicht von der konkreten Auswahl. Also wieder ein kombinatorisches Problem ...

Ich würde erst einmal die Schnittmächtigkeiten berechnen, damit sie dann in der Hauptrechnung zur Verfügung stehen:









Vielleicht gibt es auch einen genialen Kniff, mit dem man die Rechnung ganz anders und kürzer aufziehen kann. Mir fällt jedoch im Moment nichts Besseres ein.
Pascal95 Auf diesen Beitrag antworten »

Hallo,

soweit bis zur Beschreibung der nicht-surjektiven Funktionen habe ich es gut verstanden, leider ist mir aber folgendes nicht klar.

Zitat:
Original von Leopold
Dummerweise sind die nicht unvereinbar.


Ich weiß nicht, was vereinbar in diesem Zusammenhang bedeutet.

Vielen Dank schon mal für deine Hilfe smile
Leopold Auf diesen Beitrag antworten »

unvereinbar (Sprache der Wahrscheinlichkeitsrechnung) = disjunkt (Sprache der Mengenlehre)
Pascal95 Auf diesen Beitrag antworten »

Mit Schnittfaktoren meinst du wohl die Elemente, die im Schnitt enthalten sind.

Leider wüsste ich nicht, wie man herausbekommen soll, wie viele Funktionen es gibt, die j nicht annehmen.

Allerdings weiß ich, dass es genau eine Funktion gibt, die alle Werte bis auf einen nicht annehmen, also .
Hier wird z.B. das letzte Element (das b-te Element) aus B angenommen, da alle anderen Elemente aus B nicht angenommen werden.

Und es ist , da es keine Funktion gibt, die in enthalten ist, also kein Element aus B annimmt.

Ich weiß nicht, ob das jetzt weiterhilft, aber das sind meine einzigen Ideen hierfür...
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von Pascal95
Leider wüsste ich nicht, wie man herausbekommen soll, wie viele Funktionen es gibt, die j nicht annehmen.

Das entspricht der Anzahl aller Funktionen . Mit und , d.h., sind das wieviele Funktionen?
Pascal95 Auf diesen Beitrag antworten »

Aha, auf diese einfache Idee bin ich nicht gekommen ...

Das sind dann Funktionen.
Leopold Auf diesen Beitrag antworten »

Genau so ist es. Auch die Mächtigkeit von bzw. bzw. ... führt wieder auf eines der Grundprobleme der Kombinatorik. Und analog bei den Dreierschnitten, den Viererschnitten usw.
Und die Anzahl der Zweierschnitte (Dreierschnitte, Viererschnitte usw.) läuft auf ein anderes Grundproblem der Kombinatorik hinaus.

Wenn ich das richtig sehe, braucht man für die Rechnung keine Einschränkung hinsichtlich zu machen. Da jedoch ist, falls ist, hat man einen neuen, dieses Mal kombinatorischen Beweis für die Formel hier. Interessant ...
Pascal95 Auf diesen Beitrag antworten »

Ich meine, es ist , da ja 2 Werte aus B nicht angenommen werden...

Oder täusche ich mich da, weil du ja meintest, das führe auf ein anderes kombinatorisches Problem (?)
Leopold Auf diesen Beitrag antworten »

Lies meinen letzten Beitrag genau durch. Es geht da um verschiedene Zählprozesse. Den einen hast du richtig erfaßt. Jetzt noch verallgemeinern. Dann den andern.
Pascal95 Auf diesen Beitrag antworten »

Könnte man vielleicht sagen, dass die Wahrscheinlichkeit, eine Funktion in anzutreffen, die nicht auf ein beliebiges Element aus B abbildet gerade ist ?

Dann wäre die Wahrscheinlichkeit dafür, eine Funktion anzutreffen, die auf zwei verschiedene beliebige Elemente aus B nicht abbildet (?)

Leider könnte ich es mir nicht anders vorstellen...
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von Pascal95
Dann wäre die Wahrscheinlichkeit dafür, eine Funktion anzutreffen, die auf zwei verschiedene beliebige Elemente aus B nicht abbildet (?)

Irgendwie warst du in deinem vorletzten Beitrag schon mal weiter - hast du etwa Leopolds Reaktion missdeutet?

Jedenfalls ist die richtige Wahrscheinlichkeit hier. Damit hast du das für ein konkretes Paar berechnet. Um aber alle solche Paare zu erfassen (was du ja für den Einsatz in der Siebformel brauchst) musst du die zweite Frage beantworten:

Zitat:
Original von Leopold
Und die Anzahl der Zweierschnitte (Dreierschnitte, Viererschnitte usw.) läuft auf ein anderes Grundproblem der Kombinatorik hinaus.
Leopold Auf diesen Beitrag antworten »

Vor allem bringt es keinen Vorteil, jetzt zu Wahrscheinlichkeiten überzugehen (es schadet natürlich auch nicht). Mächtigkeiten genügen. Immerhin entnehmen wir dem letzten Resultat, daß



ist. Das braucht man später beim Übergang von zu .
Pascal95 Auf diesen Beitrag antworten »

Nun müsste man sich wohl überlegen, wie viele Paare es in B gibt...

Da hier das Paar geordnet ist (keine Menge), sind es . Dies muss man doppelt zählen, da es ja zwei mögliche Anordnungen gibt.

Also allgemein für x verschiedene Elemente aus B gibt es Möglichkeiten.

...
Leopold Auf diesen Beitrag antworten »

Siebformel:



Die Summationsbedingung der inneren Summe meint, daß jede -elementige Teilmenge von genau einmal als Kombination der Indizes auftritt. Man darf hier also nicht mehrfach zählen. Beachte die Kommutativität der Durchschnittsoperation. Zum Beispiel ist dasselbe wie . Das darf nur einmal gezählt werden.


Ein Beispiel zur Anwendung der Siebformel findest du hier (Aufgabe 5). Beachte, daß die Fakultäten in der Lösung dort eine andere Ursache haben.
Pascal95 Auf diesen Beitrag antworten »

Wenn ich mich nicht täusche, könnte man dann sagen:
René Gruber Auf diesen Beitrag antworten »

Nein, da bringst du schon wieder etwas bzw. sogar einiges durcheinander. unglücklich

Es ist



denn da links steht ja nur ein solcher Schnitt von Mengen. Über alle derartigen Schritte summiert ergibt sich

,

d.h. dein Faktor gehört da nicht rein! (Eigentlich hatte Leopold das schon in seinem letzten Beitrag erklärt.)
Leopold Auf diesen Beitrag antworten »

Zitat:
Original von René Gruber
(Eigentlich hatte Leopold das schon in seinem letzten Beitrag erklärt.)


@ Pascal95

Hast du den dortigen Link verfolgt? Beispiele erklären manchmal mehr als tausend Worte.
Irgendwie scheint da eine grundlegende Denkblockade bei dir vorzuliegen. Dasselbe Phänomen hatten wir schon hier.
Pascal95 Auf diesen Beitrag antworten »

Hallo,

die Siebformel ist wohl so zu lesen:


Es ist ja für k ungerade gleich 1, für k gerade gleich -1.

Dadurch wird der Summand addiert oder subtrahiert.

Nun kann man kürzer schreiben: ...

Also kann man wohl schreiben .
Leopold Auf diesen Beitrag antworten »

So stimmt es. Den Summanden für kann man natürlich weglassen. Du hattest ja bereits festgestellt, daß leer ist. Wenn man die Summanden in der entgegengesetzten Reihenfolge anordnet, man könnte auch sagen: wenn man durch substituiert, sieht es vielleicht noch etwas schöner aus. Beachte die Symmetrie der Binomialkoeffizienten.

Und was ist nun ?
Pascal95 Auf diesen Beitrag antworten »

Hallo,

man könnte also bis n-1 aufsummieren.
So müsste der Summand für dann ja Null sein, was er nach der Rechnung auch ist, weil und somit das ganze Produkt zu Null wird.

Aber wenn man einfach k durch n-k verändern sich ja auch andere Sachen, denn k taucht ja nicht nur im Binomialkoeffizienten auf. Ansonsten ist mir aber klar (anschaulich, da die nicht-ausgewählten Elemente eindeutig bestimmt sind, was gerade n-k sind).

Es ist ja (nicht-surjektiven Funktionen).

Nun ist also .

Hoffentlich ist das so richtig, und meine Frage bezüglich der Substitution von k durch n-k sich klären wird...
Leopold Auf diesen Beitrag antworten »

Baue in die Summe ein.
Pascal95 Auf diesen Beitrag antworten »

Zunächst wird durch das Minuszeichen vor der Summe die ganzen Vorzeichen der Summanden umgedreht.

Daher kann man schreiben:
.

Allerdings kann ich mir nicht vorstellen, wie man die Potenz in die Summe einbauen könnte...

Hier würde eine Doppelsumme auch nicht helfen, denn Potenzieren ist ja die mehrfache Verkettung von Multiplikation...

Einen Satz, der ähnlich einem ist, der hier helfen würde, lautet:
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von Pascal95
Allerdings kann ich mir nicht vorstellen, wie man die Potenz in die Summe einbauen könnte...

Was kommt raus, wenn du Ausdruck



für berechnest?
Pascal95 Auf diesen Beitrag antworten »

Aha, das ist genau !

Dann kann ich ja einfach schreiben:

.

Vielen Dank smile
Leopold Auf diesen Beitrag antworten »

Oder




Es ist reizvoll, sich speziell die Fälle und anzusehen. Rechne auch konkrete Beispiele.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »