komb. Beweis fallende Fakt. < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Beweisen Sie durch kombinatorische Argumente folgende Aussagen für fallende Faktorielle:
(a) Für alle n [mm] \in \IN+ [/mm] und k [mm] \in \IN+ [/mm] gilt [mm] n^{[u]k[/u]} [/mm] = k * (n - [mm] 1)^{[u]k-1[/u]} [/mm] + (n - [mm] 1)^{[u]k[/u]}
[/mm]
(b) Für alle n, m, k [mm] \in \IN [/mm] gilt (n + [mm] m)^{[u]k[/u]} [/mm] = [mm] \summe_{i=0}^{k} \vektor{k \\ i} [/mm] * [mm] n^{[u]k-i[/u]} [/mm] * [mm] m^{[u]i[/u]}
[/mm]
Bemerkung: Wir setzen [mm] n^{[u]k[/u]} [/mm] = 0, falls k < 0 oder k > n gilt. |
Hallo.
Ich bin auf dem Gebiet der kombinatorischen Beweise noch neu (1.Semester Informatik) und weiß deshalb gar nicht so recht wie ich da vorgehen soll.
In der Vorlesung haben wir das Pascal'sche Dreieck mit Hilfe von Mengenfamilien bewiesen.
Ist das bei diesen (oder zumindest bei (a)) auch der Ansatz?
Z.B. F = [mm] \{(x_1,...,x_k) | x:i \in \{1,...,n\}, x_i \not= x_j für i \not= j\} [/mm] für [mm] n^{[u]k[/u]}
[/mm]
Um dann zu zeigen [mm] F_1 [/mm] + [mm] F_2 [/mm] = F?
Ich hoffe ihr könnt mir helfen. Und bedanke mich im Vorraus.
Ludolf
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:58 So 29.05.2011 | | Autor: | IchDa |
Hey Kommilitone,
also wir haben in der Vorlesung für das Pascal'sche Dreieck folgendes ermittelt:
[mm] \vektor{n \\ k} [/mm] = [mm] \vektor{n-1 \\ k-1} [/mm] + [mm] \vektor{n-1 \\ k}
[/mm]
Und [mm] \vektor{n \\ k} [/mm] haben wir ja wie folgt eingeführt:
[mm] \vektor{n \\ k} [/mm] = [mm] \bruch{1}{k!} [/mm] * [mm] n^{\underline{k}}
[/mm]
Mit ein bisschen umschieben, sollte man dann zum Ergebnis kommen.
Gruß
|
|
|
|
