Kombination (Kombinatorik)

Eine Kombination (von lateinisch combinatio, deutsch ‚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.

Begriffsabgrenzung

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.

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

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

Anzahl

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 ${\tfrac {n!}{(n-k)!}}$ 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

${\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, 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 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

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 Objekten zur Klasse “ 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

Lotto

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

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

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 $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

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

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

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 $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.

Kombination mit Wiederholung

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

Anzahl

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):

${\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 ausgewählten Elementen aus möglichen Elementen durch eine Folge von n+k 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 ${n+k-1 \choose k}={7 \choose 3}=35$ mögliche Kombinationen.

Mengendarstellung

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 Dingen zur Klasse “ und hat die oben angegebene Anzahl von Elementen. Hierbei bezeichnet $x_{{i}}$ die Anzahl des Auftretens des -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

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

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, 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 $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

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 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 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

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

Basierend auf einem Artikel in:

Wikipedia.de