Kombinatorik Tutorial

Eine der wichtigsten Aufgaben in der Wahrscheinlichkeitsrechnung ist das Zählen von Dingen und Möglichkeiten. Das erledigt das Gebiet der Kombinatorik. Wir entwickeln Schreibweisen wie die Fakultät und den Binomialkoeffizienten. Und wir übersetzen die konkreten Zählaufgaben in Urnenmodelle, bei denen wir Kugeln aus einem Topf ziehen – mit oder ohne Zurücklegen, mit oder ohne Berücksichtigung der Reihenfolge. Für jeden dieser Fälle leiten wir hier die passende Kombinatorik-Formel her.

Wissenswertes über Mengen

Die Dinge, die wir zählen wollen, fassen wir in einer Menge zusammen. Wir alle kennen aus der Grundschule die Mengendiagramme mit zwei Kreisen, die einige Dinge enthalten. Und in der Mitte sind die Dinge, die zu beiden Mengen gehören. Schon damals war klar: Entweder gehört ein Element zu einer Menge oder nicht. Wenn eine Zahl $x$ in einer Menge $A$ enthalten ist, schreiben wir $x\in A$, andernfalls $x\notin A$.

Wir bezeichnen Mengen mit großen Buchstaben wie $A$ und $B$. Wenn wir die Elemente einer Menge auflisten, fassen wir sie in geschweifte Klammern:

• $A=\{3;5;7;9\}$
• $B=\{2;3;5;7\}$
• Die Elemente, die in $A$ und $B$ enthalten sind, bilden die Schnittmenge $A\cap B=\{3;5;7\}$.
• Die Elemente, die in $A$ oder $B$ enthalten sind, bilden die Vereinigungsmenge $A\cup B=\{2;3;5;7;9\}$.

Wir listen die Elemente mit Semikolon auf, so gibt es keine Verwechslung mit dem Dezimalkomma. Nur für den Fall, dass die Zahl 3,5 zu einer Menge gehören soll.

Die Kombinatorik will wissen, wie viele Elemente in einer Menge $M$ enthalten sind. Diese Zahl nennen wir die Mächtigkeit von $M$ und bezeichnen sie mit $|M|$. Mit den obigen Bezeichnungen gilt dann:

• $|A|=4$
• $|B|=4$
• $|A\cap B|=3$
• $|A\cup B|=5$

Produkte von Mengen

Aus zwei Mengen $M$ und $N$ können wir eine neue Menge bilden, indem wir je ein Element $m\in M$ und ein Element $n\in N$ zu einem Paar $(m,n)$ zusammenfassen. Die Menge aller solchen Paare bezeichnen wir als $M\times N$.

Ich glaube, dazu brauchen wir jetzt ein Beispiel: Wir würfeln gleichzeitig mit einem Würfel mit den Augenzahlen 1,2,3,4,5,6 und mit einem Tetraeder mit den Augenzahlen 1,2,3,4. Wir bezeichnen Menge der Augenzahlen des Würfels mit $W$ und die Menge der Augenzahlen des Tetraeders mit $T$. Dann gilt:

• $W=\{1;2;3;4;5;6\}$ mit $|W|=6$
• $T=\{1;2;3;4\}$ mit $|T|=4$
• Wurfergebnisse: $W\times T=\{(1;1),(1;2),(1;3),…\}$ mit $|W\times T|=\ ?$

Produktregel der Kombinatorik

Wie viele Elemente enthält die Menge $W\times T$? Jedes der 6 Würfelergebnisse kann man mit 4 Tetraeder-Ergebnissen kombinieren, also enthält die Menge $W\times T$ insgesamt $6\cdot 4=24$ Ergebnisse. Diese Erkenntnis formulieren wir als Regel:

Dazu gleich noch zwei Beispiele:

1. Ein Bettwaren-Fachgeschäft bietet eine Daunendecke in drei Qualitäten, vier Wärmestufen und fünf Größen an. Wie viele verschiedene Decken kann man dort auswählen?
   Lösung: Nach der Produktregel der Kombinatorik gibt es $3\cdot 4\cdot 5=60$ verschiedene Decken.
2. Wie viele mögliche Ergebnisse gibt es beim dreimaligen Wurf eines Würfels?
   Lösung: Wenn wir den Würfel einmal werfen, gibt es die Ergebnismenge $M=\{1;2;3;4;5;6\}$ mit $|M|=6$. Der dreifache Würfelwurf wird durch die Menge $M\times M\times M$ beschrieben. Und nach der Produktregel gilt:
   $$|M\times M\times M|=6\cdot 6\cdot 6=216$$

Ergebnisse abzählen

Oft wollen wir nicht alle möglichen Paare zählen, sondern nur solche, die eine Bedingung erfüllen. Eine Möglichkeit ist dann, die Ergebnisse einfach der Reihe nach aufzulisten und durchzuzählen. Wir müssen nur darauf achten, tatsächlich alle Elemente zu finden.

