Anzahl Partitionen von [n] < Kombinatorik < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:50 Di 07.02.2012 | | Autor: | clemenum |
| Aufgabe | | Ermitteln Sie die Anzahl aller Partitionen von [mm] $[n]:=\{1,2,\ldots,n\}$ [/mm] mit $k$ Blöcken. Sie können diese Anzahl zur Abkürzung [mm] $S_{n,k}$ [/mm] nennen. |
Ich behandle erst mal [mm] $S_{n,2} [/mm] $
Wenn man die Partitionen von $[10]$ betrachtet, so stellt sich gleich (allgemein) folgende Frage:
Auf wie viele Arten lässt sich eine natürliche Zahl $n$ als Summe zweier (anderer) natürlicher Zahlen darstellen?
Als (Motivations-)Beispiel für dieses Problem habe ich einfach mal die Zahl 10 systematisch in Summe von zwei natürlichen Zahlen geschrieben:
$10 = 1+9 = 2+8 = 3 + 7 = 4 + 6 = 5 + 5 = ... $
Dort wo die Pünktchen sind, brauche ich nicht mehr weiter zu machen, weil sich (im Sinne der Symmetrie der Binomialkoeffizenten) alles erneut wiederholt.
Die wichtige Erkenntnis (von mir) ist, dass eine natürliche Zahl $n$ sich auf genau $ [mm] [\frac{n}{2} [/mm] ] $ Arten (abgesehen von der Reihenfolge) als Summe zweier Zahlen darstellen lässt.
Damit habe ich also insgesamt:
[mm] $S_{n,2} [/mm] = [mm] {n\choose 1} [/mm] + [mm] {n\choose 2} [/mm] + [mm] \ldots [/mm] + [mm] {n\choose [\frac{n}{2} ]} [/mm] = [mm] 2^{n-1} [/mm] - 1 $
So, und jetzt wirds komplizierter:
Ich muss jetzt mich fragen, auf wie viele Arten $n$ als Summe dreier natürlicher Zahlen dargestellt werden kann^^ Das ist aber eine Irrsinnsarbeit, weil viel herumprobiert werden müsste.
Ich bin davon überzeugt, dass ichs hier auch ermitteln könnte, aber, es würde sehr lange dauern, wegen der geballten Unübersichtlichkeit. Das Problem: Wenn ich [mm] $S_{n,3}$ [/mm] nicht habe, sehe ich keine (allgemeine) Gesetzmäßigkeit und kann es somit nicht auf [mm] $S_{n,k} [/mm] $ verallgemeinern!
Kann mir da jemand einen Tipp zur Abkürzung geben?
|
|
| |
|
moin,
Die Bezeichnung [mm] $S_{n,k}$ [/mm] ist hier sicher nicht zufällig gewählt, denn gemeint sind damit die ![[]](/images/popup.gif) Stirlingzahlen.
Dort auf der Wikiseite stehen einige verschiedene Formeln dafür, die dir sicher helfen.
Ich würde dir raten dir die rekursive Formel recht am Anfang zu schnappen und dir logisch/kombinatorisch zu überlegen, wieso diese gilt.
Wenn du das hast kannst du ggf. auch noch weitere aus dem Wiki-Artikel ableiten oder selbst eine schöne finden.
lg
Schadow
|
|
|
|
