Stirling-Zahlen 2.Art < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:24 Mo 27.06.2005 | | Autor: | dh_zm |
Hallo,
komme wiedermal nicht weiter...
hier erstmal die aufgabe:
Beweisen Sie:
Stirling-Zahlen zweiter Art, Potenzen und fallende Faktorielle erfüllen die folgende Gleichung:
$ [mm] n^m [/mm] = [mm] \summe_{k=0}^{n} n^{\underline{k}} [/mm] * [mm] S_{m,k} [/mm] $
Wenn ich jetzt erstmal alles durch die jew. Definition ersetze:
$ [mm] n^{\underline{k}} [/mm] = [mm] \bruch{n!}{(n-k)!} [/mm] = [mm] \vektor{n \\ k} [/mm] * k! $
und
$ [mm] S_{m,k} [/mm] = [mm] \bruch{1}{k!} [/mm] * [mm] \summe_{l=0}^{k} (-1)^l [/mm] * [mm] \vektor{k \\ l} [/mm] * [mm] (k-l)^m [/mm] $
erhalte ich:
$ [mm] \summe_{k=0}^{n} \vektor{n \\ k} [/mm] * ( [mm] \summe_{l=0}^{k} (-1)^l [/mm] * [mm] \vektor{k \\ l} [/mm] * [mm] (k-l)^m [/mm] ) $
aber wie um alles in der welt komme ich da auf
$ [mm] n^m [/mm] $ ?
hoffe mir kann da jemand weiterhelfen...
daniel
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:51 Di 28.06.2005 | | Autor: | Hanno |
Hallo!
Versuche dir das Ganze doch einmal anschaulich klar zu machen:
Die Stirling-Zahl zweiter Art $S(n,k)$ gibt an, wie viele k-Partitionen einer n-Menge es gibt. Diese Anzahl kann man leicht mit der Anzahl der surjektiven Abbildungen von [mm] $[n]:=\{1,2,...,n\}$ [/mm] auf [mm] $[k]:=\{1,2,...,k\}$ [/mm] in Verbindung bringen. Suchen wir nämlich eine surjektive Abbildung, so müssen wir die $n$ Elemente der Bildmenge $[n]$ in $k$ Mengen partitionieren, die angeben, welche Elemente aus $[n]$ auf das gleiche Element in $[k]$ abgebildet werden. Dafür gibt es genau $S(n,k)$ Möglichkeiten. Nun wissen wir aber noch nicht, welche Gruppe von Elementen aus $[n]$ auf welches [mm] $k\in [/mm] [k]$ abgebildet wird - für diese Zuweisung gibt es nochmals $k!$ Möglichkeiten. D.h. also: Die Anzahl der surjektiven Abbildungen von $[n]$ auf $[k]$ beträgt [mm] $S(n,k)\cdot [/mm] k!$. Das ist doch mal was! Ich schreibe im Folgenden [mm] $s_{n,k}$ [/mm] für die Anzahl der surjektiven Abbildungen von $[n]$ auf $[k]$.
Erweitern wir in der dir gegebenen Formel die Summanden mit $k!$, so erhalten wir wegen [mm] $\frac{n^{\underline{k}}}{k!}=\vektor{n\\ k}$ [/mm] und - wie eben hergeleitet - [mm] $S(n,k)=s_{n,k}\cdot [/mm] k!$ die Summe
[mm] $\summe_{k=1}^{n} \vektor{n\\ k} s_{m,k}$
[/mm]
Betrachten wir nun die linke Seite, d.h. [mm]n^m[/mm]. Was gibt diese an? Klar: die Anzahl aller Abbildungen von [mm] $\[m\]$ [/mm] nach [mm] $\[n\]$. [/mm] Wir müssen also lediglich zeigen, dass die rechte Seite auch die Anzahl dieser Abbildungen zählt. Das können wir wie folgt einsehen: die Mächtigkeit des Bildes einer jeden Abbildung [mm] $f:\[m\]\to\[n\]$ [/mm] ist eindeutig bestimmt - nennen wir sie im Folgenden $k$, d.h. [mm] $|f(\[m\])|=k$. [/mm] Wie viele solcher Abbildungen gibt es? Nun, wir wissen, dass $f$ die Elemente von [mm] $\[m\]$ [/mm] auf genau $k$ verschiedene Elemente aus [mm] $\[n\]$ [/mm] abbildet - wählen wir diese doch erst einmal aus: dafür gibt es [mm] $\vektor{n\\ k}$ [/mm] Möglichkeiten. Nun müssen wir also noch die $m$ Elemente aus [mm] $\[m\]$ [/mm] surjektiv auf die $k$ Ausgewählten Elemente aus [mm] $\[n\]$ [/mm] abbilden. Wie viele Möglichkeiten gibt es dafür? Klar: genau [mm] $s_{m,k}$. [/mm] D.h. also, dass es genau [mm] $\vektor{n\\ k} s_{m,k}$ [/mm] Abbildungen $f:[m][mm] \to [/mm] [n]$ mit [mm] $\vert [/mm] f([m][mm] )\vert [/mm] =k$ gibt. Wie oben bereits erwähnt, hat jede Abbildung von [mm] $\[m\]$ [/mm] nach [mm] $\[n\]$ [/mm] eine eindeutig bestimmte Mächtigkeit ihrer Bildmenge, sodass wir durch Summation von k=1,2,...,n über [mm] $\vektor{n\\ k} s_{m,k}$ [/mm] die Gesamtzahl aller Abbildungen von [mm] $\[m\]$ [/mm] nach [mm] $\[n\]$, [/mm] also [mm] $n^m$, [/mm] erhalten. Ausgeschrieben bedeutet dies
[mm] $n^m [/mm] = [mm] \summe_{k=1}^{n} \vektor{n\\ k} s_{m,k}$,
[/mm]
was zu zeigen war!
Liebe Grüße,
Hanno
|
|
|
|
