Hauptmenü öffnen

Kombination (Kombinatorik)

Art und Weise, wie Dinge zu bestimmten Gruppen zusammengefasst werden

Eine Kombination (von lateinisch combinatio ‚Zusammenfassung‘) oder ungeordnete Stichprobe ist in der Kombinatorik eine Auswahl von Objekten aus einer gegebenen Grundmenge, die (im Gegensatz zur Permutation) nicht alle Objekte der Grundmenge enthalten muss und bei der (ebenfalls im Gegensatz zur Permutation) die Reihenfolge unberücksichtigt bleibt. Können Objekte dabei mehrfach ausgewählt werden, so spricht man von einer Kombination mit Wiederholung, darf dagegen jedes Objekt nur genau einmal auftreten, spricht man von einer Kombination ohne Wiederholung. Die Ermittlung der Anzahl möglicher Kombinationen ist eine Standardaufgabe der abzählenden Kombinatorik.

Inhaltsverzeichnis

BegriffsabgrenzungBearbeiten

Eine Kombination oder ungeordnete Stichprobe ist eine Auswahl von   Objekten aus einer Menge von   Objekten, bei der die Reihenfolge der Auswahl keine Rolle spielt. Soll die Reihenfolge dennoch eine Rolle spielen, so spricht man statt von einer Kombination von einer Variation. Davon abweichend werden in der Literatur manchmal auch Kombinationen und Variationen zusammengefasst und eine Variation wird dann „Kombination mit Berücksichtigung der Reihenfolge“ genannt.[1]

Bei einer Kombination mit Wiederholung können Objekte mehrfach ausgewählt werden, während bei einer Kombination ohne Wiederholung jedes Objekt nur einmal auftreten darf.[2] In einem Urnenmodell entspricht eine Kombination mit Wiederholung einer Ziehung der Kugeln mit Zurücklegen und eine Kombination ohne Wiederholung einer Ziehung ohne Zurücklegen.

Kombination ohne WiederholungBearbeiten

 
Alle 10 Kombinationen ohne Wiederholung von drei aus fünf Objekten

AnzahlBearbeiten

Auswahlprobleme ohne Wiederholung können auf zweierlei Weise untersucht werden. Im klassischen Fall geht man dabei von einer Variation ohne Wiederholung aus, für die es bei   von   auszuwählenden Elementen   Möglichkeiten gibt. Nun aber können die   ausgewählten Elemente ihrerseits auf   verschiedene Weisen angeordnet werden. Wenn diese verschiedenen Anordnungen allesamt keine Rolle spielen, also immer wieder als die gleiche Auswahl von Elementen gelten sollen, müssen wir das erhaltene Ergebnis noch einmal durch   teilen und erhalten damit nur noch

 

Möglichkeiten, deren Anzahl auch als Binomialkoeffizient bezeichnet wird.

Ein zweiter, insbesondere bei der Auswertung von Bernoulli-Experimenten Anwendung findender Ansatz fasst die Kombination ohne Wiederholung als ein Anordnungsproblem auf. Die Zahl der möglichen Auswahlen kann dann dadurch ermittelt werden, dass man die Zahl der voneinander unterscheidbaren Anordnungen ausgewählter und nicht ausgewählter Objekte bestimmt, wobei diese selbst nicht mehr voneinander unterscheidbar sein sollen, die gesamte Ausgangsmenge also nur noch in die beiden Objektklassen „ausgewählt“ (z. B. schwarze Kugel mit weißer Nummer) und „nicht ausgewählt“ (z. B. weiße Kugel mit schwarzer Nummer) unterteilt ist. Wenn man nun untersucht, wie viele verschiedene Anordnungen dieser schwarzen und weißen Kugeln es gibt, wobei nur ihre Farbe eine Rolle spielen soll, ergibt sich gemäß der Formel für die Zahl der Permutationen von Elementen, die jeweils klassenweise nicht unterscheidbar sind, die obige Formel. Ob   dabei die Zahl der ausgewählten Objekte und   die Zahl der nicht ausgewählten Objekte ist oder umgekehrt, ist für das Ergebnis unerheblich; welche der beiden Teilmengen der Ausgangsmenge die interessierende ist, hat keinen Einfluss auf die Anzahl der möglichen Aufteilungen.