Beispiel: Wie viele Möglichkeiten gibt es, mit dreimaligem Wurf eines Würfels genau die Augensumme 10 zu erreichen?

Wir versuchen, mit der Produktregel zu argumentieren: Für den ersten Würfel gibt es 6 Möglichkeiten. Für den zweiten Würfel ist dann nicht mehr jede Augenzahl zulässig, denn zum Beispiel mit den Augenzahlen 66 sind wir schon über der geforderten Augensumme. Und auch 64 geht nicht, denn dann sind keine Augen für den dritten Würfel übrig. Hat der erste Würfel aber eine 5, kann beim zweiten Wurf wiederum eine 4 kommen. Das Prinzip „jeder mit jedem“ geht hier also nicht – keine Produktregel möglich.

Wir behelfen uns, indem wir nicht rechnen, sondern wir versuchen, alle möglichen Wurffolgen mit der Augensumme 10 aufzulisten. Wir finden zuerst irgendwelche Wurffolgen wie 343 oder 361. Damit wir sicher sind, alle Lösungen zu finden, gehen wir aber in einer definierten Reihenfolge vor und beginnen z.B. mit der zahlenmäßig größten Folge 631. Die nächstkleinere ist 622 und dann 613.

Das Prinzip ist, dass wir die erste 6 so lange wie möglich stehen lassen. Erst wenn alle Kombinationen mit 6.. aufgelistet sind, gehen wir auf 5.. und starten an der zweiten Stelle wieder mit der größtmöglichen Zahl. Das wäre hier 54. Mit dieser Vorgehensweise entsteht folgende Liste mit 27 Einträgen:

• 631 622 613
• 541 532 523 514
• 451 442 433 424 415
• 361 352 343 334 325 316
• 262 253 244 235 226
• 163 154 145 136

Auf diese Weise können wir sicherstellen, wirklich alle Möglichkeiten aufzulisten. Diese Art der Anordnung heißt lexikographische Ordnung – wie im Lexikon halt.

Ausblick: Mit diesen Zählmethoden berechnen wir im nächsten Kapitel, mit welcher Wahrscheinlichkeit wir beim dreimaligen Werfen eines Würfels die Augensumme 10 erzielen. Wir haben mit der Produktregel berechnet, dass es insgesamt 216 Ergebnisse gibt. Und wir haben gezählt, dass 27 davon die Augensumme 10 haben. Die gesuchte Wahrscheinlichkeit ist dann $\frac{27}{216}=12,5\%$.

Urnenmodelle

Die Probleme der abzählenden Kombinatorik kommen aus ganz verschiedenen Anwendungsgebieten. Es hat sich bewährt, diese Anwendungen in ein Modell zu übersetzen. In diesem Modell gibt es keine Schüler, keine Klassensprecher und keine Läufer, sondern es gibt ein Kugeln in einer Urne. Das ist einfach ein Topf, und für jeden Schüler (oder worum es gerade geht) ist eine Kugel in diesem Topf. Wenn die Dinge unterscheidbar sein sollen, können die Kugeln mit Zahlen beschriftet sein, oder es können verschiedenfarbige Kugeln sein. Wichtig ist, dass die (Gedanken-)Urne so
mit Kugeln befüllt wird, dass sie die Aufgabenstellung korrekt widerspiegelt.

Die Anzahl der Kugeln in dieser Urne wird mit $n$ bezeichnet, das ist die Grundgesamtheit der Stichprobe. Das Auswählen der Schüler, Läufer etc. wird nun dadurch dargestellt, dass wir Kugeln aus dieser Urne entnehmen. Wir entnehmen insgesamt k Kugeln, das ist der Stichprobenumfang.

Neben dem korrekten Befüllen der Urne müssen wir uns bei jeder Aufgabe zwei Fragen beantworten:

1. Spielt die Reihenfolge der Ziehungen eine Rolle? Geordnete Stichproben heißen Variationen, und ungeordnete Stichproben heißen Kombinationen.
2. Wird nach jedem Wurf die gezogene Kugel wieder zurückgelegt? Wenn ja, haben wir vor jedem Wurf die gleichen Ausgangsbedingungen. Wir sprechen von Ziehen mit Zurücklegen oder einer Stichprobe mit Wiederholung. Wenn die Kugel nicht wieder zurückgelegt wird, haben wir Ziehen ohne Zurücklegen oder eine Stichprobe ohne Wiederholung. In diesem Fall reduziert sich bei jedem Zug die Zahl der Kugeln einer Farbe und damit auch die Gesamtzahl der Kugeln im Topf.

Auf diese Weise entstehen vier verschiedene Fälle. In Anwendungsaufgaben müssen wir feststellen, welcher Fall zu der Aufgabe passt. Dann bestimmen wir die Parameter $n$ und $k$ und haben für jeden der Fälle eine Formel zur Verfügung. Diese Formeln nehmen wir schon mal vorweg und werden sie gleich ausführlich erarbeiten:

	mit Wiederholung	ohne Wiederholung
