Binomialkoeffizient

k Elemente aus n Elementen ungeordnet ohne Zurücklegen ziehen

Erklärung:

Der Binomialkoeffizient ist eine mathematische Funktion, mit der sich eine der Grundaufgaben der Kombinatorik lösen lässt. Er gibt an, auf wieviele verschiedene Arten man k Objekte aus einer Menge von n verschiedenen Objekten auswählen kann (ohne Zurücklegen, ohne Beachtung der Reihenfolge). Der Binomialkoeffizient 49 über 6 entspricht damit beispielsweise der Anzahl der möglichen Ziehungen beim Lotto.

n: k:

Es gibt

Definition:

Für eine reelle Zahl n und eine nichtnegative ganze Zahl k, wobei , ist der Binomialkoeffizient n über k auf folgende Weise definiert:

Eigenschaften:

Für nichtnegative ganze Zahlen n und k ist

stets eine nichtnegative ganze Zahl.

Der Binomialkoeffizient in der Kombinatorik

Binomialkoeffizienten spielen in der abzählenden Kombinatorik eine zentrale Rolle, denn

ist die Anzahl der Möglichkeiten, aus einer Menge mit n Elementen k Elemente auszuwählen, wobei die Reihenfolge der ausgewählten Elemente nicht berücksichtigt wird. Anschaulich lässt sich das so erklären: Man berechne mit n! alle möglichen Vertauschungen, suche sich k Felder aus (6 z.B. beim Lotto) und frage sich, wie viele Möglichkeiten es gibt, diese Felder zu besetzen. Da es keine Rolle spielt, welches Ereignis sich auf welchem Feld ereignet hat, dividiert man alle unter diesen k Elementen möglichen Vertauschungen mit k! heraus. Da es auch keine Rolle spielt, wie die Anordnung auf den uninteressanten Feldern aussieht, dividiert man mit (n - k)! auch diese Vertauschungen heraus. Formaler lässt sich dieser Sachverhalt auch so formulieren: Eine n-elementige Menge hat genau

k-elementige Teilmengen. Aufgrund dieser Parallele wird die Menge aller k-elementigen Teilmengen einer Menge M gelegentlich auch mit

bezeichnet. Mit dieser

Schreibweise gilt dann für jede endliche Menge M:

Beispiel:

Die Anzahl der möglichen Ziehungen beim deutschen Lotto 6 aus 49 (ohne Zusatzzahl oder Superzahl) lässt sich so berechnen:

Der Kehrwert

gibt dann die Wahrscheinlichkeit an, mit einem Tipp 6 Richtige zu erzielen. Die Wahrscheinlichkeit für 5 Richtige bei 6 aus 49 lässt sich jedoch nicht mehr durch einen einzelnen Binomialkoeffizienten berechnen. Stattdessen benötigt man die Hypergeometrische Verteilung, in deren Berechnung dann mehrere Binomialkoeffizienten ausgewertet werden müssen.

Fakultät

Definition

Wenn man n objekte auf n plätze verteilen möchte, so hat man für das erste objekt n möglichkeiten, für das zweite (n-1), für das dritte (n-2)....für das letzte nur noch eine möglichkeit, also ingsegamt n x (n-1) x (n-2)... x1 möglichkeiten

Wenn man k objekte auf n plätze verteilen möchte, so hat man für das erste objekt n möglichkeiten, für das zweite
(n-1), für das dritte (n-2)....für das k-te nur noch (n-k+1) möglichkeiten, also ingsegamt n x (n-1) x ...(n-k+1) = n! : (n-k)! möglichkeiten

Für alle natürlichen Zahlen n ist

also das Produkt der natürlichen Zahlen von 1 bis n.

Beispiele

Gib die Zahl ein, deren Fakultät berechnet werden soll:

Ergebnis