Kombination (Kombinatorik)

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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 im Gegensatz zur Permutation und Variation 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 einmal auftreten, spricht man 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 3 aus 5 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, 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 Kugeln) und nicht ausgewählt (z. B. weiße Kugeln) 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]

Beim Lotto 6 aus 49 werden 6 von 49 Kugeln gezogen, die mit den Zahlen 1 bis 49 beschriftet sind. Weil die Kugeln nicht erneut gezogen werden können und die Reihenfolge nicht berücksichtigt wird, ist das Ergebnis jeder Ziehung der Lottozahlen eine Kombination ohne Wiederholung. Es gibt daher

Möglichkeiten für die Auswahl der gezogenen Lottozahlen. Beim Lotto ist die Reihenfolge egal, ob beispielsweise zuerst die 9 und dann die 17 oder erst die 17 und dann die 9 gezogen wird, spielt für die Gewinnzahlen und die Bestimmung des Lottogewinners keine Rolle. Die Anzahl der möglichen Kombinationen errechnet sich aus dem Produkt der 49, 48, 47, 46, 45 und schließlich 44 Kugeln, die gezogen werden können, also . Weil aber die Reihenfolge egal ist, muss berücksichtigt werden, dass jede Kombination gleichwertige Ziehungen umfasst, die sich aus der Anzahl der möglichen Permutationen der gezogenen Lottozahlen ergibt. Daher muss das Produkt durch die Anzahl der möglichen Ziehungsreihenfolgen, also , geteilt werden.

Lottozahlen mit mindester Differenz[Bearbeiten | Quelltext bearbeiten]

Gesucht ist die Anzahl der Möglichkeiten, dass bei einer Ziehung im Lotto 6 aus 49 alle 6 gezogenen Lottozahlen mindestens die Differenz 5 zueinander haben. Dabei hilft folgende Zuordnung: Sind die aufsteigend sortierten gezogenen Lottozahlen einer Ziehung, wo alle Lottozahlen mindestens die Differenz 5 zueinander haben, dann sind aufsteigend sortierte verschiedene ganze Zahlen im Intervall von 1 bis 29 und umgekehrt. Es ist ziemlich offensichtlich, dass dann alle diese 6 Zahlen mindestens die Differenz 1 zueinander haben. Diese Zuordnung kann auch umgekehrt betrachtet werden. Sind aufsteigend sortierte ganze Zahlen im Intervall von 1 bis 29, dann sind Lottozahlen mit der gewünschten Eigenschaft. Zwischen der Menge der gesuchten Kombinationen aus den 6 Lottozahlen und der Menge der Kombinationen der 6 Zahlen im Intervall von 1 bis 29 gibt es daher eine bijektive Abbildung.

Die 6 verschiedenen ganzen Zahlen können ohne weitere Einschränkungen aus den Zahlen von 1 bis 29 ausgewählt werden. Es ergibt sich daher die Anzahl der Kombinationen ohne Wiederholung mit und :

Das ist die gesuchte Anzahl der Möglichkeiten, dass alle 6 gezogenen Lottozahlen mindestens die Differenz 5 zueinander haben.

Zusammenstellung von Teams[Bearbeiten | Quelltext bearbeiten]

Aus einer Gruppe von Personen werden sollen zwei Teams, z. B. Sportmannschaften, zusammengestellt werden. Werden aus einer Gruppe von 22 Fußballspielern zwei Teams aus jeweils 11 Spielern zusammengestellt, dann ist die Anzahl der Möglichkeiten genauso groß wie die Anzahl der Möglichkeiten, 11 Personen aus einer Gruppe von 22 Personen auszuwählen, denn das erste Team lässt sich verstehen als die ausgewählten Personen und das zweite Team lässt sich verstehen als die nicht ausgewählten Personen. Diese Anzahl der Möglichkeiten ist gleich

Entscheidend ist dabei, dass klar ist, welches das erste und welches das zweite Team ist, und dass die Reihenfolge der Spieler nicht berücksichtigt wird, also z. B. nicht betrachtet wird, welche Aufgabe eine Person oder welche Position ein Sportler im Team hat.

Wenn egal ist, welches das erste und welches das zweite Team ist, wird bei dieser Berechnung jede Möglichkeit 2-mal gezählt. Durch die Vertauschung der zwei Teams oder dadurch, dass nur die zuvor nicht ausgewählten Personen ausgewählt werden, ergibt sich die jeweils andere Kombination. Um die Anzahl der Möglichkeiten in solchen Fällen zu berechnen, muss also die Anzahl der Kombinationen durch 2 geteilt werden. Für die Zusammenstellung von zwei gleich großen und nicht nummerierten Teams aus 22 Fußballspielern ergeben sich

Möglichkeiten.

Die zwei betrachteten Teams müssen selbstverständlich nicht gleich groß sein, damit sich für jede Zusammenstellung eine Kombination ohne Wiederholung ergibt. Wenn z. B. aus einer Gruppe von 16 Personen 2 Schiedsrichter ausgewählt werden, die ein Match im Handball leiten, gibt es dafür

Möglichkeiten. Wie die anderen 14 Personen zugeordnet werden, wird bei dieser Betrachtung nicht berücksichtigt. In diesem Fall besteht das erste betrachtete Team aus den 2 Schiedsrichtern und das zweite betrachtete Team besteht aus den anderen 14 Personen. Weil nur die Anzahl der Auswahlmöglichkeiten für die Schiedsrichter gesucht ist, ist es für die Berechnung nicht von Bedeutung, dass die anderen 14 Personen zwei Handballteams aus jeweils 7 Handballspielern sind.

Anzahl der Wege[Bearbeiten | Quelltext bearbeiten]

