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]

Eine Kombination oder ungeordnete Stichprobe ist eine Auswahl von k Objekten aus einer Menge von n 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]

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

Anzahl[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 k von n auszuwählenden Elementen \tfrac{n!}{(n-k)!} Möglichkeiten gibt. Nun aber können die k ausgewählten Elemente ihrerseits auf k! 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 k! teilen und erhalten damit nur noch

\frac{n!}{(n-k)! \, k!} = \frac{n (n-1)(n-2) \ldots (n-k+1)}{k!} = \binom{n}{n-k} = \binom{n}{k}

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 k dabei die Zahl der ausgewählten Objekte und n-k 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]

Die Menge

\bigl\{ (x_1, x_2, \ldots , x_n) \mid x_i \in \{0, 1\}, x_1 + \ldots + x_n = k \bigr\}

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

\bigl\{ (z_1, z_2, \ldots , z_k) \mid 1 \leq z_1 < z_2 < \dotsb < z_{k-1} < z_k \leq n \bigr\}.

Beispiele[Bearbeiten]

Lotto[Bearbeiten]

Wenn aus 49 Objekten nun 6 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

\binom{49}{6} = \frac{49!}{6! \, (49-6)!} = 13.983.816

mögliche Auswahlen. 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 Lösungen errechnet sich aus der Zahl der zunächst 49 und dann 48 Kugeln, die gezogen werden können, also 49 \cdot 48. Da aber die Reihenfolge egal ist, muss berücksichtigt werden, dass das Produkt 2 = 1 \cdot 2 = 2! gleichwertige Lösungen umfasst. Bei drei gezogenen Zahlen ist die Anzahl der Möglichkeiten 49 \cdot 48 \cdot 47, aber weil die Ziehungsreihenfolge der Kugeln egal ist, muss das Produkt durch die Anzahl möglicher Ziehungsreihenfolgen 6 = 1 \cdot 2 \cdot 3 = 3! geteilt werden.

Anzahl der Wege[Bearbeiten]

Das Wandgemälde[3] in der Wismarer Heiligen-Geist-Kirche zeigt in der Mitte den Buchstaben „D“ und links unten ein „S“. Wenn man nur Schritte nach links 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

{9 \choose 5} = \frac{9!}{5! \, 4!} = 126

Möglichkeiten. Man kann aber auch fünfmal nach rechts und viermal nach oben gehen, bzw. links und unten oder links und oben. Insgesamt ergeben sich bei diesem Beispiel daraus 126 \cdot 4 = 504 Möglichkeiten. Diese Aufgabenstellung wird gewöhnlich als Manhattan-Problem bezeichnet, benannt nach dem New Yorker Stadtteil mit dem regelmäßigen Straßenverlauf.[4]

Kombination mit Wiederholung[Bearbeiten]

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

Anzahl[Bearbeiten]

Sollen aus einer Menge von n Elementen k 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):

\frac{(n+k-1)!}{(n-1)! \, k!} = {n+k-1 \choose k} = {n+k-1 \choose n-1} = \left(\!\!{n\choose k}\!\!\right)


Dies ist ersichtlich, wenn man jedes Ergebnis von k ausgewählten Elementen aus n möglichen Elementen durch eine Folge von n+k Symbolen darstellt, wobei n Symbole („N“) die Elemente der Auswahlmenge, sowie k Symbole („K“) die k 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 n Elemente gezogen wurde, die Anzahl der K-Symbole zwischen dem zweiten und dritten N-Symbol dem zweiten der n 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.[5]

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 {n+k-1 \choose k} = {7 \choose 3} = 35 mögliche Kombinationen.

Mengendarstellung[Bearbeiten]

Die Menge

\bigl\{ (x_1, x_2, \ldots , x_{n}) \mid x_{i} \in \{0, 1, \ldots , k\}, x_1 + \ldots + x_n = k \bigr\}

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

\bigl\{ (z_1, z_2, \ldots , z_k) \mid 1 \leq z_1 \leq z_2 \leq \dotsb \leq z_{k-1} \leq z_k \leq n \bigr\}.

Beispiele[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]

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

\left(\!\!{5\choose 5}\!\!\right) = \binom{9}{5} = \frac{9!}{5! \, 4!} = 126

verschiedene Kombinationen. Dabei gibt es fünf 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 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 5^5 = 3125 Möglichkeiten. Zur gleichen Anzahl 126 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) 6^4 = 1296 Möglichkeiten.

Urne[Bearbeiten]

Aus einer Urne mit fünf nummerierten Kugeln (n=5) wird dreimal eine Kugel gezogen (k=3) 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

\left(\!\!{5\choose 3}\!\!\right) = \binom{7}{3} = \frac{7!}{4! \, 3!} = 35

verschiedene Kombinationen. Diese 35 Kombinationen mit Wiederholung von fünf Dingen zur Klasse drei, also dreielementige Multimengen mit Elementen aus der Ausgangsmenge \{1,2,3,4,5\}, entsprechen dabei, wie die nebenstehende Grafik zeigt, genau den 35 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]

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 6^3 = 216 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 1-1-2 von 1-2-1 oder 2-1-1 nicht mehr unterscheidbar ist, gibt es nur

\left(\!\!{6\choose 3}\!\!\right) = \binom{8}{3} = \frac{8!}{5! \, 3!} = 56

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

Literatur[Bearbeiten]

Einzelnachweise[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-817-12007-9, S. 810–811.
  3. Wandgemälde mit dem Schriftzug „Deo gracias“
  4. Manhattan-Problem
  5. http://www.youtube.com/watch?v=iDF5HgjMsyU

Weblinks[Bearbeiten]

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