Mit den Kombinationen kommt ein neuer Aspekt zum Tragen. Bei den Permutationen und k-Permutationen haben wir bisher immer die Reihenfolge berücksichtigt. Das mussten wir fast, denn wenn wir die Reihenfolge nicht berücksichtigen, können wir gar nicht über die Anzahl möglicher Permutationen oder k-Permutation reden. Wenn die Objekte $A$ , $B$ und $C$ da sind und es nicht mehr darauf ankommt, in welcher Reihenfolge, dann schrumpfen die sechs Permutationen zu einer Menge:

$(A,B,C),\;\; (A,C,B),\;\; (B,A,C),\;\; (B,C,A),\;\; (C,A,B),\;\; (C,B,A) \quad \rightarrow \quad \Big\{ A, B, C \Big\}$

Bei den Kombinationen gibt es keine Reihenfolge mehr!

Kombinationen ohne Zurücklegen

Stellen wir uns einen Eisstand vor, der 18 leckere Eissorten im Angebot hat. Amélie wählt zwei Kugeln aus. Wie viele mögliche Eiskombinationen gibt es, wenn beide Kugeln unterschiedlich sind?

Beachte, dass in der Kombinatorik «zweimal das gleiche Eis» bedeutet, dass die gewählte erste Kugel «zurückgelegt» wird. In diesem ersten Beispiel wollen wir das nicht und verlangen, dass beide Kugeln wirklich unterschiedlich sind. Wir betrachten deshalb ein Urnenmodell ohne Zurücklegen.

Wenn wir die Reihenfolge berücksichtigen, dann haben wir natürlich die Anzahl $k$ -Permutationen schnell berechnet:

$^nP_k = \frac{n!}{(n-k)!} = \frac{18!}{(18-2)!} = \frac{18!}{16!} = \frac{18 \cdot 17 \cancel{\cdot 16 \cdot 15 \cdot ... \cdot 2 \cdot 1}}{\cancel{16 \cdot 15 \cdot ... \cdot 2 \cdot 1}} = 18 \cdot 17 = 306$

Jetzt wird aber die Reihenfolge unterschieden, d.h. Schokolade auf Vanille ist nicht gleich Vanille auf Schokolade. Wir haben bei zwei Kugeln zwei mögliche $k$ -Permutationen: $(A,B)$ und $(B,A)$ . Hätte Amélie drei Kugeln gewählt, dann gäbe es sechs $k$ -Permutationen: $(A,B,C),\;(A,C,B),\;(B,A,C),\;(B,C,A),\;(C,A,B)$ und $(C,B,A)$ . Für Amélie kommt es aber nicht darauf an, in welcher Reihenfolge der Eisverkäufer die Kugel serviert hat. Sie ignoriert die Reihenfolge und macht aus «Schokolade auf Vanille» bzw. «Vanille auf Schokolade» einfach «Schokolade mit Vanille»:

$(A,B),\;\; (B,A) \quad \rightarrow \quad \Big\{ A, B \Big\}$

Deshalb teilen wir 306 mögliche $k$ -Permutationen von zwei Kugeln aus 18 Eissorten durch die Anzahl verschiedener Reihenfolgen von zwei Kugeln ( $2!$ ) und erhalten die Anzahl möglicher Kombinationen $C_2^{18}$ :

$^{18}C_2 = \frac{306}{2!} = \frac{306}{2} = 153$

Es gibt für sie 153 verschiedene Kombinationen aus den 18 Eissorten (bei zwei unterschiedlichen Kugeln).

Verallgemeinern wir diese Rechnung, so müssen wir die Anzahl $k$ -Permutationen $P_k^n$ noch durch die Anzahl Reihenfolgen $k!$ teilen, um die korrekte Anzahl Kombinationen von $k$ aus $n$ zu erhalten:

$^nC_k = \frac{P_k^n}{k!} = \frac{\frac{n!}{(n-k)!}}{k!} = \frac{n!}{(n-k)! \; k!}$

Der etwas komplizierte Bruch kann durch den sog. Binomialkoeffizienten abgekürzt geschrieben werden:

$\frac{n!}{(n-k)! \; k!} = \begin{pmatrix} n \\ k \end{pmatrix}$

Die Anzahl Kombinationen von $k$ Objekten aus einer Grundmenge von $n$ Objekten ohne Zurücklegen, beträgt:

$^nC_k = \frac{n!}{(n-k)! \; k!} = \begin{pmatrix} n \\ k \end{pmatrix}$

Kombinationen sind wie $k$ -Permutationen, jedoch ohne Berücksichtigung der Reihenfolge.

Beispiel

An einem regionalen Rennen, an welchem 20 Athleten teilnehmen, können sich die drei Besten für die landesweiten Wettkämpfe qualifizieren. Wie viele mögliche Dreierteams gibt es?

In einem früheren Beispiel hatten wir die Anzahl Podest-Besetzungen berechnet, die 20 Teilnehmer bilden können. Nun ist die Sache sehr sehr ähnlich, aber die Reihenfolge spielt keine Rolle mehr. Die ersten Drei sind qualifiziert und wir unterscheiden nicht, wer jetzt Erster, wer Zweiter war etc.