geordnete Stichprobe (Variation)	$\displaystyle n^k$	$\displaystyle\frac{n!}{(n-k)!}$
ungeordnete Stichprobe (Kombination)	$\displaystyle \binom{n+k-1}{k}$	$\displaystyle \binom{n}{k}$

In dieser Tabelle steckt viel Neues: Es sind vier Formeln vom Himmel gefallen, und es gibt unbekannte Notationen wie $n!$ und $\binom nk$. Es gibt also viel zu tun, fangen wir an!

Anordnung von n Elementen

Beispiel: Wie viele „Wörter“ kann man aus den Buchstaben M,A,T,H,E bilden, wenn man alle Buchstaben genau einmal verwendet?

Im ersten Zug sind 5 Buchstaben im Topf, im zweiten noch 4, im dritten noch 3 usw. Nach der Produktregel gibt es insgesamt

$$5\cdot 4\cdot 3\cdot 2\cdot 1=120$$

Möglichkeiten. Produkte dieser Art kommen sehr oft vor und sind Grundlage für viele weitere Abzählprobleme, deshalb haben diese Produkte einen eigenen Namen und eine Kurzschreibweise, die wir nun einführen.

Fakultät

Das Produkt der ersten $n$ natürlichen Zahlen bezeichnen wir mit $n!$ (sprich: „$n$ Fakultät“):
$$n!=n\cdot(n-1)\cdot(n-2)\cdot\ldots\cdot 1$$
Für das Weitere ist es einfacher, wenn auch $0!$ (das leere Produkt) einen Wert hat. Deshalb legen wir fest: $0!=1$. Wir stellen es uns so vor, dass ein Produkt ohne echte Faktoren der Wert 1 hat. Das ist plausibel und harmoniert auch mit allen weiteren Berechnungen.

Wir wollen einige Fakultäten berechnen:

• $1! = 1 = 1$
• $2! = 1\cdot 2 = 2$
• $3! = 1\cdot 2\cdot 3 = 2!\cdot 3 = 6$
• $4! = 1\cdot 2\cdot 3\cdot 4 = 3!\cdot 4 = 24$
• $5! = 1\cdot 2\cdot 3\cdot 4\cdot 5 = 4!\cdot 5 = 120$

Wie im vorigen Abschnitt dargestellt, beschreibt $n!$ die Anzahl Möglichkeiten, $n$ Dinge anzuordnen. Eine Auswahl findet noch nicht statt, da alle $n$ Elemente angeordnet werden. Aber wir sind auf dem Weg zu unserer ersten Kombinatorik-Formel.

Absteigende Produktfolgen (Teile von Fakultäten)

Die Fakultät $n!$ enthält immer alle Faktoren von $n$ bis 1. Wir können mit Fakultäten aber auch Produktfolgen darstellen, die nicht bis zur 1 gehen. Dazu erweitern wir den Term als Bruch mit den fehlenden Faktoren:

$$7\cdot 6\cdot 5\cdot 4=\frac{7\cdot 6\cdot 5\cdot 4}1=\frac{7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}{3\cdot 2\cdot 1}=\frac{7!}{3!}=\frac{7!}{(7-4)!}$$

Wir formulieren diese Produktfolgen als Regel:

Das klingt kompliziert, ist aber ganz einfach, deshalb schnell noch ein Beispiel dazu: Wir notieren eine absteigende Folge von 5 Faktoren, beginnend bei 17:

$$\underbrace{17}_{n}\cdot 16\cdot 15\cdot 14\cdot\underbrace{13}_{n-k+1}=\frac{17!}{(17-5)!}=\frac{17!}{12!}$$

Diese Formel wird uns nun dabei helfen, geordnete Stichproben zu beschreiben, bei der nicht alle $n$ Elemente angeordnet werden. Damit erhalten wir die erste Kombinatorik-Formel aus der obigen Tabelle.

Geordnete Stichprobe ohne Wiederholung

Beispiel: Wie viele mögliche Platzierungen gibt es bei einem 100m-Lauf mit 8 Läufern auf den ersten drei Plätzen?

Für den Sieger gibt es 8 mögliche Läufer, für den Zweitplatzierten 7 und für den dritten noch 6 Möglichkeiten. Mit der Produktregel gibt es also
$$8\cdot 7\cdot 6=\frac{8!}{(8-3)!}$$
Möglichkeiten. Bei der Fakultät-Schreibweise wenden wir unser Wissen über absteigende Produktfolgen an.

Wir übersetzen das Beispiel in ein Urnenmodell und erhalten die folgende Kombinatorik-Formel:

Ungeordnete Stichprobe ohne Wiederholung

