In diesem Kurs lernst du Grundlagen der Kombinatorik, wie das Zählprinzip und verschiedene Urnenmodelle (Ziehen mit/ohne Zurücklegen mit/ohne Reihenfolge) kennen.

Dadurch kannst du nach Abschluss des Kurses Fragen beantworten, die sich mit Anzahlen von Möglichkeiten beschäftigen wie z.B.:

• Wie viele Möglichkeiten gibt es, 3 Shirts, 2 Hosen und 3 Hüte zu kombinieren?

• Wie viele mögliche Zahlenkombinationen hat ein Zahlenschloss für Fahrräder?

• Wie viele Möglichkeiten gibt es, aus 100 Menschen zwei "Gewinner*innen" auszuwählen?

• ...

Li und Luca machen ein Praktikum bei "Spritzig und Witzig Eventmanagement".

Ihre Chefin, Frau Secco, ist gerade dabei eine große Benefizveranstaltung mit mehrgängigem Menü und Tombola zu planen und bittet die beiden dabei immer wieder um Unterstützung.

Li ist gerade dabei, die Einladung zu gestalten und rauft sich die Haare. Luca schaut vom Schreibtisch auf und zieht die Augenbraue nach oben.

Luca: "Was ist los?"

Li: "Ich weiß einfach nicht, wie ich den Text kürzen soll. Er ist zu lang. Aber ich möchte klar machen, dass wir ein großes kulinarisches Angebot haben"

Luca "Zeig mal her..." (Luca kommt zum anderen Computer und liest den Text laut vor) "Wählen Sie ein exquisites Menü aus 3 Vorspeisen, 4 Hauptspeisen und 3 Desserts und stellen Sie sich so ein einzigartiges Dinnererlebnis zusammen."

Es ist kurz Stille, beide überlegen. Nach einigem hin und her hat Li selbst eine Idee.

Li: "Wie wäre 'Wählen Sie Ihr 3-Gänge Menü aus einer von 36 Möglichkeiten!'"

Luca: "36? Wie kommst du denn jetzt auf 36?"

Li: "Das ist ganz einfach. Um alle möglichen Variationen zu erhalten, musst du einfach nur..."

Ja, was muss man einfach nur?

Überlege dir, wie du auf die 36 möglichen Menüabfolgen kommst.

Auflösung auf der nächsten Seite

Als Gast der Gala hat man die Möglichkeit, jede Vorspeise mit jeder Hauptspeise und jeder Nachspeise zu kombinieren. Für jede der drei Vorspeisen gibt es vier Hauptspeisen, also $4\cdot 3=124\backslash cdot\; 3=12$ Variationen. Jede dieser 12 Variationen kann mit einer der drei Nachspeisen kombiniert werden, also $12\cdot 3=3612\backslash cdot\; 3=36$.

Du musst also für jede Entscheidung, die du triffst, die Anzahl der Möglichkeiten mit denen der anderen Entscheidungen multiplizieren.

Die Zusagen sind eingetroffen und die Gästeliste ist komplett. Li und Luca planen die Sitzordnung.

Luca: "Diese Gruppe macht uns das Leben schwer. Es sind 10 Personen, aber die Tische haben immer nur 6 Plätze."

Li: "Nicht so schlimm, wir suchen uns einfach eine Aufteilung raus und der Rest kommt an den Nebentisch."

Luca: "Ja, da hast du recht. Aber wenn wir schon dabei sind. Wie viele Möglichkeiten gäbe es eigentlich einen Tisch mit 6 Stühlen mit einer Auswahl aus 10 Personen zu besetzen? Du weißt schon, wenn nicht nur wichtig ist, wer sitzt, sondern auch wo die Person sitzt. Das muss man doch berechnen können?"

Überlege dir, wie du die Anzahl der Möglichkeiten berechnen kannst, 6 nummerierte Stühle mit einer Auswahl aus 10 Personen zu besetzen, wenn die Anordnung der Personen am Tisch wichtig ist.

Als Gedankenexperiment: Wie sähe der Term aus, wenn wir 10 Personen zufällig auf 10 Plätze verteilen (es also genug Stühle für alle gibt und kein Stuhl leeer bleibt)?

Die erste Person hat 10 Möglichkeiten, die zweite 9, dann 8, dann 7, ... bis zur letzten Person, die nur noch einen freien Stuhl sieht. Mit dem Zählprinzip ergibt das $10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1=362880010\backslash cdot9\backslash cdot8\backslash cdot7\backslash cdot6\backslash cdot5\backslash cdot4\backslash cdot3\backslash cdot2\backslash cdot1=3628800$ Möglichkeiten. Für diesen langen Term gibt es aber auch eine abkürzende Schreibweise: Die Fakultät

Da jedes Zufallsexperiment als Urnenexperiment aufgefasst werden kann, kannst du das Experiment auch als "Ziehen aller Kugeln aus einer Urne ohne Zurücklegen und mit Beachtung der Reihenfolge" sehen.

Zurück zu Li und Luca: Auch ihr Problem kann durch eine Urne simuliert werden. Dabei wird aus einer Urne mit 10 Kugeln sechsmal gezogen und die Reihenfolge der erhaltenen Kugeln beachtet, sodass es wichtig ist, ob die Kugel "Paul Huber" als 1. oder 5. gezogen wird (=Paul Huber auf dem 1. oder 5. Stuhl am Tisch sitzt).