MengendarstellungBearbeiten

Die Menge

 

ist die „Menge aller Kombinationen ohne Wiederholung von   Objekten zur Klasse  “ und hat die oben angegebene Anzahl von Elementen. Eine alternative Darstellung dieser Menge ist

 .

BeispieleBearbeiten

LottoBearbeiten

Wenn aus   Objekten nun   ohne Wiederholung und ohne Beachtung der Reihenfolge ausgewählt werden sollen, wie dies zum Beispiel bei der Ziehung der Lottozahlen der Fall ist, gibt es dabei

 

mögliche Auswahlen. Beim Lotto ist die Reihenfolge egal, ob beispielsweise zuerst die   und dann die   oder erst die   und dann die   gezogen wird, spielt für die Gewinnzahlen und die Bestimmung des Lottogewinners keine Rolle. Die Anzahl der möglichen Lösungen errechnet sich aus der Zahl der zunächst   und dann   Kugeln, die gezogen werden können, also  . Da aber die Reihenfolge egal ist, muss berücksichtigt werden, dass das Produkt   gleichwertige Lösungen umfasst. Bei drei gezogenen Zahlen ist die Anzahl der Möglichkeiten  , aber weil die Ziehungsreihenfolge der Kugeln egal ist, muss das Produkt durch die Anzahl möglicher Ziehungsreihenfolgen   geteilt werden.

Anzahl der WegeBearbeiten

 
Wandgemälde mit dem mehrfach verborgenen Schriftzug „Deo gracias“

Das Wandgemälde in der Wismarer Heiligen-Geist-Kirche zeigt in der Mitte den Buchstaben „D“ und rechts unten ein „S“. Wenn man nur Schritte nach rechts bzw. unten geht, ergibt sich immer der Text „DEOGRACIAS“. Insgesamt geht man neun Schritte, davon muss man fünfmal einen Schritt nach rechts und viermal einen nach unten gehen. Dafür gibt es

 

Möglichkeiten. Man kann aber mit demselben Ergebnis auch in die anderen Ecken gehen: fünfmal nach rechts und viermal nach oben beziehungsweise links und unten oder links und oben. Insgesamt ergeben sich bei diesem Beispiel daraus   Möglichkeiten. Diese Aufgabenstellung wird gewöhnlich als Manhattan-Problem bezeichnet, benannt nach dem New Yorker Stadtteil mit dem regelmäßigen Straßenverlauf.[3]

Kombination mit WiederholungBearbeiten

 
Alle 35 Kombinationen mit Wiederholung von drei aus fünf Objekten

AnzahlBearbeiten

Sollen aus einer Menge von   Elementen   Elemente ausgewählt werden, wobei ihre Reihenfolge weiterhin ohne Belang sein soll, sie sich aber nun auch wiederholen dürfen, wie das z. B. beim Ziehen mit Zurücklegen möglich ist, ergibt sich für die Zahl der Möglichkeiten folgende Formel (siehe Multimenge):

 

Dies ist ersichtlich, wenn man jedes Ergebnis von   ausgewählten Elementen aus   möglichen Elementen durch eine Folge von   Symbolen darstellt, wobei   Symbole („N“) die Elemente der Auswahlmenge, sowie   Symbole („K“) die   ausgewählten Elemente darstellen. Die Folge beginnt immer mit einem N-Symbol; die Anzahl der K-Symbole vor dem zweiten N-Symbol entspricht der Häufigkeit, mit der das erste der   Elemente gezogen wurde, die Anzahl der K-Symbole zwischen dem zweiten und dritten N-Symbol dem zweiten der   Elemente usw. Da bis auf das erste „N“ alle Symbole frei kombiniert werden können, entspricht die Anzahl der Kombinationen und damit die Anzahl der Zugmöglichkeiten der angegebenen Formel.

Beispielsweise entspricht bei der Auswahl von 3 aus 5 Elementen („1“, „2“, „3“, „4“, „5“) mit Zurücklegen das Ergebnis „1, 3, 3“ der Symbolfolge „NKNNKKNN“, das Ergebnis „5, 5, 5“ der Folge „NNNNNKKK“. Es ergeben sich   mögliche Kombinationen.