Beispiel: Aus den 24 Schülern der Klasse soll ein fünfköpfiger Ausschuss gebildet werden, der die nächsten Klassenfahrt plant. Wie viele Möglichkeiten gibt es, diesen Ausschuss zusammenzustellen?

Aus 24 Schülern sollen 5 gleichberechtigt für den Ausschuss ausgewählt werden. Der Ausschuss (Arne, Franziska, Bente, Johann, Henry) ist derselbe wie (Johann, Franziska, Arne, Henry, Bente). Deshalb handelt es sich um eine ungeordnete Stichprobe.

Nichtsdestotrotz nähern wir uns der Lösung schrittweise und wählen die Schüler der Reihe nach aus. Für den ersten Schüler gibt es 24 Möglichkeiten, für den zweiten 23 und so weiter, so dass wir zunächst bei
$$24\cdot 23\cdot 22\cdot 21\cdot 20=\frac{24!}{19!}$$
Möglichkeiten landen. Dadurch haben wir die Schüler in einer bestimmten Reihenfolge ausgewählt, was aber gerade keine Rolle spielen soll. Wir haben also jede Ausschussbesetzung mehrfach gezählt und müssen noch bestimmen, wie oft wir die Mitglieder untereinander vertauschen können.

Es gibt $5!$ Möglichkeiten, die fünf Schüler untereinander anzuordnen. Deshalb müssen wir für den Ausdruck $\frac{24!}{19!}$ noch durch $5!$ teilen und erhalten als Endergebnis: Es gibt
$$\frac{24!}{19!\cdot 5!}$$
Möglichkeiten, aus 24 Schülern einen fünfköpfigen Ausschuss zu bilden. Mit dieser Argumentation erhalten wir folgende Regel:

Dieser Bruch ist in der Kombinatorik und Wahrscheinlichkeitsrechnung so wichtig, dass er eine eigene Bezeichnung und Kurzschreibweise hat. Lies einfach weiter.

Binomialkoeffizient

Für ganze Zahlen $n\ge 0$ und $k\ge 0$ mit $k\le n$ ist der Binomialkoeffizient „$n$ über $k$“ wie folgt definiert:
$$\binom nk = \frac{n!}{(n-k)!\cdot k!}$$
Der Binomialkoeffizient beschreibt die Anzahl Möglichkeiten, aus $n$ Elementen $k$ ohne Wiederholung und ohne Berücksichtigung der Reihenfolge auszuwählen. Noch mathematischer ausgedrückt: $\binom nk$ ist die Anzahl $k$-elementiger Teilmengen einer $n$-elementigen Menge.

Der Binomialkoeffizient hat einige Eigenschaften, die seine Berechnung oft vereinfachen. Es lohnt sich, das mal durchzuarbeiten, weil es mehr Einsichten liefert als einfach „8 nCr 3“ auf dem Taschenrechner zu tippen. Diese Eigenschaften lassen sich auch gut kombinatorisch veranschaulichen.

1. $\binom nk$ ist, obwohl als Bruch definiert, immer eine natürliche Zahl. Die Faktoren im Nenner lassen sich also immer vollständig wegkürzen. Beweisen wollen wir das an dieser Stelle nicht, aber es stimmt wirklich!
2. Es ist $\binom n0=\frac{n!}{n!\cdot 0!}=1$. Anschaulich: Es gibt genau eine Möglichkeit, aus n Dingen keines auszuwählen, nämlich die leere Menge.
3. Es ist $\binom nn=\frac{n!}{(n-n)!\cdot n!}=1$. Es gibt genau eine Möglichkeit, aus n Dingen n auszuwählen, nämlich indem man alle auswählt.
4. Außerdem gilt $\binom nk=\binom n{n-k}$, wie man durch Einsetzen in die Definition feststellt. Im Nenner vertauschen sich nämlich genau die Faktoren. Dies kann man wie folgt plausibel machen: Statt aus $n$ Dingen $k$ auszuwählen, kann ich auch die $n-k$ Dinge festlegen, die ich nicht auswähle.
5. Zur Berechnung von $\binom nk$ ohne Taschenrechner gibt es folgende Regel: Im Zähler stehen k Faktoren „von oben“, im Nenner k Faktoren „von unten“. Das sieht dann so aus:
   $$\binom 83=\frac{8\cdot 7\cdot 6}{1\cdot 2\cdot 3}=4\cdot 7\cdot 2=56$$
6. Man kann die Regeln auch kombinieren:
   $$\binom{12}{8}=\binom{12}{4}=\frac{12\cdot 11\cdot 10\cdot 9}{1\cdot 2\cdot 3\cdot 4}=3\cdot 11\cdot 5\cdot 3=495$$
7. Der Term $\binom n2$ lässt sich recht einfach berechnen:
   $$\binom n2=\frac{n\cdot (n-1)}{2}$$
   Da eine der Zahlen $n$ und $n-1$ durch 2 teilbar ist, lässt sich der Bruch immer vor dem Ausrechnen kürzen:
   $$\binom{10}2=\frac{10\cdot 9}{2}=5\cdot 9=45$$