Der Unterschied zur Permutation ist, dass diesmal die Fakultät nicht bis zum Ende ausgerechnet wird:

10 Personen könnten auf dem 1. Platz sitzen, noch 9 auf dem 2., noch 8 auf dem 3., noch 7 auf dem 4., noch 6 auf dem 5. und noch 5 auf dem 6., also:

$10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5=15120010\backslash cdot9\backslash cdot8\backslash cdot7\backslash cdot6\backslash cdot5=151200$ Möglichkeiten 6 Menschen aus 10 auf 6 feste Plätze zuzuteilen.

Li und Luca bereiten die Tombola vor. Es sollen unter allen 250 Gästen 25 gleichwertige Wellnessgutscheine verlost werden, wobei jede Person nur einmal gewinnen kann.

Luca überlegt: "Wir könnten die Gewinnchancen auf das Schild der Tombola drucken: Mit 10% Wahrscheinlichkeit gewinnen Sie einen Wellnessgutschein! Das klingt doch nach guten Chancen."

Li schüttelt den Kopf: "Es klingt nach guten Chancen, weil es nicht der Wahrheit entspricht, die Wahrscheinlichkeit, dass genau ich das Gewinnlos bekomme, ist weitaus kleiner. Es gibt viel mehr Möglichkeiten als 250. Schau mal..."

Überlege bei dieser Aufgabe erstmal mit weitaus kleineren Zahlen: Wie viele Möglichkeiten gibt es zum Beispiel aus einer Gruppe aus 5 Personen 3 Personen auszuwählen, wenn die Reihenfolge egal ist?

Verwendet man die Formel für die Variation ohne Wiederholung und teilt dann das Ergebnis noch durch die Anzahl der möglichen Variationen in den kleinen Grüppchen, so kann die Frage damit beantwortet werden.

Da die Fragestellung "Wie viele Möglichkeiten gibt es, k aus n auszuwählen?" so häufig ist, gibt es für $\frac{n!}{(n-k)!\cdot k!}\backslash frac\{n!\}\{\backslash left(n-k\backslash right)!\backslash cdot\; k!\}$ eine Kurzschreibweise, den Binomialkoeffizienten

Als weiteres Gewinnspiel wurde den beiden aufgetragen, eine Art Bingo im Eingangsbereich zu organisieren, bei dem man mitspielen kann, um Kleinpreise von Sponsoren zu gewinnen. Sie probieren das Spiel selbst mit drei verschiedenfarbigen Kugeln aus.

Luca: "Wenn wir bei drei Kugeln bleiben und die Personen nur eine Farbe sagen müssen, ist die Gewinnwahrscheinlichkeit schon $\frac{1}{3}\backslash frac\{1\}\{3\}$. Das ist zu hoch."

Li: "Aber wenn wir mehr Kugeln verwenden, wirkt es vielleicht so, als wäre es fast unmöglich zu gewinnen, selbst wenn es bei 6 Kugeln immer noch nur 6 Möglichkeiten gäbe. Außerdem ist das Spiel dann nicht spannend. Einmal ziehen und es ist vorbei..."

Luca: "Ich habe eine Idee! Wie wäre es, wenn mehrmals mit Zurücklegen aus der Urne gezogen wird, zum Beispiel dreimal und die Gäste müssen genau die richtige Abfolge der Farben nennen, um zu gewinnen. Dann fiebern sie länger mit!",

Li: "Aber gibt es da nicht immer noch viel zu wenig Möglichkeiten? 9 Möglichkeiten sind mir ehrlich gesagt zu wenig."

Luca: "Es sind aber nicht nur 9 Möglichkeiten, sondern 27. Und das bei nur dreimal ziehen! Überleg mal, wenn wir vier Kugeln in der Urne hätten oder viermal ziehen."

Überlege dir, warum es 27 mögliche Ergebnisse gibt, wenn man aus einer Urne mit 3 verschiedenfarbigen Kugeln dreimal mit Zurücklegen zieht. Schätze zuerst, wie sich diese Zahl verändert, wenn du 4 Kugeln verwendest oder wenn du viermal statt dreimal ziehst und berechne dort ebenfalls die Anzahl der Möglichkeiten.

Da bei jedem Zug die gleiche Zahl an Kugeln zur Verfügung steht, ergibt sich die Anzahl der Möglichkeiten aus dem Zählprinzip mit $27=3\cdot 3\cdot 3=3^{3}27=3\backslash cdot3\backslash cdot3=3^3$.

(zu ergänzen, gehe direkt weiter zur Zusammenfassung)

In der Kombinatorik wird nach der Anzahl der Möglichkeiten bei der Durchführung eines Zufallsexperiments gefragt. Dabei ist es häufig von Nutzen, das Experiment auf ein Urnenexperiment zurückzuführen.

Die Anzahl der Möglichkeiten aus einer Urne mit/ohne Zurücklegen zu ziehen und dabei die Reihenfolge der gezogenen Kugeln zu beachten/nicht zu beachten lässt sich jeweils berechnen durch:

Wobei $\left(\genfrac{}{}{0px}{}{n_{}}{k}\right)=\frac{n!}{(n-k)!k!}\backslash binom\{n\_\{\; \}\}\{k\}=\backslash frac\{n!\}\{\backslash left(n-k\backslash right)!k!\}$ der Binomialkoeffizient ist.