Menge der surjektiven Abbildungen anhand der Rekursionsformel
Neue Frage »

30.01.2013, 22:13 Gosat Auf diesen Beitrag antworten »
Menge der surjektiven Abbildungen anhand der Rekursionsformel
Ich steh bei einer einfachen Formel auf dem Schlauch :/
Wir haben eine Rekursionsformel für die Menge der surjektiven Abbildungen bekommen, aber ich komm nie auf das richtige Ergebnis und sehe einfach nicht wo mein Fehler ist.

Formel: sur(p, n) = p * (sur(p-1, n-1) + sur(p, n-1))
sur(0, 0) = 1
sur(0, n) = 0 für n > 0
sur(p, 0) = 0 für p > 0

Versuch sur(2, 4), das Ergebnis sollte 14 sein

2*(sur(1, 3) + sur(2, 3))
=2*(1*(sur(0, 2)+ sur(1,2)) + 2*(sur(1, 2) + sur(2, 2))
=2*(0+1*(sur(0,1) + sur(1,1)) + 2*(1*sur(0, 1) + sur(1, 1)) + 2*(sur(1, 1) + sur(2, 1))
=2*(0+0+1*1+0) + 2*(1*0+1*1)+2*(1*1+0)
=2+2+2=6

Diese ganzen Rekursionen verwirren mich total unglücklich
30.01.2013, 23:53 Mystic Auf diesen Beitrag antworten »
RE: Menge der surjektiven Abbildungen anhand der Rekursionsformel
Zitat:
Original von Gosat
Formel: sur(p, n) = p * (sur(p-1, n-1) + sur(p, n-1))

Bist du sicher, dass es nicht

sur(p, n) = sur(p-1, n-1) + p*sur(p, n-1)

heißt? verwirrt
31.01.2013, 00:05 RavenOnJ Auf diesen Beitrag antworten »

wie ist sur(p,n) definiert? Anzahl surjektiver Abbildungen einer p-elementigen auf eine n-elementige Menge?
31.01.2013, 00:40 Mystic Auf diesen Beitrag antworten »

Zitat:
Original von RavenOnJ
wie ist sur(p,n) definiert? Anzahl surjektiver Abbildungen einer p-elementigen auf eine n-elementige Menge?

Wohl eher andersrum... Big Laugh

Irgendwie erinnert mich das an die Rekursionsformel für Stirlingzahlen 2.Art



mit den Anfangsbedingungen

und
für k = 0 < n oder n < k.
31.01.2013, 00:47 Mystic Auf diesen Beitrag antworten »

...
31.01.2013, 01:28 RavenOnJ Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
Zitat:
Original von RavenOnJ
wie ist sur(p,n) definiert? Anzahl surjektiver Abbildungen einer p-elementigen auf eine n-elementige Menge?

Wohl eher andersrum... Big Laugh


Ich hatte die Rekursionsformel nicht analysiert, hatte nur mal kurz reingeguckt.
 Anzeige 
 
31.01.2013, 01:42 RavenOnJ Auf diesen Beitrag antworten »

Zitat:
Original von Mystic

Irgendwie erinnert mich das an die Rekursionsformel für Stirlingzahlen 2.Art


Genau das sind sie auch: "Anzahl der Möglichkeiten, eine n-elementige Menge in k nichtleere disjunkte Teilmengen aufzuteilen" (wikipedia), nichts anderes ist ja die Zahl der surjektiven Abbildungen einr n-elementigen auf eine k-elementige Menge. Von den Stirlingzahlen hatte ich noch nie gehört, wieder was gelernt.
31.01.2013, 09:42 Mystic Auf diesen Beitrag antworten »

Zitat:
Original von RavenOnJ
Genau das sind sie auch: "Anzahl der Möglichkeiten, eine n-elementige Menge in k nichtleere disjunkte Teilmengen aufzuteilen" (wikipedia), nichts anderes ist ja die Zahl der surjektiven Abbildungen einr n-elementigen auf eine k-elementige Menge. Von den Stirlingzahlen hatte ich noch nie gehört, wieder was gelernt.

Ja, das war mir wohl bewußt, als ich das oben schrieb... Schließlich gab es hier schon epische Schlachten unter dem Titel "Siebformal versus Stirlingzahlen 2.Art", wie könnte ich also das auch vergessen... Big Laugh
31.01.2013, 10:39 Leopold Auf diesen Beitrag antworten »

siehe auch hier
Neue Frage »
Antworten »



Verwandte Themen

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


MatheBoard » Hochschulmathematik » Stochastik & Kombinatorik » Menge der surjektiven Abbildungen anhand der Rekursionsformel