8. Und wer auf diese Rechenspiele keine Lust hat, gibt in den Taschenrechner für $\binom{12}4$ ein: \anf{12 nCr 4}.

Eine schöne Anwendung des Binomialkoeffizienten ist das Pascalsche Dreieck.

Das Pascalsche Dreieck

Ungeordnete Stichprobe mit Wiederholung

Beispiel: Bei einem Sonderangebot kann man sich eine Getränkekiste (12 Flaschen) aus drei verschiedenen Getränkesorten beliebig zusammenstellen. Wie viele Möglichkeiten gibt es dafür?

Diesen Fall behandeln wir mit einem Trick. Wir nennen die drei Getränkesorten A,B,C und betrachten als Beispiel die Stichprobe AABACBCCAAA. Da es eine ungeordnete Stichprobe ist, können wir sie auch als AAAAAABBBCCC schreiben. (Umsortieren der Flaschen in der Kiste verändert die Auswahl nicht.)

Nun fügen wir zwischen den verschiedenen Sorten Trennstriche ein: AAA | BBBBB | CCCC. Für drei Sorten brauchen wir zwei Trennstriche, und die Stichprobe ist nun eindeutig durch die Position der Trennstriche festgelegt. Da wir nun 12 Flaschen und zwei Trennstriche haben, benötigen wir in unserem Gedankenexperiment nun 14 Plätze.

Anstatt die Getränkesorten auszuwählen, verteilen wir nun zwei Trennstriche auf 14 Plätze und legen fest, dass die Zwischenräume jeweils mit den Getränkesorten A,B,C aufgefüllt werden sollen. Für die Anordnung der Trennstriche gibt es $\binom{14}2$ Plätze.

Allgemein benötigen wir für $n$ Getränkesorten $n-1$ Trennstriche und haben dann insgesamt $k+n-1$ Plätze zu besetzen ($k$ Getränkeflaschen und $n-1$ Trennstriche). Auf diese Plätze werden die $n-1$ Trennstriche verteilt, und wir erhalten
$$\binom {n+k-1}{n-1}\stackrel{(*)}{=}\binom{n+k-1}{(n+k-1)-(n-1)}=\binom{n+k-1}k$$
Möglichkeiten. Bei der Umformung $(*)$ wurde die Regel $\binom nk=\binom n{n-k}$ angewendet.

Damit haben wir auch den vierten Fall gelöst, der nicht so oft vorkommt wie die anderen.. Wir notieren die allgemeine Regel:

Übungsaufgaben

Nun wird es Zeit, das Erlernte an verschiedenen Aufgaben anzuwenden. Finde bei den Übungsaufgaben einen kombinatorischen Lösungsweg, um die gefragten Anzahlen zu bestimmen. Die Lösungen der Kombinatorik-Aufgaben gibt es hier.

1. Wir wollen Eis essen und stellen uns einen Eisbecher zusammen.
   1. Wie viele Möglichkeiten hat man, sich aus den Eissorten Vanille, Schokolade, Zitrone, Erdbeere und Mokka einen Eisbecher mit drei Kugeln zusammenzustellen?
   2. Wie viele Eisbecher gibt es, wenn Zitrone und Erdbeere nicht zusammen verwendet werden sollen?
2. Klassenfahrt nach Amrum! Die Klasse 4b fährt ins Schullandheim Ban Horn. Die 14 Mädchen der Klasse werden in einem 6er und einem 8er Zimmer untergebracht.
   1. Wie viele Möglichkeiten gibt es, die Mädchen auf die beiden Zimmer zu verteilen?
   2. In wie vielen davon sind Lene und Jelva im gleichen Zimmer?
3. Beim Bäcker gibt es ein Frühstückspaket, das aus 10 Brötchen besteht. Man kann es aus vier verschiedenen Sorten (Schnittbrötchen, Semmeln, Mohn, Mehrkorn) beliebig zusammenstellen. Wie viele verschiedene Zusammenstellungen sind möglich?
4. Ein Fußballspiel geht ins Elfmeterschießen.
   1. Wie viele Möglichkeiten hat der Trainer, aus den 11 Spielern auf dem Platz ein Elfmeterschießen mit 5 Spielern zusammenzustellen?
   2. Wie viele Möglichkeiten sind es, wenn der sicherste Schütze zuerst schießt und der Torwart gar nicht schießen soll?
