Kombination (Kombinatorik)

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

Eine Kombination kann als eine Zusammenstellung von Objekten verstanden werden, die aus einer gegebenen Menge gewählt werden. Als eine ungeordnete Stichprobe ist sie eine Auswahl von $k$ Objekten aus einer Menge von $n$ Objekten, bei der die Reihenfolge der Auswahl keine Rolle spielt und nicht alle Objekte vertreten sein müssen. Darf in solch einer Zusammenstellung kein Objekt mehrmals gewählt werden, so wird diese als Kombination ohne Wiederholung bezeichnet, andernfalls als Kombination mit Wiederholung. Zusammenstellungen, bei denen die Reihenfolge eine Rolle spielt und nicht alle auswählbaren Objekte vertreten sein müssen, werden stattdessen als Variationen bezeichnet. Eine Variation kann auch als eine Kombination mit Berücksichtigung der Reihenfolge aufgefasst werden. Zusammenstellungen hingegen, bei denen die Reihenfolge eine Rolle spielt und alle Objekte auftreten müssen, werden Permutationen 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 somit 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 3 aus 5 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 $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\cdot (n-1)\cdot (n-2)\cdot \ldots \cdot (n-k+1)}{k!}}={\frac {n!}{(n-k)!\cdot 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 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 $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

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

Lotto

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

${\binom {49}{6}}={\frac {49!}{6!\cdot (49-6)!}}={\frac {49!}{6!\cdot 43!}}=13983816$

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 $49\cdot 48\cdot 47\cdot 46\cdot 45\cdot 44$. Weil aber die Reihenfolge egal ist, muss berücksichtigt werden, dass jede Kombination $6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1=6!$ gleichwertige Ziehungen umfasst, die sich aus der Anzahl der möglichen Permutationen der gezogenen Lottozahlen ergibt. Daher muss das Produkt $49\cdot 48\cdot 47\cdot 46\cdot 45\cdot 44$ durch die Anzahl der möglichen Ziehungsreihenfolgen, also $6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1$, geteilt werden.

Lottozahlen mit mindester Differenz

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 $z_{1},z_{2},z_{3},z_{4},z_{5},z_{6}$ die aufsteigend sortierten gezogenen Lottozahlen einer Ziehung, wo alle Lottozahlen mindestens die Differenz 5 zueinander haben, dann sind $z_{1},z_{2}-4,z_{3}-8,z_{4}-12,z_{5}-16,z_{6}-20$ 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 $a_{1},a_{2},a_{3},a_{4},a_{5},a_{6}$ aufsteigend sortierte ganze Zahlen im Intervall von 1 bis 29, dann sind $a_{1},a_{2}+4,a_{3}+8,a_{4}+12,a_{5}+16,a_{6}+20$ 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 $k=6$ und $n=29$:

${\binom {29}{6}}={\frac {29!}{6!\cdot (29-6)!}}={\frac {29!}{6!\cdot 23!}}=475020$

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

Zusammenstellung von Teams

Aus einer Gruppe von Personen werden 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

${\binom {22}{11}}={\frac {22!}{11!\cdot (22-11)!}}={\frac {22!}{11!\cdot 11!}}=705432$

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

${\frac {1}{2}}\cdot {\binom {22}{11}}=352716$

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

${\binom {16}{2}}={\frac {16!}{2!\cdot (16-2)!}}={\frac {16!}{2!\cdot 14!}}=120$

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

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

${\binom {9}{5}}={\frac {9!}{5!\cdot 4!}}=126$

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

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 $n=7+7=14$ und $k=7$ genau 3432 verschiedene Möglichkeiten ergeben, MANHATTANSUNSET zu lesen.

Kombination mit Wiederholung

Alle 35 Kombinationen mit Wiederholung von 3 aus 5 Objekten

Anzahl

Von einer Kombination mit Wiederholung ist die Rede, wenn aus einer Menge von $n$ Elementen $k$ Elemente ausgewählt werden sollen, wobei deren Reihenfolge ohne Belang ist, sie sich aber auch wiederholen dürfen, wie das beispielsweise beim Ziehen mit Zurücklegen möglich ist (siehe auch Multimenge). Für die Anzahl möglicher Kombinationen unter diesen Bedingungen gilt die folgende Formel:

${\frac {(n+k-1)!}{(n-1)!\cdot k!}}={\binom {n+k-1}{k}}={\binom {n+k-1}{n-1}}=\left(\!\!{\binom {n}{k}}\!\!\right)$

In der nebenstehenden Abbildung wird das Ergebnis für $k=3$ ausgewählte Elementen aus $n=5$ möglichen Elementen veranschaulicht, wobei die schwarzen Ziffern die Elemente der Auswahlmenge $\{1,2,3,4,5\}$ darstellen und die roten Ziffern jeweils die (wiederholt) gewählten Elemente zählen. Es ergeben sich somit ${\binom {n+k-1}{k}}={\binom {7}{3}}={\frac {7!}{3!\cdot 4!}}=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 $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

Bijektion zwischen Kombinationen mit Wiederholung von 3 aus 5 Objekten (rechts) und Kombinationen ohne Wiederholung von 3 aus 7 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 zieht, die sehr viele Gummibärchen in genau $n=5$ verschiedenen Farben enthält. 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. Wenn jedoch die Reihenfolge keine Rolle spielt, beträgt die Anzahl möglicher Kombinationen

$\left(\!\!{\binom {5}{5}}\!\!\right)={\binom {9}{5}}={\frac {9!}{5!\cdot 4!}}=126.$

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

Aus einer Urne mit 5 nummerierten Kugeln wird 3-mal eine Kugel gezogen und jeweils wieder zurückgelegt, d. h. es ist $n=5$ und $k=3$. 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

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

verschiedene Kombinationen. Diese 35 Kombinationen mit Wiederholung von 5 Dingen zur Klasse 3, also 3-elementige Multimengen mit Elementen aus der Ausgangsmenge $\{1,2,3,4,5\}$, entsprechen dabei, wie die obenstehende 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

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

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

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

Die Zahl $k=4$ soll als Summe von $n=3$ 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

$\left(\!\!{\binom {3}{4}}\!\!\right)={\binom {6}{4}}={\frac {6!}{4!\cdot 2!}}=15$

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	$\bigstar \bigstar \bigstar \bigstar ||$
3 + 1 + 0	AAAB	$\bigstar \bigstar \bigstar |\bigstar |$
3 + 0 + 1	AAAC	$\bigstar \bigstar \bigstar ||\bigstar$
2 + 2 + 0	AABB	$\bigstar \bigstar |\bigstar \bigstar |$
2 + 1 + 1	AABC	$\bigstar \bigstar |\bigstar |\bigstar$
2 + 0 + 2	AACC	$\bigstar \bigstar ||\bigstar \bigstar$
1 + 3 + 0	ABBB	$\bigstar |\bigstar \bigstar \bigstar |$
1 + 2 + 1	ABBC	$\bigstar |\bigstar \bigstar |\bigstar$
1 + 1 + 2	ABCC	$\bigstar |\bigstar |\bigstar \bigstar$
1 + 0 + 3	ACCC	$\bigstar ||\bigstar \bigstar \bigstar$
0 + 4 + 0	BBBB	$|\bigstar \bigstar \bigstar \bigstar |$
0 + 3 + 1	BBBC	$|\bigstar \bigstar \bigstar |\bigstar$
0 + 2 + 2	BBCC	$|\bigstar \bigstar |\bigstar \bigstar$
0 + 1 + 3	BCCC	$|\bigstar |\bigstar \bigstar \bigstar$
0 + 0 + 4	CCCC	$||\bigstar \bigstar \bigstar \bigstar$

Literatur

• Martin Aigner: Diskrete Mathematik. Vieweg, 2006, ISBN 3-8348-9039-1. 
• Konrad Jacobs, Dieter Jungnickel: Einführung in die Kombinatorik. de Gruyter, 2003, ISBN 3-11-016727-1. 
• Joachim Hartung, Bärbel Elpelt, Karl-Heinz Klösener: Statistik: Lehr- und Handbuch der angewandten Statistik. Oldenbourg, 2005, ISBN 3-486-57890-1. 

Weblinks

Wiktionary: Kombination – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

Commons: Combinations with repetition – Sammlung von Bildern, Videos und Audiodateien

• V.M. Mikheev: Combination. In: Michiel Hazewinkel (Hrsg.): Encyclopedia of Mathematics. Springer-Verlag und EMS Press, Berlin 2002, ISBN 1-55608-010-7 (englisch, encyclopediaofmath.org). 
• kfgauss70: Combinations with repeated elements. In: PlanetMath. (englisch)
• Eric W. Weisstein: Combination. In: MathWorld (englisch).