MengendarstellungBearbeiten

Die Menge

 

ist die „Menge aller Kombinationen mit Wiederholung von   Dingen zur Klasse  “ und hat die oben angegebene Anzahl von Elementen. Hierbei bezeichnet   die Anzahl des Auftretens des  -ten Elements der Stichprobe. Eine alternative Darstellung dieser Menge ist

 .

BeispieleBearbeiten

 
Bijektion zwischen Kombinationen mit Wiederholung von drei aus fünf Objekten (rechts) und Kombinationen ohne Wiederholung von drei aus sieben Objekten (links)

Gummibärchen-OrakelBearbeiten

Eine Anwendung davon ist das sogenannte Gummibärchen-Orakel, bei dem man   Bärchen aus einer Tüte mit Gummibärchen in   verschiedenen Farben auswählt. Demnach gibt es

 

verschiedene Kombinationen. Dabei gibt es fünf Kombinationen, bei denen alle Bärchen die gleiche Farbe haben,   Kombinationen mit zwei verschiedenen Farben,   mit drei Farben,   mit vier Farben und eine mit allen fünf Farben. Würde es beim Ziehen auf die Reihenfolge ankommen, hätte man es mit einer „Variation mit Wiederholung“ zu tun, das heißt mit   Möglichkeiten. Zur gleichen Anzahl   kommt man bei der Frage nach der Zahl der Möglichkeiten, vier Stifte aus einem Vorrat von Stiften mit sechs verschiedenen Farben auszuwählen (Mastermind ohne Berücksichtigung der Anordnung). Dagegen gibt es beim „richtigen“ Mastermind (mit Berücksichtigung der Anordnung)   Möglichkeiten.

UrneBearbeiten

Aus einer Urne mit fünf nummerierten Kugeln   wird dreimal eine Kugel gezogen   und jeweils wieder zurückgelegt. Man kann also bei allen drei Ziehungen immer aus fünf Kugeln auswählen. Wenn man die Reihenfolge der gezogenen Zahlen nicht berücksichtigt, gibt es

 

verschiedene Kombinationen. Diese   Kombinationen mit Wiederholung von fünf Dingen zur Klasse drei, also dreielementige Multimengen mit Elementen aus der Ausgangsmenge  , entsprechen dabei, wie die nebenstehende Grafik zeigt, genau den   Kombinationen ohne Wiederholung von sieben Dingen zur Klasse drei, also der Zahl dreielementiger Teilmengen einer insgesamt siebenelementigen Ausgangsmenge. (Die Existenz einer Bijektion kann zum Beweis der Formel für die Anzahl der Kombinationen mit Zurücklegen genutzt werden.)

WürfelBearbeiten

Dem Zurücklegen gleich ist die Verwendung mehrerer gleicher Objekte, wie beispielsweise Würfeln mit eins bis sechs Augen. Wie viele verschiedene Würfe sind mit drei Würfeln möglich? Grundsätzlich sind   unterschiedliche Würfe möglich, wenn man einen Würfel nach dem anderen wirft und die Reihenfolge beachtet. Wenn man dagegen alle drei Würfel gleichzeitig wirft, dann lässt sich keine Reihenfolge mehr sinnvoll definieren. Da beim gleichzeitigen Wurf aller drei Würfel beispielsweise der Wurf   von   oder   nicht mehr unterscheidbar ist, gibt es nur

 

verschiedene (unterscheidbare) Würfe. Nicht damit zu verwechseln ist die Summe der Augen, diese kann nur   verschiedene Werte (von   bis  ) annehmen.

LiteraturBearbeiten

WeblinksBearbeiten

  Wiktionary: Kombination – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen
  Commons: Combinations with repetition – Sammlung von Bildern, Videos und Audiodateien

EinzelnachweiseBearbeiten

  1. Hartung, Elpelt, Klösener: Statistik: Lehr- und Handbuch der angewandten Statistik. S. 96.
  2. Bronstein, Semendjajew: Taschenbuch der Mathematik. Harri Deutsch, 2008, ISBN 3-8171-2007-9, S. 810–811.
  3. Manhattan-Problem