Proposition - Anzahl aller k-Kombinationen mit Wiederholung

• Bewiesen durch:
  • Anzahl aller k-Kombinationen ohne Wiederholung
• Involvierte Definitionen:
  • k-Kombination mit Wiederholung
  • k-Kombination ohne Wiederholung
  • Binomialkoeffizient
• Veranstaltung: EiS
• Referenz: @henze2019

⠀

Proposition: Anzahl aller k-Kombinationen mit Wiederholung

Seien .
Dann gilt:

Beweis

Zur Erinnerung:

Memo - Kombination ohne Wiederholung

Sei eine -elementige Totalordnung.

Memo - Kombination mit Wiederholung

Sei eine -elementige Totalordnung.

Wie wir -Kombinationen mit Wiederholung als -Kombinationen ohne Wiederholung ausdrücken können

Seien also mit .
Dann gilt auch:

Das bedeutet: Wir können die -Kombination mit Wiederholung

auch als -Kombination ohne Wiederholung

ausdrücken.

Das bedeutet: Wir können jede -Kombination mit Wiederholung als -Kombination ohne Wiederholung darstellen (wie in ), müssen dafür aber um neue Elemente erweitern.

Dafür müssen wir aber um neue Elemente erweitern

Weshalb müssen wir um neue Elemente erweitern? Nun, angenommen . Dann ist

Außerdem ist

die entsprechende -Kombination ohne Wiederholung.

Da , folgt aber

Die Frage ist jetzt: Wie viele neue Elemente brauchen wir dafür?

Wenn wir das wüssten, könnten wir nämlich einfach die Anzahl berechnen. Und die Antwort darauf kennen wir bereits aus der Proposition über die Anzahl aller k-Permutationen ohne Wiederholung.

Jetzt könnte man vermuten, dass wir für jedes Element neue Element , einführen müssten.

Das ist zum Glück aber gar nicht nötig. Angenommen, wir hätten die Kombination (mit Wiederholung):

Dann wäre

eine zugehörige Kombination (ohne Wiederholung). Wir mussten hier aber nur eine einzige neue Zahl einführen (nämlich die ).

Das heißt: Wir können uns stets mit bereits existierenden Elementen aus behelfen, es sei denn, wir sind schon bei angekommen. Diesen Fall beobachten wir in diesem Beispiel bei oder etwas weiter oben bei den beiden Gleichungen und .

Zusammengefasst: Wir müssen nur diejenigen Elemente hinzufügen, die über hinausgehen, und das sind genau die Elemente

aus Gleichung . Und das sind wiederum genau Stück. Wir müssen also um Elemente erweitern, um es als -Permutation ohne Wiederholung darzustellen.

Es folgt:

was zu zeigen war.