Kombination (Kombinatorik)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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

Begriffsabgrenzung[Bearbeiten | Quelltext bearbeiten]

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 Wiederholung[Bearbeiten | Quelltext bearbeiten]

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

Anzahl[Bearbeiten | Quelltext bearbeiten]

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, die 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.

Mengendarstellung[Bearbeiten | Quelltext bearbeiten]

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

.

Beispiele[Bearbeiten | Quelltext bearbeiten]

Lotto[Bearbeiten | Quelltext bearbeiten]

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 Wege[Bearbeiten | Quelltext bearbeiten]

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 Wiederholung[Bearbeiten | Quelltext bearbeiten]

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

Anzahl[Bearbeiten | Quelltext bearbeiten]

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.[4]

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.

Mengendarstellung[Bearbeiten | Quelltext bearbeiten]

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

.

Beispiele[Bearbeiten | Quelltext bearbeiten]

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

Gummibärchen-Orakel[Bearbeiten | Quelltext bearbeiten]

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.

Urne[Bearbeiten | Quelltext bearbeiten]

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ürfel[Bearbeiten | Quelltext bearbeiten]

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, die kann nur verschiedene Werte (von bis ) annehmen.

Literatur[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  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
  4. http://www.youtube.com/watch?v=iDF5HgjMsyU

Weblinks[Bearbeiten | Quelltext bearbeiten]

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