Stirlingzahlen 2.Art,Rekursion < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:39 Do 05.08.2010 | | Autor: | kawu |
Hallo Community!
Ich versuche schon seit gestern, diese Formel zu verstehen:
[mm] $\begin{Bmatrix}n+1\\
k\end{Bmatrix}= \sum_{m=0}^n {n\choose m}\begin{Bmatrix}m\\
k-1\end{Bmatrix}$
[/mm]
Die Stirling-Zahl soll als Anzahl der möglichen Permutationen einer Menge mit n+1 Elementen aufgefasst werden. Kann mir jemand erklären, wieso die Anzahl der Partitionen der (n+1)-elementigen Menge gleich der Summe ist?
lg, KaWu
|
|
| |
|
> Ich versuche schon seit gestern, diese Formel zu
> verstehen:
>
> [mm]$\begin{Bmatrix}n+1\\
k\end{Bmatrix}= \sum_{m=0}^n {n\choose m}\begin{Bmatrix}m\\
k-1\end{Bmatrix}$[/mm]
>
> Die Stirling-Zahl soll als Anzahl der möglichen
> Permutationen einer Menge mit n+1 Elementen aufgefasst
> werden.
Das kann ja wohl nicht sein, denn die Anzahl dieser
Permutationen wäre ja einfach (n+1)!
> Kann mir jemand erklären, wieso die Anzahl der
> Partitionen der (n+1)-elementigen Menge gleich der Summe
> ist?
>
> lg, KaWu
Hallo KaWu,
bei wikipedia habe ich die Definition gefunden:
"Die Stirling-Zahl zweiter Art [mm] S_{n,k} [/mm] oder [mm] $\begin{Bmatrix} n \\ k \end{Bmatrix}$ [/mm] ist die
Anzahl der k-elementigen Partitionen einer n-elemen-
tigen Menge, also die Anzahl der Möglichkeiten, eine
n-elementige Menge in k nichtleere disjunkte Teilmen-
gen aufzuteilen."
Ich verwende lieber die Indexschreibweise anstelle der
geschweiften Klammern. Dann wäre deine zu beweisende
Formel:
$\ [mm] S_{n+1,k}\ [/mm] =\ [mm] \summe_{m=0}^{n}\pmat{n\\m}*S_{m,k-1}$
[/mm]
Ich habe versucht, mir diese Formel direkt plausibel zu
machen (via Definition), aber das habe ich leider nicht
geschafft.
Nun habe ich bei Wiki noch eine einfache Rekursions-
formel gefunden, nämlich:
[mm] S_{n,k} [/mm] = [mm] S_{n-1,k-1} [/mm] + [mm] k\,*\,S_{n-1,k}
[/mm]
Man kann sie auch so schreiben:
[mm] S_{n+1,k} [/mm] = [mm] S_{n,k-1} [/mm] + [mm] k\,*\,S_{n,k}
[/mm]
Jetzt ginge es zunächst darum, diese Formel zu verstehen
und erklären zu können. Dann kann man versuchen, ob
man mittels dieser Formel die zu beweisende Formel
herleiten kann (Z.B. mit vollständiger Induktion).
LG Al-Chwarizmi
|
|
|
|
