Definition - Binomialkoeffizient

• Beispiele:
  • Anzahl aller k-Kombinationen ohne Wiederholung
  • Anzahl aller k-Kombinationen mit Wiederholung
• Konstrukte:
  • Binomischer Lehrsatz
• Generalisierungen:
  • Multinomialkoeffizient
• Eigenschaften:
  • Proposition - ArgMax-k des Binomialkoeffizienten
  • Abschätzung des Binomialkoeffizienten
  • Abschätzung des maximalen Binomialkoeffizienten
• Identitäten
  • Proposition - Binomialkoeffizient mit Bruch
  • Proposition - Identität Binomialkoeffizient (n-1 k-1) mit Bruch
  • Proposition - Identität Binomialkoeffizient Symmetrie (n k) = (n n-k)
  • Proposition - Binomialkoeffizient binäre Identität
  • Proposition - Binomialkoeffizient negative Pascalsche Regel
  • Proposition - Binomialkoeffizient positive Pascalsche Regel
  • Proposition - Identität zwei Binomialkoeffizienten
  • Proposition - Identität Binomialkoeffizient Summe über den oberen Index
  • Proposition - Binomialkoeffizient Summe über den unteren Index
  • Proposition - Chu-Vandermonde Identität
• Involvierte Definitionen:
  • Proposition - Anzahl aller injektiven Funktionsvorschriften
  • Definition - Permutation
  • Fallende Faktorielle
• Referenzen:
  • } AlgoMathe KE1 - Binomialkoeffizient

⠀

Definition: Binomialkoeffizient

Seien mit Der Binomialkoeffizient ist definiert durch

(Gesprochen ” über ”)

• falls dann

Anmerkung

Tipp: Basis-Identitäten

Für den Binomialkoeffizienten gilt:

Interpretation

Der Binomialkoeffizient gibt an, auf wie viele Arten man aus einer Menge mit Elementen jeweils Elemente auswählen kann und zwar

• ohne Zurücklegen
• ohne Beachtung der Reihenfolge

Er ist also die Anzahl der -elementigen Teilmengen einer -elementigen Grundmenge.

Das bedeutet aber auch: Er unterscheidet zwischen zwei Sorten:

• den “ausgewählten Elementen”, von denen es genau Stück gibt
• den “anderen Elementen”, von denen es genau Stück gibt.

Herleitung

Wie viele Möglichkeiten es gibt, Elemente aus der Potenzmenge zu wählen, wissen wir bereits von Proposition - Anzahl aller injektiven Funktionsvorschriften

Es sind .

Diese Anzahl beachtet jedoch die Reihenfolge der Mengen. Diese “Überschätzung” müssen wir also abziehen.

Was ist also diese “Überschätzung”? Es gibt beispielsweise 2 Möglichkeiten dafür 2 Zahlen zu ziehen:

1. die erste Zahl, dann die zweite
2. die zweite Zahl, dann die ersten

In anderen Worten, wir müssen herausfinden, wie viele Permutationen eine -elementige Menge hat.

Glücklicherweise wissen wir das bereits: genau

Die even-Teilmengen-Beziehung

Wir wissen, jede Teilmenge hat gerade/ungerade Teilmengen. Diese Identität behandelt die geraden Teilmengen.

Die odd-Teilmengen-Beziehung

Wir wissen, jede Teilmenge hat gerade/ungerade Teilmengen. Diese Identität behandelt die ungeraden Teilmengen.