Es handelt sich deshalb um eine Kombination, d.h. ohne Berücksichtigung der Reihenfolge. Da die Athleten nicht doppelt vorkommen können, ist es ein «Ziehen ohne Zurücklegen». Die Anzahl möglicher Dreierteams-Kombinationen ist deshalb:

$^{20}C_3 = \frac{20!}{(20-3)! \; 3!} = \underline{1'140}$

Beachte, dass die Anzahl Podest-Besetzungen $6'840$ betragen hat. Das ist genau das Sechsfache von $1'140$ . Das ist kein Zufall, denn die drei qualifizierten Athleten können auf 6 verschiedene Arten auf dem Podest stehen. Es sind wieder einmal unsere 6 Permutationen von 3 Objekten.

Beispiel

Während der Projektwoche braucht der Lehrer eine Gruppe von 5 Schülerinnen und Schülern, die zusammen die schweren Sachen wegräumen. In der Gruppe sollten mindestens 3 Schüler sein.

Auf wie viele Arten kann er diese Gruppe zusammenstellen, wenn in der Klasse 8 Jungs und 7 Mädchen sind?

Bevor wir uns ans Rechnen machen, unterscheiden wir drei mögliche Kategorien von Gruppen: Gruppen mit 5 Jungs, Gruppen mit 4 Jungs und Gruppen mit 3 Jungs.

Jetzt überlegen wir uns, wie wir Gruppen von 5 Jungs aus 8 Jungs bilden können. Die Reihenfolge spielt keine Rolle (Kombination) und es ist ein Ziehen ohne Zurücklegen, da jeder Schüler nur einmal in der Gruppe vorkommen kann.

$^8C_5 = \frac{8!}{(8-5)! \; 5!} = 56$

Für die Gruppen mit 4 Jungs und einem Mädchen haben wir die Anzahl Möglichkeiten 4 aus 8 ( $^8C_4$ ) bei den Jungs und die Anzahl Möglichkeiten 1 aus 7 ( $^7C_1$ ) bei den Mädchen. Die beiden Kombinationszahlen müssen gemäss Fundamentalsatz der Kombinatorik mit einander multipliziert werden:

$^8C_4 \;\cdot\; ^7C_1 = \frac{8!}{(8-4)! \; 4!} \cdot \frac{7!}{(7-1)! \; 1!} = 70 \cdot 7 = 490$

Analog berechnen wir die Anzahl Möglichkeiten für die Gruppe mit 3 Jungs und 2 Mädchen:

$^8C_3 \;\cdot\; ^7C_2 = \frac{8!}{(8-3)! \; 3!} \cdot \frac{7!}{(7-2)! \; 2!} = 56 \cdot 21 = 1'176$

Damit hat der Lehrer total $56+490+1'176=\underline{1'722}$ Möglichkeiten, seine Fünfergruppe zusammenzustellen!

Kombinationen mit Zurücklegen

Wir erlauben jetzt das Zurücklegen oder anders gesprochen: Es dürfen Wiederholungen vorkommen. Erstaunlicherweise macht das die Sache etwas komplizierter. Wir schauen uns wieder das Beispiel der zwei Kugeln Eis an, erlauben Amélie dieses Mal aber auch zweimal auf die gleiche Sorte zu setzen. Das ist das was wir mit «Zurücklegen» der Kugel im Urnenmodell meinen. Die gleiche Sorte kann nochmals gezogen werden.

Um die Veranschaulichung dieses Beispiels übersichtlich zu behalten, reduzieren wir die zur Auswahl stehenden Eissorten (vorerst) auf drei!

Wir bauen eine kleine Tabelle auf. Horizontal haben wir die drei üblichen Eissorten Schokolade ( $S$ ), Vanille ( $V$ ) und Erdbeer ( $E$ ). Jetzt machen wir einfach für jede mögliche Kombination eine Zeile, indem wir für die gewählte Sorte ein Kreuz setzen:

$C$	$S$	\|	$V$	\|	$E$
1	$X$ $X$	\|		\|
2	$X$	\|	$X$	\|
3	$X$	\|		\|	$X$
4		\|	$X$ $X$	\|
5		\|	$X$	\|	$X$
6		\|		\|	$X$ $X$

Aus der Tabelle lesen wir ab, dass es 6 mögliche Kombinationen gibt. Wären das Zurücklegen nicht erlaubt, so würden drei Kombinationen wegfallen, nämlich $\{S,S\}$ , $\{V,V\}$ und $\{E,E\}$ . Wir kontrollieren kurz, ob wir ohne Zurücklegen tatsächlich auf $6-3=3$ Kombinationen kommen:

$^3C_2 = \frac{3!}{(3-2)!\;2!} = \frac{6}{1 \cdot 2} = 3$

Es stimmt! Wir haben beim Modus mit Zurücklegen drei Kombinationen mit unterschiedlichen Kugeln und drei Kombinationen mit gleichen Kugeln.