Wandgemälde mit dem mehrfach verborgenen Schriftzug DEOGRACIAS

Das Deo-Gracias-Fresko 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 9 Schritte, davon muss man 5-mal einen Schritt nach rechts und 4-mal einen nach unten gehen. Dafür gibt es

Möglichkeiten. Man kann aber mit demselben Ergebnis auch in die anderen Ecken gehen: 5-mal nach rechts und 4-mal 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]

Irene Schramm-Biermann, Manhattansunset

Das Bild rechts bezieht sich ebenfalls auf das Manhattan-Problem. Es geht hier um die Buchstabenfolge, die das Wort MANHATTANSUNSET ergibt. Start ist bei M links oben, Ziel ist das T rechts unten. Man benötigt jeweils 7 Schritte nach rechts und 7 Schritte nach unten, sodass sich mit und genau 3432 verschiedene Möglichkeiten ergeben, MANHATTANSUNSET zu lesen.

Kombination mit Wiederholung[Bearbeiten | Quelltext bearbeiten]

Alle 35 Kombinationen mit Wiederholung von 3 aus 5 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 die Symbole N die Elemente der Auswahlmenge und die Symbole K die ausgewählten Elemente darstellen. Die Folge beginnt immer mit einem N. Die Anzahl der K vor dem zweiten N entspricht der Häufigkeit, mit der das erste der Elemente gezogen wurde, die Anzahl der K zwischen dem zweiten und dritten N entspricht der Häufigkeit des zweiten Elements 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 den 5 Elementen der Menge mit Zurücklegen das Ergebnis 1, 3, 3 der Symbolfolge NKNNKKNN, das Ergebnis 5, 5, 5 der Folge NNNNNKKK.

Die Symbolfolgen können auch mit senkrechten Strichen und Sternen dargestellt werden. Das Ergebnis 1, 3, 3 entspricht und das Ergebnis (5, 5, 5) entspricht . Die 3 Sterne können an 7 verschiedenen Positionen platziert werden.

Es ergeben sich daher 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 3 aus 5 Objekten (rechts) und Kombinationen ohne Wiederholung von 3 aus 7 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 5 Kombinationen, bei denen alle Bärchen die gleiche Farbe haben, 40 Kombinationen mit zwei verschiedenen Farben, 60 mit drei Farben, 20 mit vier Farben und 1 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 126 kommt man bei der Frage nach der Zahl der Möglichkeiten, 4 Stifte aus einem Vorrat von Stiften mit 6 verschiedenen Farben auszuwählen.

Urne[Bearbeiten | Quelltext bearbeiten]

Aus einer Urne mit 5 nummerierten Kugeln wird 3-mal eine Kugel gezogen und jeweils wieder zurückgelegt, d. h. es ist und . Man kann also bei allen 3 Ziehungen immer aus 5 Kugeln auswählen. Wenn man die Reihenfolge der gezogenen Zahlen nicht berücksichtigt, gibt es

verschiedene Kombinationen. Diese 35 Kombinationen mit Wiederholung von 5 Dingen zur Klasse 3, also 3-elementige Multimengen mit Elementen aus der Ausgangsmenge , entsprechen dabei, wie die nebenstehende Grafik zeigt, genau den 35 Kombinationen ohne Wiederholung von 7 Dingen zur Klasse 3, also der Zahl 3-elementiger Teilmengen einer insgesamt 7-elementigen 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 1 bis 6 Augen. Wie viele verschiedene Würfe sind mit 3 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 3 Würfel gleichzeitig wirft, dann lässt sich keine Reihenfolge mehr sinnvoll definieren. Da beim gleichzeitigen Wurf aller 3 Würfel beispielsweise die Würfe (1, 1, 2) und (1, 2, 1) und (2, 1, 1) nicht mehr unterscheidbar sind, gibt es nur

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

Darstellung von Summen[Bearbeiten | Quelltext bearbeiten]

Die Zahl soll als Summe von natürlichen Zahlen größer oder gleich 0 dargestellt werden. Jede Darstellung entspricht dem 4-maligen Ziehen einer Kugel aus einer Urne mit 3 nummerierten Kugeln, z. B. A, B, C, wobei jede gezogene Kugel zurückgelegt wird und die Reihenfolge der Kugeln nicht berücksichtigt wird. Jeder Summand gibt an, wie oft die entsprechende Kugel gezogen wurde. Es gibt also

verschiedene Kombinationen. Die folgende Tabelle listet die 15 Darstellungen der Summe 4 und die entsprechenden Kombinationen der Kugeln auf. Außerdem ist jeweils eine entsprechende Darstellung mit senkrechten Strichen und Sternen angegeben. Direkt aufeinanderfolgende Sterne stellen die Summanden dar und die senkrechten Striche stellen die Pluszeichen dar. Die Anzahl der Darstellungen ist daher gleich der Anzahl der Möglichkeiten, 4 Sterne an 6 verschiedenen Positionen zu platzieren.

Darstellung der Summe 4 Kombination Darstellung mit senkrechten Strichen

und Sternen

4 + 0 + 0 AAAA
3 + 1 + 0 AAAB
3 + 0 + 1 AAAC
2 + 2 + 0 AABB
2 + 1 + 1 AABC
2 + 0 + 2 AACC
1 + 3 + 0 ABBB
1 + 2 + 1 ABBC
1 + 1 + 2 ABCC
1 + 0 + 3 ACCC
0 + 4 + 0 BBBB
0 + 3 + 1 BBBC
0 + 2 + 2 BBCC
0 + 1 + 3 BCCC
0 + 0 + 4 CCCC

Literatur[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]

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

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