Zusammenhang Stirlingzahlen und Siebformel |
| 22.02.2014, 12:23 | Brayn410 | Auf diesen Beitrag antworten » | ||
| Zusammenhang Stirlingzahlen und Siebformel Hallo ihr Lieben 
wir schrieben vor kurzem eine Probeklausur in der folgende Frage vor kam: Wieviel surj. Abbildungen gibt es von A -> B wenn A={1,2,3,4} und B={1,2,3}. Ich habe die Aufgabe über die Stirling Zahlen zweiter Art gelöst, allg. quasi so: m! * S(n,m) = m!*( S(n-1,m-1) + m*(S(n-1,m)) ) Die Zahlen aus der Aufgabenstellung eingesetzt ergibt somit: 3! * S(4,3) = S(3,2) + 3*S(3,3) = 6 * (3 + 3) = 36 Ich hab das mal abgekürzt, wer will kann es ja noch nachrechnen
Nach der Probeklausur hat unser Dozent die Aufgabe mit uns noch besprochen und er löste die Aufgabe über die Siebformel. Im folgenden entspricht # der Anzahl: # aller surj. Abb = # aller Abb - #(Abb. die 1 nicht treffen) - #(Abb. die 2 nicht treffen) - #(Abb. die 3 nicht treffen) + #(Abb. die 1 und 2 nicht treffen) + #(Abb. die 1 und 3 nicht treffen) + #(Abb. die 2 und 3 nicht treffen) = 3^n - 3*2^n + 3*1 = 36 Somit sind die Ergebnisse schonmal gleich, kann man das auch verallgemeinern? Nun meine Frage: Kann man in allen Aufgaben bei denen die Siebformel die Lösung des Problems ist, auch die Stirling Zahlen zweiter Art multpliziert mit Fakultät der Mächtigkeit der Zielmange, benutzen? (also so wie ich es oben auch gemacht habe) oder war das nur Zufall? Falls es einen Zusammenhang gibt und ihr wisst wer diesen Zusammenhang entdeckt hat wäre es auch toll, wenn ihr mir diesen Namen nennen könnt, damit ich später (in der Klausur oder ähnlichem) darauf verweisen kann.
Liebe Grüße Matthias Meine Ideen: Meine Ideen stehen ja schon oben. |
||||
| 22.02.2014, 12:38 | HAL 9000 | Auf diesen Beitrag antworten » | ||
In dieser Allgemeinheit muss man das sicher verneinen, da die Siebformel in weit allgemeineren Szenarien anwendbar ist, als du dir im Moment vorstellen magst. Z.B. muss ja i.a. nicht mal "Symmetrie" zwischen den Mengen vorliegen, auf die die Siebformel angewandt wird. |
||||
| 22.02.2014, 14:14 | Brayn410 | Auf diesen Beitrag antworten » | ||
Hallo HAL 9000, zuerst mal vielen Dank für deine schnelle Antwort
Ich verstehe aber nicht so ganz was du mit:
Ich kenne die Symmetrie Gruppen und die symmetrie Eigenschaft auf Relationen, dennoch erschließt sich mir der Zusammenhang dazwischen nicht. Oder gibt es noch eine weitere Symmetrieeigenschaft von Mengen die ich noch nicht kenne. Dann noch generell, aus deiner Antwort schließe ich dass du sagst, die Mengen die bei den Stirling Zahlen müssen diese für mich unbekannte Symmetrie Eigenschaft erfüllen. Ich weiß, du sagst es nicht direkt, aber du implizierst es ja quasi, oder? Liebe Grüße und nochmals vielen Dank, Matthias |
||||
| 22.02.2014, 14:31 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Mit "Symmmetrie" meine ich, dass dein Anwendungsbeispiel der Siebformel - so wie viele andere auch - die spezielle Eigenschaft hat, dass die Mächtigkeit des Durchschnitts von der Ausgangsmengen nur von , nicht aber von den Mengen selbst abhängt. Falls dir immer noch nicht klar ist, was ich meine, hier ein einfaches Beispiel der Siebformelanwendung, wo das nicht so ist: Wir suchen die Anzahl der natürlichen Zahlen , die teilerfremd zu sind. Dazu definieren wir ... Menge der Zahlen aus , die durch 2 teilbar sind ... Menge der Zahlen aus , die durch 3 teilbar sind ... Menge der Zahlen aus , die durch 5 teilbar sind Die gesuchte Anzahl ist dann Wie willst du das mit Stirlingzahlen rechnen? 
P.S.: Mir ist klar, dass man obiges Beispiel eigentlich besser mit der Eulerschen Phi-Funktion rechnet - für diejenigen, die das gerne posten möchten. 
|
||||
| 22.02.2014, 14:50 | Brayn410 | Auf diesen Beitrag antworten » | ||
Hallo HAL 9000, vielen Dank für deine Hilfe. Ich glaube ich habe es verstanden
Vorallem nach deinem Beispiel (was wir so ähnlich auch schonmal machten) wurde mir klar, dass man die Stirling Zahlen nur auf zwei Mengen anwenden kann. Dann merke ich mir wohl doch besser: "Stirling Zahlen nur für surj. Abbildungen und Partitionen" und "Siebformel ist allgemeiner". Wobei es mir dennoch schwer fällt zu erkennen wann ich in einer Aufgabe die Siebformel benutzen kann/sollte. Liebe Grüße Matthias |
||||
| 22.02.2014, 14:52 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Ein Indiz ist, wenn man die Mächtigkeit der Vereinigung von Mengen berechnen will, wo man die Mächtigkeit beliebiger Durchschnitte dieser Mengen relativ leicht bestimmen kann. |
||||
| Anzeige | ||||
|
|
||||
| 22.02.2014, 15:11 | Brayn410 | Auf diesen Beitrag antworten » | ||
Stimmt so wie in deinem Beispiel.
Aber ich fand in einem Mathebuch z. B. eine Aufgabe die hieß: "Wie viele fünfstellige Dualzahlen gibt es die mit 11 beginnen oder mit 00 enden?" [MfI, Band 1 (Teschl & Teschl)] Wenn mir keine der "Standardformeln" passend erscheinen, mache ich mir meist eine abstrakte Skizze, sowas wie: Erlaubt ist: 1 1 _ _ _ und _ _ _ 0 0 bei den leeren Feldern ist egal was da steht daher: 2^3 + 2^3 = 2^4 = 16 Richtig wäre aber 2^3 + 2^3 - 2^1 = 8 + 8 - 2 = 14 Jetzt wo ich die Lösung weiß, kann ich mir vorstellen wo mein Fehler liegt, links hatte ich 1 1 0 0 0 einmal gezählt und rechts einmal, das heißt ich hab diese Form dopplet gezählt, also würde ich ein - 1 und somit 15 als Endergebnis verstehen, vermutlich ist das oder aber als exklusives oder zu verstehen und deshalb wir es zwei mal abgezogen, oder was meinst du?
Liebe Grüße Matthias |
||||
| 22.02.2014, 17:38 | Math1986 | Auf diesen Beitrag antworten » | ||
Nein, kein exklusives oder. Das Problem ist, dass die Zahlen 11100 und 11000 jeweils in beide Klassen fallen, also doppelt gezählt werden. Das wäre dann der Durchschnitt der Mengen M1 und M2, wobei M1=11... und M2=...00 Wenn du die Siebformel anwendest dann musst du eben von der Summe der Mächtigkeiten der beiden Mengen noch die Mächtigkeit des Durchschnitts abziehen. Allgemein kannst du dir das Oder mengentechnisch als eine Vereinigung von Mengen vorstellen. Somit kannst du die Siebformel anwenden. |
||||
| 22.02.2014, 18:24 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Ich meine, dass du auch 1 1 1 0 0 doppelt gezählt hast, und deswegen nicht nur 1, sondern 2 subtrahiert werden muss.
EDIT: Oh sorry, muss meine Brille aufsetzen - hab deinen Beitrag noch gar nicht gesehen.
|
||||
| 22.02.2014, 21:04 | Brayn410 | Auf diesen Beitrag antworten » | ||
Hallo ihr Zwei, vielen vielen Dank für eure Hilfe Ihr habt mir sehr geholfen.
Liebe Grüße Matthias P.S.: Schließt sich der Thread automatisch oder kann ich das irgendwo machen? |
||||
| 23.02.2014, 09:47 | Math1986 | Auf diesen Beitrag antworten » | ||
|
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
