Textversion des Videos

Transkript Permutationsgruppe – Stirlingzahlen erster Art

Hi! Dieses Video befasst sich mit den Stirlingzahlen erster Art. Wir haben hier eine kleine Einführung. Also, es ist zwar eine Einführung, aber ihr solltet schon Vorkenntnisse mitbringen. Ihr solltet zumindest das Abi haben, wissen, was ist eine Permutation, was ist Zykelschreibweise. Ich zeige das noch mal kurz, erkläre es aber nicht ausreichend, würde ich sagen. Okay, kommen wir zu den Stirlingzahlen: Die Stirlingzahl, Sn,m ist definiert als, das Ding hier heißt Anzahl - also, die Anzahl der Permutationen in S(n) mit genau m Zykeln. Okay, kommen wir noch mal kurz zum Wort Permutation und zu Zykelschreibweise. Sei ? Element von S(n), also wenn es zum Beispiel S(5) wäre, dann wären das alle natürlichen Zahlen, 1 bis 5 - und das wollen wir jetzt in der Zykelschreibweise darstellen. ? ist eine Permutation in S(5), alle Zahlen von 1 bis 5, nur ein wenig verschoben, permutiert. Gut, und jetzt wollen wir das in der Zykelschreibweise haben. Dann gucken wir nach, welche Zahl steht über welcher. Wir fangen zuerst an mit der 1. 1 ist über 5. Hier haben wir die 2. Und unter der 2 steht wieder die 1. Das ist also unser 1. Zykel. Die 1 haben wir hier, die 2 auch. Dann kommen wir jetzt zur 3. Aha, da haben wir die 4. Und bei der 4 haben wir wieder die 3, also haben wir den 2. Zykel. Okay, dann zeige ich euch jetzt noch ein Permutation, und zwar ?. ? wollen wir jetzt auch wieder in Zykelschreibweise darstellen. Wir fangen an mit der 1, und da hört der 1. Zykel schon auf. Dann nehmen wir jetzt die 2. Aha, da haben wir die 3. Unter der 3 steht die 4 und unter der 4 steht die 5. Und schon haben wir ?. Und genauso wie ? ist ? eine Permutation in S(5) mit genau 2 Zykeln. Gut, ? und ? waren jetzt nur ein paar Beispiele. Wenn wir jetzt die Sterlingzahl in S(5) mit 2 Zykeln haben wollen, müssen wir gucken, wie viele Permutationen kann es geben, die so sind. Also wir können zum Beispiel so eine Permutation haben: (.)(....), so ähnlich wie ?, ein (..) (...) so wie ?, ein (...)(..), auch wie ? und ein (....)(.) so wie ?. Aber die beiden hier unten brauchen wir nicht, weil es im Prinzip dasselbe ist wie die da drüber, denn das könnten wir durch shiften ja wieder selber erreichen. Wir müssen also uns nur auf diese beiden Zykeln konzentrieren. Okay, wir müssen jetzt also rauskriegen, wenn wir die Stirlingzahl in S(5) mit 2 Zykeln haben wollen, wie viele Permutationen dieses Typs gibt es. Also, wir haben die Zahlen 1 bis 5. Das heißt, wie viele Möglichkeiten haben wir hier, den 1. Zykel zu füllen? Ist ja ganz leicht - 5. Na, wenn man es genauer nimmt, sind es 5 über 1 Möglichkeiten. Ich weiß, sind ja auch 5, aber wird noch wichtig. Okay, und wie viele Möglichkeiten haben wir hier? Wir haben hier noch 4 Zahlen über und wir haben 4 Plätze frei. Wir wollen also 4 Zahlen auf 4 Plätze verteilen. Das wären ja 4! Möglichkeiten eigentlich, aber wir müssen das Shiften noch betrachten, wir könnten nämlich selbe Permutation haben. Zum Beispiel, wenn wir sagen, hier haben wir die 5 drin, dann haben wir noch alle Zahlen von 1 bis 4. Und (1234)=(2341). Rübergeschoben, und die 1 hinten dran, ist derselbe Zykel. Wenn man hier die Pfeile nimmt, bleibt es so. Das ist das gleiche wie (3412), ist auch das gleiche wie (4123). Wenn wir das jetzt noch einmal verschieben würden, dann wären wir wieder hier am Anfang. Das heißt es gibt also 4 Möglichkeiten, wie wir das doppelt zählen könnten, also müssten wir das noch durch 4 teilen. Und insgesamt haben wir hierfür (4-1)! viele Möglichkeiten. (4-1)!=3! 3!=6 5 über 1=5 und 5×6=30. Okay, ich nehme an, das war jetzt ein bisschen schnell, deswegen noch einmal allgemein. Wenn wir die Anzahl der Endzykeln in S(n) haben wollen, dann müssen wir rechnen n!/n, wie wir hier gerade 4!/4 hatten, oder (n-1)!. Das Ganze stellt ihr euch so vor: Wenn wir hier alle Zahlen von 1 bis n haben, dann könnten wir das auf n! Möglichkeiten ja verteilen. Also nLeute auf nPlätze verteilen, dafür gibt es n! viele Möglichkeiten. Bei Permutationen spielt das Shiften aber eine Rolle, und wir wollen dafür sorgen, dass wir nicht dasselbe haben, wenn wir das einmal durchshiften. Deswegen sagen wir, wir schieben hier die 1 drauf und die fixieren wir da. Und jetzt können wir hier sämtliche Zahlen irgendwie durchschieben, wie wir wollen, und erhalten immer eine andere Permutation, weil wir die 1 nicht mit durchshiften. Das heißt, wir haben 1 Möglichkeit sozusagen rausgenommen. Wie ein Platz, wo wir eine spezielle Person hinsetzen, und wenn wir die anderen irgendwie verschieben, bleibt das nicht dasselbe. Machen wir mit unserer ursprünglichen Aufgabe weiter. Wir wollen jetzt wissen, wie viele Permutationen des Typs 1 (..) und 1 (...) gibt es? Okay, wir können die 5 Zahlen auf 2 Plätze verteilen, haben also 5 über 2 Möglichkeiten dafür ×, wie können wir es hier am besten verteilen, das wären ja 3!, aber das Durchshiften nicht vergessen, also ×(3-1)!. Übrigens, streng genommen, würde hier noch stehen ×1!, einfach (2-1)! und hier noch ×3 über 3. Ist aber beides 1 und ×1 muss man ja nicht schreiben. Wir haben also hier 5 über 2 Möglichkeiten ×1! und hier 3 über 3 Möglichkeiten ×2!. So, 5 über 2 macht 10×1, können wir weglassen, ×1, können wir weglassen, ×2!, also ×2=20. Gut, und 20+30=50.

 

Informationen zum Video