Kombination (Kombinatorik)

Eine Kombination (von lateinisch combinatio ‚Zusammenfassung‘) o​der ungeordnete Stichprobe i​st in d​er Kombinatorik e​ine Auswahl v​on Objekten a​us einer gegebenen Grundmenge, d​ie (im Gegensatz z​ur Permutation) n​icht alle Objekte d​er Grundmenge enthalten m​uss und b​ei der (im Gegensatz z​ur Permutation u​nd Variation) d​ie Reihenfolge unberücksichtigt bleibt. Können Objekte d​abei mehrfach ausgewählt werden, s​o spricht m​an von e​iner Kombination m​it Wiederholung. Darf dagegen j​edes Objekt n​ur einmal auftreten, spricht m​an von e​iner Kombination o​hne Wiederholung. Die Ermittlung d​er Anzahl möglicher Kombinationen i​st eine Standardaufgabe d​er abzählenden Kombinatorik.

Begriffsabgrenzung

Eine Kombination oder ungeordnete Stichprobe ist eine Auswahl von ${\displaystyle k}$ Objekten aus einer Menge von ${\displaystyle 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 e​iner Kombination m​it Wiederholung können Objekte mehrfach ausgewählt werden, während b​ei einer Kombination o​hne Wiederholung j​edes Objekt n​ur einmal auftreten darf.[2] In e​inem Urnenmodell entspricht e​ine Kombination m​it Wiederholung e​iner Ziehung d​er Kugeln m​it Zurücklegen u​nd eine Kombination o​hne Wiederholung e​iner Ziehung o​hne 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 ${\displaystyle k}$ von ${\displaystyle n}$ auszuwählenden Elementen ${\displaystyle {\tfrac {n!}{(n-k)!}}}$ Möglichkeiten gibt. Nun aber können die ${\displaystyle k}$ ausgewählten Elemente ihrerseits auf ${\displaystyle 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 ${\displaystyle k!}$ teilen und erhalten damit nur noch

${\displaystyle {\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, d​eren Anzahl a​uch 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 ${\displaystyle k}$ dabei die Zahl der ausgewählten Objekte und ${\displaystyle 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

${\displaystyle {\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 ${\displaystyle n}$ Objekten zur Klasse ${\displaystyle k}$“ und hat die oben angegebene Anzahl von Elementen. Eine alternative Darstellung dieser Menge ist

${\displaystyle {\bigl \{}(z_{1},z_{2},\ldots ,z_{k})\mid 1\leq z_{1}<z_{2}<\dotsb <z_{k-1}<z_{k}\leq n{\bigr \}}}$.

Lotto

Wenn aus ${\displaystyle 49}$ Objekten nun ${\displaystyle 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

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

mögliche Auswahlen. Beim Lotto ist die Reihenfolge egal, ob beispielsweise zuerst die ${\displaystyle 9}$ und dann die ${\displaystyle 17}$ oder erst die ${\displaystyle 17}$ und dann die ${\displaystyle 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 ${\displaystyle 49}$ und dann ${\displaystyle 48}$ Kugeln, die gezogen werden können, also ${\displaystyle 49\cdot 48}$. Da aber die Reihenfolge egal ist, muss berücksichtigt werden, dass das Produkt ${\displaystyle 2=1\cdot 2=2!}$ gleichwertige Lösungen umfasst. Bei drei gezogenen Zahlen ist die Anzahl der Möglichkeiten ${\displaystyle 49\cdot 48\cdot 47}$, aber weil die Ziehungsreihenfolge der Kugeln egal ist, muss das Produkt durch die Anzahl möglicher Ziehungsreihenfolgen ${\displaystyle 6=1\cdot 2\cdot 3=3!}$ geteilt werden.

Anzahl der Wege

Wandgemälde mit dem mehrfach verborgenen Schriftzug „Deo gracias“

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 neun Schritte, davon muss man fünfmal einen Schritt nach rechts und viermal einen nach unten gehen. Dafür gibt es

${\displaystyle {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 ${\displaystyle 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.[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 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 drei aus fünf Objekten

Anzahl

Sollen aus einer Menge von ${\displaystyle n}$ Elementen ${\displaystyle 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):

${\displaystyle {\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 ${\displaystyle k}$ ausgewählten Elementen aus ${\displaystyle n}$ möglichen Elementen durch eine Folge von ${\displaystyle n+k}$ Symbolen darstellt, wobei ${\displaystyle n}$ Symbole („N“) die Elemente der Auswahlmenge, sowie ${\displaystyle k}$ Symbole („K“) die ${\displaystyle 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 ${\displaystyle n}$ Elemente gezogen wurde, die Anzahl der K-Symbole zwischen dem zweiten und dritten N-Symbol dem zweiten der ${\displaystyle 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.

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

Mengendarstellung

Die Menge

${\displaystyle {\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 ${\displaystyle n}$ Dingen zur Klasse ${\displaystyle k}$“ und hat die oben angegebene Anzahl von Elementen. Hierbei bezeichnet ${\displaystyle x_{i}}$ die Anzahl des Auftretens des ${\displaystyle i}$-ten Elements der Stichprobe. Eine alternative Darstellung dieser Menge ist

${\displaystyle {\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 ${\displaystyle k=5}$ Bärchen aus einer Tüte mit Gummibärchen in ${\displaystyle n=5}$ verschiedenen Farben auswählt. Demnach gibt es

${\displaystyle \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, ${\displaystyle 40}$ Kombinationen mit zwei verschiedenen Farben, ${\displaystyle 60}$ mit drei Farben, ${\displaystyle 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 ${\displaystyle 5^{5}=3125}$ Möglichkeiten. Zur gleichen Anzahl ${\displaystyle 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) ${\displaystyle 6^{4}=1296}$ Möglichkeiten.

Urne

Aus einer Urne mit fünf nummerierten Kugeln ${\displaystyle (n=5)}$ wird dreimal eine Kugel gezogen ${\displaystyle (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

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

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

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 ${\displaystyle 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 ${\displaystyle 1-1-2}$ von ${\displaystyle 1-2-1}$ oder ${\displaystyle 2-1-1}$ nicht mehr unterscheidbar ist, gibt es nur

${\displaystyle \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, diese kann nur ${\displaystyle 16}$ verschiedene Werte (von ${\displaystyle 3}$ bis ${\displaystyle 18}$) annehmen.

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

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

Einzelnachweise

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