Kombinatorik, Binomialkoeff. < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:23 Sa 09.03.2013 | | Autor: | Labrinth |
| Aufgabe | | Für [mm] $k,n\in\mathbb{N}$ [/mm] zeige man, dass die Menge [mm] $\left\{(a_1,\dots,a_n)\in\mathbb{N}^n\;\middle|\;\sum_{i=1}^{n}a_i=k\right\}$ [/mm] genau [mm] $\binom{k+n-1}{n-1}$ [/mm] Elemente besitzt. |
Guten Tag!
Der Induktionsanfang ist klar (sowohl für Induktion über $k$, als auch über $n$). Ich denke, den rechnerischen Teil des Induktionsschrittes würde ich auch hinbekommen, ich scheitere am Argumentativen, sowohl bei $n$, als auch bei $k$ wüsste ich nicht, wie sich die Anzahl der Elemente beim Induktionsschritt verändert.
Beste Grüße,
Labrinth
|
|
| |
|
> Für [mm]k,n\in\mathbb{N}[/mm] zeige man, dass die Menge
> [mm]\left\{(a_1,\dots,a_n)\in\mathbb{N}^n\;\middle|\;\sum_{i=1}^{n}a_i=k\right\}[/mm]
> genau [mm]\binom{k+n-1}{n-1}[/mm] Elemente besitzt.
> Guten Tag!
>
> Der Induktionsanfang ist klar (sowohl für Induktion über
> [mm]k[/mm], als auch über [mm]n[/mm]). Ich denke, den rechnerischen Teil des
> Induktionsschrittes würde ich auch hinbekommen, ich
> scheitere am Argumentativen, sowohl bei [mm]n[/mm], als auch bei [mm]k[/mm]
> wüsste ich nicht, wie sich die Anzahl der Elemente beim
> Induktionsschritt verändert.
>
> Beste Grüße,
> Labrinth
Hallo Labrinth,
zu dieser Aufgabe habe ich in einem früheren Thread,
den ich nur leider nicht gerade wieder finden kann,
einen anschaulichen Beweis gezeigt, den ich hier nur
an einem Beispiel kurz erläutern möchte.
Betrachte wir etwa den Fall mit k=9 und n=5.
Es soll also die Zahl 9 auf alle möglichen Arten in
eine Summe von 5 (in einer geordneten Folge
angeordneten !) Summanden zerlegt werden.
Dabei sollen die einzelnen Summanden natürliche
Zahlen sein. Dabei ist in den "natürlichen Zahlen"
auch die Null inbegriffen - denn andernfalls stimmt
die angegebene Formel nicht !
Jede Lösung ist also eine Summendarstellung
9 = [mm] a_1 [/mm] + [mm] a_2 [/mm] + [mm] a_3 [/mm] + [mm] a_4 [/mm] + [mm] a_5 [/mm] = [mm] \summe_{i=1}^{5}a_i
[/mm]
Ein Beispiel:
9 = 2 + 0 + 1 + 4 + 2
Anschaulich kann man sich vorstellen, dass man
9 Punkte in eine Reihe setzt:
[mm] $\bullet\ \bullet\ \bullet\ \bullet\ \bullet\ \bullet\ \bullet\ \bullet\ \bullet$
[/mm]
und dann diese Reihe durch genau 4 Trennstriche
in 5 Teilabschnitte zerlegt, so, dass in den i-ten
Abschnitt genau [mm] a_i [/mm] Punkte zu liegen kommen.
Wir brauchen einen Trennstrich weniger als wir
Summanden haben wollen: 5-1=4 (allgemein n-1
Trennstriche für n Summanden).
In unserem Beispiel sähe dies so aus:
[mm] $\bullet\ \bullet\ \mid\ \mid\ \bullet\ \mid\ \bullet\ \bullet\ \bullet\ \bullet\ \mid\ \bullet\ \bullet$
[/mm]
In dieses Modell übersetzt lautet nun die Frage
anstatt "auf wieviele Arten kann man die Zahl k=9
in eine Summe von n=5 der Reihe nach angeordneten
Summanden [mm] a_i\in\IN_0 [/mm] zerlegen ?" so:
"auf wie viele Arten kann man 9+5-1=13 Symbole,
wovon genau 9 Punkte [mm] (\bullet) [/mm] und 4=5-1 Trenn-
striche [mm] (\mid) [/mm] in einer Reihe anordnen ?"
Damit ist die Aufgabe auf eine gängige Grundaufgabe
der Kombinatorik zurückgeführt.
LG , Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:51 Sa 09.03.2013 | | Autor: | Labrinth |
Danke, geschickte Idee!
Beste Grüße,
Labrinth
|
|
|
|
