Proposition - Anzahl aller k-Kombinationen ohne Wiederholung

• Bewiesen durch:
  • Anzahl aller k-Permutationen ohne Wiederholung
• Generalisierungen:
  • Anzahl aller k-Permutationen ohne Wiederholung
• Involvierte Definitionen:
  • k-Kombination ohne Wiederholung
• Veranstaltung: EiS
• Referenz: @henze2019

⠀

Proposition: Anzahl aller k-Kombinationen ohne Wiederholung

Seien .
Dann gilt:

Beweis

Um das Ergebnis herzuleiten, untersuchen wir zunächst das Verhältnis von und .

Memo -

Memo -

In beiden Fällen (also sowohl bei als auch bei ) sind die allesamt eindeutig. Heißt, es gilt .

Im Fall der ist darüber hinaus festgelegt, dass sie auch noch aufsteigend sortiert sind (also ).

Daraus folgt

Da wir mittels der Proposition über die Anzahl aller k-Permutationen ohne Wiederholung bereits wissen, dass

Ist die Frage jetzt nur noch: wie viel kleiner ist ? Das ist anhand eines Beispiels relativ einfach zu beantworten.

Angenommen, . Dann gilt . Das -Tupel ist also die einzige Möglichkeit aus , die Elemente miteinander zu kombinieren.

Und wie sieht das für aus? Nun, wenn wir uns fragen, wie viele Permutationen der Menge gibt, dann können wir uns das an dieser Stelle mit der eben schon erwähnten Proposition über die Anzahl aller k-Permutationen ohne Wiederholung beantworten.

Die Menge hat genau

Permutationen.

Da also genau -mal so viele Elemente enthält wie gilt:

was zu zeigen war.