5. Wie viele Möglichkeiten gibt es, 8 Personen an einem runden Tisch zu platzieren? Zwei Möglichkeiten gelten als gleich, wenn jeder links und rechts die gleichen Tischnachbarn hat.
6. Bei einer Feier stößt jeder Teilnehmer mit jedem anderen an. Lasse hat mitgezählt und hört 25 Mal „kling“. Warum hat er sich verzählt? Wie viele Teilnehmer sind mindestens auf der Feier, wenn es öfter „geklingt“ hat, als Lasse gezählt hat?
7. Aus dem Ziffernvorrat 1,1,1,2,2,3 werden dreistellige Zahlen gebildet. Schreibe alle Möglichkeiten in einer Liste auf. Gehe dabei systematisch vor.
8. Auf wie viele Arten kann man auf einem Schachbrett von der linken unteren zur rechten oberen Ecke gelangen, wenn nur jeweils ein Feld nach rechts bzw. oben weitergezogen werden darf?
9. Du würfelst mit einem Würfel vier Mal hintereinander und willst die Augensumme 7 erreichen. Welche Möglichkeiten ergeben sich?
10. Das Viertelfinale im DFB-Pokal wird ausgelost.
    1. Wie viele verschiedene Auslosungen sind möglich? Die Reihenfolge innerhalb einer Paarung ist bedeutsam, weil sie über das Heimrecht entscheidet. Die Reihenfolge der Paarungen spielt keine Rolle.
    2. Wie viele verschiedene Auslosungen gibt es, wenn auch die Reihenfolge innerhalb einer Paarung egal ist?
    3. Bei wie vielen davon spielen Holstein Kiel und Bayern München gegeneinander (egal wo)?
    4. Mit welcher Wahrscheinlichkeit spielen Holstein Kiel und Bayern München gegeneinander?
11. Beim wöchentlichen Badminton-Abend treffen sich 5 Spieler und spielen in wechselnden Besetzungen Doppel (also zwei gegen zwei). Wie viele Spiele müssen gemacht werden, damit jedes Zweierteam gegen jedes andere Zweierteam einmal angetreten ist?
12. Beim Brettspiel „Siedler von Catan“ würfelt man mit zwei normalen Würfeln.
    1. Wie viele Augenpaare sind möglich?
    2. Erstelle eine Tabelle, die zu jeder möglichen Augensumme notiert, wie häufig diese Augensumme möglich ist.

Lösungen zu den Kombinatorik-Aufgaben

Schau dir die Lösung einer Aufgabe bitte erst an, nachdem du dich ausgiebig mit eigenen Lösungsideen beschäftigt hast. Bei Kombinatorik-Aufgaben gibt es üblicherweise keine komplizierten Lösungswege, sondern man muss meist nur die richtige Formel ermitteln und anwenden. Es lohnt sich also durchaus, bei Problemen noch einmal die relevanten Abschnitte des Tutorials nachzulesen und die folgenden Lösungswege nur zum Vergleich der eigenen Lösung zu nutzen. Man tappt sonst leicht in eine „Lesefalle“, wenn man sich Lösungen nur durchliest und dabei denkt „ja, habe ich verstanden“. Aber Mathematik betreiben bedeutet nicht, die Lösungen anderer zu verstehen, sondern selbst Lösungen für Probleme zu finden. Und diese Aussage beantwortet nebenbei auch die Frage „Wofür ist Mathe eigentlich gut?“ In Mathe lernt man, Probleme zu analysieren und Lösungswege zu finden. Und das ist nun wirklich eine wichtige Fertigkeit im Leben.

Nun aber zu den Lösungen:

1. Wir wollen Eis essen und stellen uns einen Eisbecher zusammen.
   1. Wie viele Möglichkeiten hat man, sich aus den Eissorten Vanille, Schokolade, Zitrone, Erdbeere und Mokka einen Eisbecher mit drei Kugeln zusammenzustellen?
      
      Lösung: Der Eisbecher ist eine ungeordnete Stichprobe ohne Wiederholung mit $k=3$ Kugeln aus $n=5$ Sorten. Also gibt es $\binom 53=\binom 52=10$ verschiedene Eisbecher.
   2. Wie viele Eisbecher gibt es, wenn Zitrone und Erdbeere nicht zusammen verwendet werden sollen?
      
      Lösung: Wir subtrahieren von der Gesamtzahl möglicher Eisbecher diejenigen, bei denen Zitrone und Erdbeere zusammen vorkommen. Diese sind ZEV, ZES, ZEM. Also bleiben noch 7 Möglichkeiten übrig.