Zurück zu unserer Tabelle. Ich habe sie bewusst so gezeichnet, dass die Trennstriche | ebenfalls vorkommen. Ich schreibe die sechs Zeilen nun als Permutationen von $X$ und | hin:

$(X,X,|,|),\;\;(X,|,X,|),\;\;(X,|,|,X),\;\;(|,X,X,|),\;\;(|,X,|,X),\;\;(|,|,X,X)$

Diese Anzahl von 6 Permutationen können wir ja rechnen: Es handelt sich um Permutationen aus einer Grundmenge von 4 Objekten mit je doppelt vorkommenden $X$ und |:

$^4P_{(2,2)} = \frac{4!}{2!\;2!} = \frac{24}{4} = 6$

Die Grundmenge ist die Länge unserer Permutationen. Im oberen Fall bestanden die Permutationen aus je zwei $X$ und |, was 4 «Stellen» entspricht. Allgemeiner gesprochen, ist die Grundmenge $n=k+s$ , wobei $k$ die Anzahl Kreuze und $s$ die Anzahl Trennstriche bedeutet.

Wir können die Anzahl möglicher Permutationen mit $k$ Kreuzen und $s$ Strichen, die sich wiederholen, aufschreiben als:

$^{k+s}P_{(k,s)} = \frac{(k+s)!}{k!\;s!}$

Nun ist die Anzahl Striche $s$ eigentlich immer gleich $(n-1)$ , denn wir haben $n$ Spalten in unserer Tabelle und dazu braucht es immer $(n-1)$ Trennstriche:

$s = n-1$

Wir ersetzen $s$ mit dem neuen Ausdruck und erhalten:

$^{k+n-1}P_{(k,n-1)} = \frac{(k+n-1)!}{k!\;(n-1)!}$

Damit haben wir die allgemeine Formel für die Berechnung der Anzahl Kombinationen mit Zurücklegen von $k$ Objekten aus einer Grundmenge von $n$ . Wir gesagt, geht es hier um Kombinationen, d.h. die Reihenfolge der gezogenen Objekte wird nicht berücksichtigt.

Die Anzahl Kombinationen von $k$ Objekten aus einer Grundmenge von $n$ Objekten mit Zurücklegen, d.h. mit möglichen Wiederholungen, beträgt:

$\overline{^nC_k} = \frac{(n+k-1)!}{(n-1)! \; k!} = \begin{pmatrix} n+k-1 \\ k \end{pmatrix}$

Beispiel

Drei Kinder spielen ein Spiel, wobei der Gewinner oder die Gewinnerin jeder Runde, ein Bonbon aus der Schale nehmen darf. In der Schale hat es noch 7 Bonbons für die letzten 7 Runden des Spiels.

Auf wie viele Arten können die 7 verbleibenden Bonbons auf die drei Kinder verteilt werden?

Im Extremfall könnte das erste Kind alle sieben Bonbons kriegen. Dann gibt es die Möglichkeit (ebenfalls noch extrem), dass das erste Kind sechs Bonbons hat und das zweite Kind nur eines. Wenn wir das in einer Tabelle mit Kreuzen und Trennstrichen aufzeichnen, wäre der Anfang der Tabelle wie folgt:

Wir brauchen die Tabelle nicht vollständig aufzuzeichnen, denn wir können bereits jetzt vermuten, dass sie sehr lang sein könnte. Andererseits können wir das Problem jetzt gleich lösen, wie damals mit den 2 Kugeln Eis aus einer Auswahl von 3 Eissorten.

Die Anzahl Kombinationen von $k$ aus $n$ mit Zurücklegen, d.h. mit erlaubter Wiederholung, haben wir hier klar gegeben. $n=3$ ist die Anzahl Spalten, also Kinder, die Bonbons erhalten. $k=7$ ist die Anzahl Kreuze, also Anzahl Bonbons, die zu verteilen sind und die Anzahl Trennstriche ist wieder $3-1=2$ , eines weniger als die Anzahl Spalten. Damit können wir die Anzahl Kombinationen berechnen:

$\overline{^3C_7} = \frac{(3+7-1)!}{(3-1)! \; 7!} = \frac{9!}{2! \; 7!} = \underline{36}$

Unsere vollständige Tabelle hätte 36 Zeilen gehabt!

Kombinationen

Kombinationen ohne Zurücklegen

Beispiel

Beispiel

Kombinationen mit Zurücklegen

Beispiel

Zufallsgrösse und Wahrscheinlichkeitsverteilung

Abkling- und Sättigungsfunktion

Binomialkoeffizient

Ereignismenge

Arkusfunktionen

Berechnung des Schwerpunkts

Schreibe einen Kommentar Antworten abbrechen

$C$	1	\|	2	\|	3
1	$XXXXXXX$	\|		\|
2	$XXXXXX$	\|	$X$	\|
3	$XXXXXX$	\|		\|	$X$

Kombinationen ohne Zurücklegen

Beispiel

Beispiel

Kombinationen mit Zurücklegen

Beispiel

Ähnliche Artikel

Schreibe einen Kommentar Antworten abbrechen