Stirling Zahlen zweiter Art: < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:15 Sa 14.05.2005 | | Autor: | squeezer |
Hallo
Wie kann man überhaupt vorgehen wenn man folgende Formel für die Stirling Zahlen zweiter Art beweisen soll:
[mm] S_{kn}= \bruch{1}{n} \summe_{j=n-1}^{k-1} \vektor{k \\ j}S_{j,n-1}
[/mm]
k,n [mm] \in \IN; [/mm] k [mm] \ge [/mm] n > 0
Wie beweist man solche Formeln im Prinzip. Ich hab keine Ahnung von was ich ausgehen soll.
Vielen Dank für Ihre Hilfe
Marc
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:07 Di 17.05.2005 | | Autor: | Julius |
Hallo squeezer!
> Wie kann man überhaupt vorgehen wenn man folgende Formel
> für die Stirling Zahlen zweiter Art beweisen soll:
> [mm]S_{kn}= \bruch{1}{n} \summe_{j=n-1}^{k-1} \vektor{k \\ j}S_{j,n-1}[/mm]
>
> k,n [mm]\in \IN;[/mm] k [mm]\ge[/mm] n > 0
Ich will dir die Formel mal plausibel machen. Es geht ja darum, wie viele Partitionen einer $k$-elementigen Menge in $n$ disjunkte Teilmengen möglich sind.
Man kann dies (rechte Seite) so machen: Wir wählen uns erst einmal eine Menge fest, die zwischen $1$ und $n-1$ (dann sind alle anderen $n-1$ Mengen einelementig) und Elemente enthalten muss. Dazu wählen wir aber nicht die Menge selbst, sondern das Komplement der Menge. Für das Komplement dieser Menge bedeutet die obige Erkenntnis, dass dieses zwischen $n-1$ und $k-1$ Elemente enthält. Darüber läuft die Summe. Es gibt für jedes [mm] $j=n-1,\ldots,n-1$ [/mm] genau ${k [mm] \choose [/mm] j}$ Möglichkeiten aus den $k$ Elementen solch ein Komplement der Größe $j$ zu wählen. Dieses Komplement müssen wir in $n-1$ disjunkte Teilmengen aufteilen, wofür es [mm] $S_{j,n-1}$ [/mm] Möglichkeiten gibt.
Die Frage ist jetzt nur noch, warum anschließend noch durch $n$ geteilt wird. Aber auch das ist einfach einzusehen. Jede Menge kann in einer bestimmten (festen)Partition entweder die am Anfang gewählte Menge sein (deren Komplement wird gewählt und in $n-1$ disjunkte Teilmengen zerlegt haben) oder aber ein Bestandteil des Komplements und darin wieder eines von $n-1$ möglichen Bestandteilen, so dass wir vorher jede Partition $n$-fach gezählt hatten.
Beispiel:
Zerlege die Menge [mm] $\{1,2,3,4,5\}$ [/mm] in drei disjunkte Teilmengen:
Obiges Vorgehen:
Wähle zunächst das Komplement der Größe $3$, das in zwei disjunkte Teilmengen zerlegt wird.
1) Komplement [mm] $\{1,2,3\}$
[/mm]
[mm] $\{1,2\}$, $\{3\}$, $\{4,5\}$
[/mm]
[mm] $\{1,3\}$, $\{2\}$, $\{4,5\}$
[/mm]
[mm] $\{2,3\}$, $\{1\}$, $\{4,5\}$
[/mm]
2) Komplement [mm] $\{1,2,4\}$
[/mm]
[mm] $\{1,2\}$, $\{4\}$, $\{3,5\}$
[/mm]
[mm] $\{1,4\}$, $\{2\}$, $\{3,5\}$
[/mm]
[mm] $\{2,4\}$, $\{1\}$, $\{3,5\}$
[/mm]
3) Komplement [mm] $\{1,2,5\}$
[/mm]
[mm] $\{1,2\}$, $\{5\}$, $\{3,4\}$
[/mm]
[mm] $\{1,5\}$, $\{2\}$, $\{3,4\}$
[/mm]
[mm] $\{2,5\}$, $\{1\}$, $\{3,4\}$
[/mm]
4) Komplement [mm] $\{2,3,4\}$
[/mm]
[mm] $\{2,3\}$, $\{4\}$, $\{1,5\}$
[/mm]
[mm] $\{2,4\}$, $\{3\}$, $\{1,5\}$
[/mm]
[mm] $\{3,4\}$, $\{2\}$, $\{1,5\}$
[/mm]
5) Komplement [mm] $\{2,3,5\}$
[/mm]
[mm] $\{2,3\}$, $\{5\}$, $\{1,4\}$
[/mm]
[mm] $\{2,5\}$, $\{3\}$, $\{1,4\}$
[/mm]
[mm] $\{3,5\}$, $\{2\}$, $\{1,4\}$
[/mm]
6) Komplement [mm] $\{2,4,5\}$
[/mm]
[mm] $\{2,4\}$, $\{5\}$, $\{1,3\}$
[/mm]
[mm] $\{2,5\}$, $\{4\}$, $\{1,3\}$
[/mm]
[mm] $\{4,5\}$, $\{2\}$, $\{1,3\}$
[/mm]
7) Komplement [mm] $\{1,3,4\}$
[/mm]
[mm] $\{1,3\}$, $\{4\}$, $\{2,5\}$
[/mm]
[mm] $\{1,4\}$, $\{3\}$, $\{2,5\}$
[/mm]
[mm] $\{3,4\}$, $\{1\}$, $\{2,5\}$
[/mm]
8) Komplement [mm] $\{1,3,5\}$
[/mm]
[mm] $\{1,3\}$, $\{5\}$, $\{2,4\}$
[/mm]
[mm] $\{1,5\}$, $\{3\}$, $\{2,4\}$
[/mm]
[mm] $\{3,5\}$, $\{1\}$, $\{2,4\}$
[/mm]
9) Komplement [mm] $\{1,4,5\}$
[/mm]
[mm] $\{1,4\}$, $\{5\}$, $\{2,3\}$
[/mm]
[mm] $\{1,5\}$, $\{4\}$, $\{2,3\}$
[/mm]
[mm] $\{4,5\}$, $\{1\}$, $\{2,3\}$
[/mm]
10) Komplement [mm] $\{3,4,5\}$
[/mm]
[mm] $\{3,4\}$, $\{5\}$, $\{1,2\}$
[/mm]
[mm] $\{3,5\}$, $\{4\}$, $\{1,2\}$
[/mm]
[mm] $\{4,5\}$, $\{3\}$, $\{1,2\}$
[/mm]
Jetzt wählen wir die Komplemente der Größe $1$:
1) Komplement [mm] $\{1\}$
[/mm]
[mm] $\{2,3\}$, $\{4,5\}$, $\{1\}$
[/mm]
[mm] $\{2,4\}$, $\{3,5\}$, $\{1\}$
[/mm]
[mm] $\{2,5\}$, $\{3,4\}$, $\{1\}$
[/mm]
[mm] $\{2,3,4\}$, $\{5\}$, $\{1\}$
[/mm]
[mm] $\{2,3,5\}$ ,$\{4\}$, $\{1\}$
[/mm]
[mm] $\{2,4,5\}$, $\{3\}$, $\{1\}$
[/mm]
[mm] $\{3,4,5\}$, $\{2\}$, $\{1\}$
[/mm]
1) Komplement [mm] $\{1\}$
[/mm]
[mm] $\{2,3\}$, $\{4,5\}$, $\{1\}$
[/mm]
[mm] $\{2,4\}$, $\{3,5\}$, $\{1\}$
[/mm]
[mm] $\{2,5\}$, $\{3,4\}$, $\{1\}$
[/mm]
[mm] $\{2,3,4\}$, $\{5\}$, $\{1\}$
[/mm]
[mm] $\{2,3,5\}$ ,$\{4\}$, $\{1\}$
[/mm]
[mm] $\{2,4,5\}$, $\{3\}$, $\{1\}$
[/mm]
[mm] $\{3,4,5\}$, $\{2\}$, $\{1\}$
[/mm]
2) Komplement [mm] $\{2\}$
[/mm]
[mm] $\{1,3\}$, $\{4,5\}$, $\{2\}$
[/mm]
[mm] $\{1,4\}$, $\{3,5\}$, $\{2\}$
[/mm]
[mm] $\{1,5\}$, $\{3,4\}$, $\{2\}$
[/mm]
[mm] $\{1,3,4\}$, $\{5\}$, $\{2\}$
[/mm]
[mm] $\{1,3,5\}$ ,$\{4\}$, $\{2\}$
[/mm]
[mm] $\{1,4,5\}$, $\{3\}$, $\{2\}$
[/mm]
[mm] $\{3,4,5\}$, $\{1\}$, $\{2\}$
[/mm]
3) Komplement [mm] $\{3\}$
[/mm]
[mm] $\{1,2\}$, $\{4,5\}$, $\{3\}$
[/mm]
[mm] $\{1,4\}$, $\{2,5\}$, $\{3\}$
[/mm]
[mm] $\{1,5\}$, $\{2,4\}$, $\{3\}$
[/mm]
[mm] $\{1,2,4\}$, $\{5\}$, $\{3\}$
[/mm]
[mm] $\{1,2,5\}$ ,$\{4\}$, $\{3\}$
[/mm]
[mm] $\{1,4,5\}$, $\{2\}$, $\{3\}$
[/mm]
[mm] $\{2,4,5\}$, $\{1\}$, $\{3\}$
[/mm]
4) Komplement [mm] $\{4\}$
[/mm]
[mm] $\{1,3\}$, $\{2,5\}$, $\{4\}$
[/mm]
[mm] $\{1,2\}$, $\{3,5\}$, $\{4\}$
[/mm]
[mm] $\{1,5\}$, $\{3,2\}$, $\{4\}$
[/mm]
[mm] $\{1,3,2\}$, $\{5\}$, $\{4\}$
[/mm]
[mm] $\{1,3,5\}$ ,$\{2\}$, $\{4\}$
[/mm]
[mm] $\{1,2,5\}$, $\{3\}$, $\{4\}$
[/mm]
[mm] $\{3,2,5\}$, $\{1\}$, $\{4\}$
[/mm]
5) Komplement [mm] $\{5\}$
[/mm]
[mm] $\{1,3\}$, $\{4,2\}$, $\{5\}$
[/mm]
[mm] $\{1,4\}$, $\{3,2\}$, $\{5\}$
[/mm]
[mm] $\{1,2\}$, $\{3,4\}$, $\{5\}$
[/mm]
[mm] $\{1,3,4\}$, $\{2\}$, $\{5\}$
[/mm]
[mm] $\{1,3,2\}$ ,$\{4\}$, $\{5\}$
[/mm]
[mm] $\{1,4,2\}$, $\{3\}$, $\{5\}$
[/mm]
[mm] $\{3,4,2\}$, $\{1\}$, $\{5\}$
[/mm]
Hier siehst du ganz deutlich: Es gibt ${5 [mm] \choose [/mm] 2}=10$ bzw. ${5 [mm] \choose [/mm] 1}=5$ Möglichkeiten das Komplement zu wählen (und jeweils [mm] $S_{3,2}=3$ [/mm] bzw. [mm] $S_{4,2}=7$ [/mm] Möglichkeiten dies in zwei disjunkte Teilmengen aufzuspalten), aber jede Partition wird insgesamt genau dreifach gezählt.
Der formale Beweis ist jetzt nur noch abstrakter Nonsens.
Liebe Grüße
Julius
|
|
|
|