2. Klassenfahrt nach Amrum! Die Klasse 4b fährt ins Schullandheim Ban Horn. Die 14 Mädchen der Klasse werden in einem 6er und einem 8er Zimmer untergebracht.
   1. Wie viele Möglichkeiten gibt es, die Mädchen auf die beiden Zimmer zu verteilen?
      
      Lösung: Aus den 14 Mädchen werden zunächst 6 ausgewählt, die in das 6er-Zimmer kommen. Die Belegung des anderen Zimmers ergibt sich dann automatisch. Also gibt es $\binom{14}6$ mögliche Zimmer-Belegungen. Andererseits könnte man auch zunächst das 8er-Zimmer belegen und die restlichen Kinder ins 6er-Zimmer stecken. Dann gibt es $\binom{14}8$ mögliche Belegungen. Aber zum Glück haben beide Ausdrücke denselben Wert, denn eine Rechenregel für den Binomialkoffizienten besagt: $\binom{14}6=\binom{14}{14-6}=\binom{14}{8}=3003$. Und dass diese Gleichheit auch kombinatorisch sinnvoll ist, hat diese Aufgabe sehr schön gezeigt.
   2. In wie vielen davon sind Lene und Jelva im gleichen Zimmer?
      
      Lösung: Wir setzen Lene und Jelva vorab zusammen in ein Zimmer. Wenn sie im 8er-Zimmer sind, gibt es dort für die verbleibenden 12 Mädchen noch 6 Plätze. Also gibt es $\binom{12}6$ Möglichkeiten. Wenn Lene und Jelva im 6er-Zimmer sind, gibt es in diesem Zimmer für 12 Mädchen noch 4 Plätze, also $\binom{12}4$ Möglichkeiten. Insgesamt gibt es also $\binom{12}6+\binom{12}4=1419$ Möglichkeiten der Verteilung, bei denen Lene und Jelva im gleichen Zimmer sind.
      Mit diesen Informationen können wir im nächsten Kapitel die Wahrscheinlichkeit berechnen, mit der Lene und Jelva im gleichen Zimmer landen. Sie beträgt $\frac{1419}{3003}=0,4725=47,25\%\text,$ wenn die Lehrerin die Kinder zufällig verteilt. Aber welche Lehrerin macht das schon.
3. Beim Bäcker gibt es ein Frühstückspaket, das aus 10 Brötchen besteht. Man kann es aus vier verschiedenen Sorten (Schnittbrötchen, Semmeln, Mohn, Mehrkorn) beliebig zusammenstellen. Wie viele verschiedene Zusammenstellungen sind möglich?
   
   Lösung: Es handelt sich um eine ungeordnete Stichprobe mit Wiederholung. Aus $n=4$ Brötchensorten wird $k=10$ Mal eine Sorte mit Wiederholung ausgewählt. Es gibt
   $\binom{n+k-1}k=\binom{4+10-1}{10}=\binom{13}{10}=\binom{13}3=\frac{13\cdot 12\cdot 11}{1\cdot 2\cdot 3}=13\cdot 2\cdot 11=286$
   verschiedene Brötchentüten.
4. Ein Fußballspiel geht ins Elfmeterschießen.
   1. Wie viele Möglichkeiten hat der Trainer, aus den 11 Spielern auf dem Platz ein Elfmeterschießen mit 5 Spielern zusammenzustellen?
      
      Lösung: Es handelt sich um eine geordnete Stichprobe, da der Trainer auch festlegen muss, in welcher Reihenfolge die Schützen antreten. Und ein Spieler darf nicht zweimal schießen. Also gibt es $\frac{11!}{(11-5)!}=11\cdot 10\cdot 9\cdot 8\cdot 7$ Möglichkeiten.
   2. Wie viele Möglichkeiten sind es, wenn der sicherste Schütze zuerst schießt und der Torwart gar nicht schießen soll?
      
      Lösung: Nun gibt es noch 10 Spieler zur Auswahl, und der erste Schütze steht fest. Damit gibt es $1\cdot 9\cdot 8\cdot 7\cdot 6$ Möglichkeiten.
      
5. Wie viele Möglichkeiten gibt es, 8 Personen an einem runden Tisch zu platzieren? Zwei Möglichkeiten gelten als gleich, wenn jeder links und rechts die gleichen Tischnachbarn hat.
   
   Lösung: Als geordnete Stichprobe gibt es zunächst einmal $8!$ Möglichkeiten, die Personen der Reihe nach an den Tisch zu setzen. Nun müssen wir aber noch berücksichtigen, dass es ein runder Tisch ist. Jede Sitzanordnung kann noch einmal im Kreis herum rotieren, ohne dass sich die Nachbarn ändern. Diese Anordnungen gelten als gleich. Deshalb gibt es $\frac{8!}{8}=7!$ unterscheidbare Möglichkeiten. Man kann auch so argumentieren, dass man den ersten Gast zuerst irgendwo an den Tisch setzen kann und das nur eine unterscheidbare Situation liefert, da er noch keine Nachbarn hat. Erst wenn die erste Person sitzt, ist die Sitzordnung fixiert, und die weiteren können mit $7!$ Möglichkeiten gesetzt werden.
6. Bei einer Feier stößt jeder Teilnehmer mit jedem anderen an. Lasse hat mitgezählt und hört 25 Mal „kling“. Warum hat er sich verzählt? Wie viele Teilnehmer sind mindestens auf der Feier, wenn es öfter „geklingt“ hat, als Lasse gezählt hat?
   
   Lösung: Jeder stößt mit jedem an. Also werden aus $n$ Personen 2 ausgewählt, und zwar ohne Berücksichtigung der Reihenfolge. Es gibt $\binom n2=\frac{n\cdot(n-1)}2$ Möglichkeiten. Gibt es ein $n$, so dass hier 25 herauskommt? Man könnte nun diesen Term mit 25 gleichsetzen, eine quadratische Gleichung lösen und schauen, ob eine ganze Zahl für $n$ herauskommen kann. Oder wir probieren einfach ein paar Werte für $n$ aus. Für $n=7$ gibt es $\binom 72=21$ Teilnehmer, und für $n=8$ gibt es $\binom n2=28$ Teilnehmer. Es kann also nicht genau 25 Mal „kling“ erreicht werden, und es gibt mindestens 8 Teilnehmer. Vielleicht ist es ja der runde Tisch aus der vorigen Aufgabe.
7. Aus dem Ziffernvorrat 1,1,1,2,2,3 werden dreistellige Zahlen gebildet. Schreibe alle Möglichkeiten in einer Liste auf. Gehe dabei systematisch vor.
   
   Lösung: Wir beginnen mit der zahenmäßig größten Zahl 322 und versuchen dann immer, die nächstkleinere Zahl zu finden. Das erreichen wir, indem wir eine Stelle so lange unverändert lassen, bis wir in den nachfolgenden Stellen nichts mehr verkleinern können. Wenn wir eine Stelle verkleinert haben, setzen wir die nachfolgenden wieder auf den größtmöglichen Wert. Dabei müssen wir natürlich den Ziffernvorrat berücksichtigen. Es ergibt sich folgende Liste: 322 321 312 311 232 231 223 213 212 211 132 131 123 122 121 113 112 111.
8. Auf wie viele Arten kann man auf einem Schachbrett von der linken unteren zur rechten oberen Ecke gelangen, wenn nur jeweils ein Feld nach rechts bzw. oben weitergezogen werden darf?
   
   Lösung: Der Weg zum Ziel besteht aus 16 Zügen, davon 8 nach rechts und 8 nach oben in beliebiger Reihenfolge. Also müssen wir 8 Rechtszüge auf 16 Züge verteilen und erhalten $\binom{16}8$ mögliche Zugfolgen.
9. Du würfelst mit einem Würfel vier Mal hintereinander und willst die Augensumme 7 erreichen. Welche Möglichkeiten ergeben sich?
10. Das Viertelfinale im DFB-Pokal wird ausgelost.
    1. Wie viele verschiedene Auslosungen sind möglich? Die Reihenfolge innerhalb einer Paarung ist bedeutsam, weil sie über das Heimrecht entscheidet. Die Reihenfolge der Paarungen spielt keine Rolle.
    2. Wie viele verschiedene Auslosungen gibt es, wenn auch die Reihenfolge innerhalb einer Paarung egal ist?
    3. Bei wie vielen davon spielen Holstein Kiel und Bayern München gegeneinander (egal wo)?
    4. Mit welcher Wahrscheinlichkeit spielen Holstein Kiel und Bayern München gegeneinander?
11. Beim wöchentlichen Badminton-Abend treffen sich 5 Spieler und spielen in wechselnden Besetzungen Doppel (also zwei gegen zwei). Wie viele Spiele müssen gemacht werden, damit jedes Zweierteam gegen jedes andere Zweierteam einmal angetreten ist?
    
    Lösung: Wir besetzen das Feld und wählen für das erste Team 2 aus 5 Spielern aus. Für das zweite Team werden aus den verbleibenden 3 Spielern noch 2 ausgewählt. Nun haben wir aber A gegen B und B gegen A einzeln gezählt, deshalb teilen wir das Ergebnis noch durch 2. Es gibt also $\frac{\binom 52\cdot\binom 32}2=15$ verschiedene Spiele.
    Wir können auch so argumentieren: Ein Spieler setzt erstmal aus, und die anderen vier spielen alle möglichen Kombinationen. Das sind drei Stück, weil ein Spieler mit drei Partnern gegen das jeweils verbleibende Team antreten muss. Und wenn 5 Spieler ausgesetzt haben, gab es $5\cdot 3=15$ Spiele. Man sieht, dass es oft verschiedene Wege zum Ziel geben kann.
    Diese Aufgabe ist tatsächlich in der Sporthalle entstanden, da wir bei unserem wöchentlichen Badminton-Abend öfter mal am Ende noch zu fünft sind, aber trotzdem gerne Doppel spielen wollen.
12. Beim Brettspiel „Siedler von Catan“ würfelt man mit zwei normalen Würfeln.
    1. Wie viele Augenpaare sind möglich?
    2. Erstelle eine Tabelle, die zu jeder möglichen Augensumme notiert, wie häufig diese Augensumme möglich ist.