Diskrete Mathematik - Anzahl ganzzahliger Lösungen

Neue Frage »

goldenone12q Auf diesen Beitrag antworten »
Diskrete Mathematik - Anzahl ganzzahliger Lösungen
Meine Frage:
Hallo, ich studiere Informatik und komme noch nicht so ganz mit dem Beweisen zurecht und habe daher die Frage, ob mir kemand bei dieser Aufgabe helfen kann:

1. Beweisen Sie, dass die Anzahl der ganzzahligen Lösungen (x1,..,xn), xi>=1 für die Gleichung x1 + x2 + .. + xn = k (k >= n >= 1 ist auch eine ganze Zahl) gleich (k-1 über n-1) ist.

Meine Ideen:
Leider weiß ich nicht wie ich vorzugehen habe.
riwe Auf diesen Beitrag antworten »
RE: Diskrete Mathematik - Anzahl ganzzahliger Lösungen
vermutlich VI, was nicht "Verflixte Informatik" sondern "Vollständige Induktion" bedeutet smile
HAL 9000 Auf diesen Beitrag antworten »

Sofern die kombinatorische Anzahlformel für "Kombinationen mit Wiederholung" bekannt ist, würde ich den Beweis direkt über die führen, ohne dass Induktion noch nötig wäre:

Über die Substitution entspricht die gesuchte Anzahl der Tupelanzahl mit und . Und die wiederum entspricht der Anzahl der Auswahlen von Elementen aus der Grundmenge der Indizes ohne Berücksichtigung der Reihenfolge (also Kombinationen), aber mit Zurücklegen (d.h. mit Wiederholung) - dabei kennzeichnet wie oft Element in der Auswahl vertreten ist. Diese Auswahlanzahl ist nun gemäß bekannter Formel .
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »