Kombinatorik

Verstehen

Was zählt die Kombinatorik?

Kombinatorik untersucht, wie viele Möglichkeiten eine Auswahl oder Anordnung hat. Kleine Beispiele kannst du vollständig auflisten. Bei großen Aufgaben ersetzen Zählregeln die lange Liste.

Aus A, B und C sollen zwei verschiedene Buchstaben ausgewählt werden. Wenn die Reihenfolge zählt, gibt es sechs Möglichkeiten:

Wenn nur die ausgewählten Buchstaben zählen, sind AB und BA dieselbe Auswahl. Dann bleiben nur drei:

Mehrere Entscheidungsschritte multiplizieren

Für ein Outfit stehen drei unterschiedliche Oberteile und zwei unterschiedliche Hosen zur Auswahl. Jedes Oberteil lässt sich mit jeder Hose kombinieren:

Die Produktregel gilt, wenn auf jede Möglichkeit eines Schritts dieselbe Anzahl von Fortsetzungen folgt. Die Anzahlen dürfen von Schritt zu Schritt verschieden sein. Bei drei Plätzen ohne Wiederholung können es zum Beispiel zuerst fünf, dann vier und zuletzt drei Optionen sein.

Bei getrennten Fällen, die sich nicht überschneiden, addierst du dagegen. Gibt es wahlweise drei verschiedene Kuchen oder zwei verschiedene Eisbecher und du nimmst genau eine Nachspeise, rechnest du:

Die Anzahlen deiner Entscheidungsschritte multiplizieren→

Reihenfolge wichtig, Wiederholung erlaubt

Ein vierstelliger Code verwendet die Ziffern 0 bis 9. Jede Ziffer darf mehrfach vorkommen, auch 0 am Anfang ist erlaubt. Für jede der vier Stellen gibt es zehn Möglichkeiten:

Allgemein gibt es bei n Möglichkeiten pro Stelle und k Stellen:

n^k

Der Code 0123 ist etwas anderes als 3210. Erlaubt die Aufgabe keine führende Null, ändert sich die erste Stelle:

Reihenfolge wichtig, Wiederholung verboten

Fünf Personen bewerben sich für drei verschiedene Ämter: Vorsitz, Stellvertretung und Kasse. Eine Person darf nur ein Amt übernehmen. Für das erste Amt gibt es fünf, für das zweite vier und für das dritte drei Möglichkeiten:

Wer welches Amt bekommt, zählt. Aus n verschiedenen Objekten werden k ohne Wiederholung in eine Reihenfolge gebracht:

n · (n − 1) · … · (n − k + 1) = n!(n − k)!

Dabei gilt 0 ≤ k ≤ n. Die Fakultät n! multipliziert alle ganzen Zahlen von 1 bis n. Zum Beispiel ist 5! = 120; per Definition gilt 0! = 1.

Alle Objekte anordnen: Permutationen

Wenn alle n verschiedenen Objekte angeordnet werden, ist k = n. Für fünf unterschiedliche Bücher in einer Reihe gibt es:

Das heißt Permutation. Die Plätze sind hier unterscheidbar und bilden eine Reihe. Kreisförmige Sitzordnungen können anders gezählt werden, wenn Drehungen als dieselbe Anordnung gelten.

Gleiche Zeichen: Bei den Buchstaben A, A, B sind die beiden A nicht unterscheidbar. Die sechs Anordnungen mit gedanklich nummerierten A würden jede sichtbare Anordnung doppelt zählen:

Bei mehreren Gruppen gleicher Zeichen teilst du n! durch die Fakultäten ihrer jeweiligen Häufigkeiten. Für AABB ergibt sich:

Reihenfolge unwichtig, Wiederholung verboten

Aus fünf Personen wird ein Team aus drei Personen gewählt. Alle drei Teammitglieder haben dieselbe Rolle. Das Team aus Anna, Ben und Cem bleibt dasselbe, egal in welcher Reihenfolge die Namen genannt werden.

Allgemein lautet der Binomialkoeffizient, gesprochen „n über k“:

C(n, k) = n!k! · (n − k)!

Am Rechner findest du ihn oft als nCr. C(5, 3) = C(5, 2): Drei Personen auszuwählen ist gleichbedeutend damit, die zwei nicht gewählten festzulegen.

Deine Teamauswahl ohne Reihenfolge berechnen→

Reihenfolge unwichtig, Wiederholung erlaubt

Du wählst drei Kugeln Eis aus vier Sorten. Sorten dürfen mehrfach vorkommen, und die Reihenfolge der Kugeln wird nicht unterschieden. Drei Kugeln Schokolade zählen als eine Auswahl; zweimal Schokolade und einmal Vanille ebenfalls.

Für k Auswahlen aus n Sorten lautet die Anzahl:

C(n + k − 1, k)

Die Idee dahinter: Drei Markierungen stehen für die Kugeln, drei Trennzeichen teilen sie auf die vier Sorten auf. Unter insgesamt sechs Positionen wählst du die drei Positionen der Kugel-Markierungen. So wird jede Sortenverteilung genau einmal gezählt.

Eine Auswahl mit unbegrenzter Wiederholung untersuchen→

Die vier Auswahlmodelle vergleichen

n ist die Anzahl verfügbarer unterschiedlicher Objekte oder Sorten, k die Anzahl der ausgewählten Plätze oder Objekte. Prüfe zusätzlich besondere Bedingungen, etwa eine verbotene Null am Anfang oder eine vorgeschriebene Person.

Vom Zählen zur Wahrscheinlichkeit

Eine Urne enthält fünf rote und drei blaue, einzeln unterscheidbare Kugeln. Es werden zwei Kugeln zufällig ohne Zurücklegen gezogen. Wir betrachten ungeordnete Kugelpaare. Alle C(8, 2) = 28 Paare sind gleich wahrscheinlich.

Das Verhältnis „günstige durch mögliche Fälle“ darfst du nur bei gleich wahrscheinlichen Fällen verwenden. Zähle im Zähler und Nenner nach demselben Modell: hier beide Male ungeordnet.