Kombinationen – Grundlagen der Kombinatorik

Es gibt in der Wahrscheinlichkeitsrechnung zwei Experimenttypen, die einem immer wieder begegnen. Das sind einerseits Laplace-Experimente (alle Ereignisse sind gleich wahrscheinlich) und auf der anderen Seite Bernoulli- Experimente (genau zwei Elemente in der Ergebnismenge).

In diesem Kapitel befassen wir uns nun, welche Bedeutung die Reihenfolge der Elemente für die Wahrscheinlichkeit eines Gesamtergebnisses hat. In den bisherigen Kapiteln Permutationen und Variationen haben wir uns mit der Anzahl an Möglichkeiten beschäftigt, wenn die Reihenfolge berücksichtigt wird.

Nun befassen wir uns mit der “Kombination”. Bei einer Kombination wird aus einer Menge von n Elementen eine Auswahl an k Elementen berücksichtigt, wobei die Reihenfolge der Elemente nicht berücksichtigt wird.

Grundlagen der Kombinatorik – Kombinationen

Kombinationen treten auf, wenn wir aus einer bestimmten Menge mit n Elementen eine Anzahl an k Elementen (k ≤ n) entnehmen und diese ohne Beachtung der Reihenfolge auslegen. Bei Kombinationen gibt es zwei Möglichkeiten, zum einen ist es möglich, dass kein Element mehrfach vorkommen darf, zum anderen sind auch Kombinationen möglich, bei denen ein Element mehrfach vorkommen darf. Dies muss bei der Verwendung der richtigen Formel zur Berechnung der Kombination berücksichtigt werden (meist ergibt sich dies aus der Aufgabenstellung).

Zur Wiederholung: In einem anderen Kapitel haben wir uns mit der Variation befasst, im Unterschied zur Kombination wird die Reihenfolge aller Elemente berücksichtigt (n-Elemente und k-Auswahlen jeweils bei der Kombination und der Variation)

Kombination ohne Wiederholung

Gemäß der Definition werden bei einer Kombination ohne Wiederholung  k Elemente aus n Elementen ohne Beachtung der Reihenfolge ausgewählt. Voraussetzung, dass keine Wiederholung auftritt ist, dass keine Elemente mehrfach ausgewählt werden können.

Bevor wir die Formel zur Berechnung der Kombination herleiten, nochmals die Formel zur Berechnung der Variation::

Bei der Variation gibt es beim ersten Ziehen n Möglichkeiten (aus n Elementen), da noch kein Element verwendet wurden. Nach dem ersten Ziehen, bleiben noch (n-1) Elemente übrig, die für das zweite Ziehen verwendet werden können. Also haben wir beim zweiten Zug der Anordnung noch (n – 1), beim dritten Ziehen sind es noch (n – 2) Möglichkeiten und beim k-ten Zug sind es noch (n – k + 1) Möglichkeiten. Damit erhalten wir  (Anordnungen mit Berücksichtigung der Reihenfolge und ohne Wiederholung der Elemente) folgende Möglichkeiten der Anordnung der Ereignisse:

Möglichkeiten = n · (n -1) · (n – 2) · (n – 3) · … · (n – k + 1) = n! : (n – k)!

Der Unterschied zwischen Variation und Kombination ist, dass keine Reihenfolge bei der Kombination möglich ist. Daher hat man bei der Kombination auch weniger Möglichkeiten, als bei der Variation. Dies muss in der obigen Formel berücksichtigt werden. Daher muss die Gesamtzahl der Möglichkeiten durch die Anzahl der möglichen Anordnungen der Elemente (die gezogen werden) dividiert werden. Die Anzahl ist k1· k2· k3 … = k!

Damit erhalten wir (Anordnungen ohne Berücksichtigung der Reihenfolge und ohne Wiederholung der Elemente) folgende Möglichkeiten der Anordnung der Elemente (Kombinationen ohne Wiederholung):

Möglichkeiten = [n · (n -1) · (n – 2) · (n – 3) · … · (n – k + 1)] : k! = n! : [(n – k)! · k!]

Kombination mit Wiederholung

Bei einer Kombination mit Wiederholung werden k aus n Objekten ohne Beachtung der Reihenfolge ausgewählt, wobei Objekte auch mehrfach ausgewählt werden können. Dies muss in der Formel berücksichtigt werden:

Damit erhalten wir (Anordnungen ohne Berücksichtigung der Reihenfolge und mit Wiederholung der Elemente) folgende Möglichkeiten der Anordnung der Elemente (Kombinationen mit Wiederholung):

Kombination mit Wiederholung

Zusammenfassung der Kombinatorik

Die Kombinatorik befasst sich mit der Anzahl von Anordnung von einer bestimmten Anzahl an Elementen mit oder ohne Berücksichtigung der Reihenfolge. Sind die Elemente unterscheidbar (und kommen diese nur einzeln vor) so spricht man von “ohne Wiederholung”. Sind die Elemente hingegen nicht unterscheidbar, so spricht man von “mit Wiederholung”, da jedes Element, dass bereits verwendet wurde, wieder verwendet werden kann.

  • Kombination (mit Wiederholung) – Auswahl von k aus n Elementen – keine Reihenfolgenbeachtung Kombination mit Wiederholung
  • Kombination (ohne Wiederholung) – Auswahl von k aus n Elementen – keine ReihenfolgenbeachtungKombination ohne Wiederholung
  • Variation (mit Wiederholung) – Auswahl von k aus n Elementen – Reihenfolgenbeachtung: nk
  • Variation (ohne Wiederholung) – Auswahl von k aus n Elementen – Reihenfolgenbeachtung: Variation ohne Wiederholung
  • Permuation (mit Wiederholung) – Auswahl von n aus n Elementen – Reihenfolgenbeachtung: Permutation mit Wiederholung
  • Permutation (ohne Wiederholung) – Auswahl von n aus n Elementen – Reihenfolgenbeachtung: n!
Autor: , Letzte Aktualisierung: 24. November 2022