1. Einführung
Vielen Schülern und Studenten fällt es schwer zu entscheiden, wann man welche Formel zum Berechnen der Anzahl an Möglichkeiten für unterschiedliche Problemstellungen einsetzt. Mithilfe eines einfachen Algorithmus lässt sich jedoch entscheiden, welche Formel im Kontext verwendet werden kann bzw. muss. Der Algorithmus erhält als Eingabe eine Menge an Antworten auf Fragen, die im Kontext eines bestimmten Problems gegeben werden und liefert als Ergebnis eine Formel, mit der die Berechnung der Anzahl an Möglichkeiten möglich ist.
2. Der Algorithmus
1. Sind alle \(n\) Elemente der Grundmenge relevant?
--- Falls ja: Es liegt eine Permutation vor. Mache mit Schritt 2 weiter.
--- Falls nein: Mache mit Schritt 3 weiter.
2. Sind alle \(n\) Elemente voneinander unterscheidbar?
--- Falls ja: Verwende die Formel \(n!\) ("11")
--- Falls nein: Verwende die Formel \(\frac{n!}{k!}\), wobei \(k\) die Anzahl der nicht unterscheidbaren Objekte ist. ("10")
3. Spielt die Reihenfolge eine Rolle?
--- Falls ja: Es liegt eine Variation vor. Mache weiter mit Schritt 4.
--- Falls nein: Es liegt eine Kombination vor. Mache weiter mit Schritt 5.
4. Sind alle Elemente voneinander unterscheidbar (im Urnenkontext: "Ziehen ohne Zurücklegen")?
--- Falls ja: Verwende die Formel \(\frac{n!}{(n-k)!}\), wobei \(k\) die Anzahl der relevanten Elemente aus der Grundmenge ist. ("011")
--- Falls nein: Verwende die Formel \(n^k\), wobei \(k\) die Anzahl der relevanten Elemente aus der Grundmenge ist. ("010")
5. Sind alle Elemente voneinander unterscheidbar (im Urnenkontext: "Ziehen ohne Zurücklegen")?
--- Falls ja: Verwende die Formel \(\binom{n}{k}\) oder \(\frac{n!}{k!\cdot (n-k)!}\), wobei \(k\) die Anzahl der relevanten Elemente aus der Grundmenge ist. ("001")
--- Falls nein: Verwende die Formel \(\binom{n+k-1}{k}\) oder \(\frac{(n+k-1)!}{k!\cdot (n-1)!}\), wobei \(k\) die Anzahl der relevanten Elemente aus der Grundmenge ist. ("000")
3. Beispiele
Um die Eingabe, die der Algorithmus erhält, zu konkretisieren, kannst du einen Vektor aus Einsen und Nullen übergeben. Einsen stehen dabei für "ja" und Nullen für "nein". Wenn du also \((0,0,1)\) eingibst, bedeutet das so viel wie \((\text{nein}, \text{nein}, \text{ja})\). Im Kontext des Algorithmus bedeutet das, dass nicht alle \(n\) Elemente einer Grundmenge relevant sind, die Reihenfolge keine Rolle spielt und alle Elemente voneinander unterscheidbar sind. Der Algorithmus liefert für diesen Fall also die Formel \(\binom{n}{k}\) zurück.
Nach so vielen abstrakten Formulierungen bedarf es nun einiger Beispiele:
- Am Drive-In eines McDonalds stehen \(8\) unterscheidbare Autos. Wie viele unterschiedliche Warteschlangen mit \(8\) Autos sind hier möglich?
--- Sind alle \(n\) Elemente (Autos) der Grundmenge (die \(8\) Autos am Drive-In) relevant? \(\Longrightarrow\) Ja (1), es liegt also eine Permutation vor. Mache mit Schritt 2 weiter.
--- Sind alle \(n\) Elemente (Autos) voneinander unterscheidbar? \(\Longrightarrow\) Ja (1). Verwende also die Formel \(n!\) mit \(n=8\), um die Anzahl der möglichen Warteschlangen zu berechnen. Es gibt \(8!\) Möglichkeiten für die Anordnung der \(8\) Autos in der Warteschlange vom Drive-In. Der Algorithmus erhält die Eingabe "11" und liefert als Formel \(n!\).
- Aus den Ziffern \(0\) bis \(9\) soll ein fünfstelliges Zahlenpasswort erstellt werden. Wie viele solcher Passwörter gibt es? Stelle dir für die Lösung vor, dass du zum Erstellen deines Passworts aus einer Urne mit \(n=10\) Kugeln, die mit den Ziffern \(0\) bis \(9\) beschriftet sind, \(k=5\) mit Zurücklegen auswählst.
--- Sind alle \(n\) Elemente der Grundmenge (Ziffern) relevant? \(\Longrightarrow\) Nein (0), denn das Passwort könnte z. B. nur aus Einsen bestehen. Mache also mit Schritt 3 weiter.
--- Spielt die Reihenfolge eine Rolle? \(\Longrightarrow\) Ja (1), denn "12345" ist ein anderes Passwort als "54321". Es liegt also eine Variation vor. Mache mit Schritt 4 weiter.
--- Wird ohne Zurücklegen gezogen? \(\Longrightarrow\) Nein (0), denn das Passwort könnte z. B. "11111" lauten, d. h. eine Ziffer kann mehrfach verwendet werden. Verwende also die Formel \(n^k\) mit \(n=10\) und \(k=5\).
--- Es gibt \(10^5\) Möglichkeiten aus den Ziffern \(0\) bis \(9\) einen fünfstelligen Code zu erzeugen. Der Algorithmus erhält die Eingabe "010" und liefert als Formel \(n^k\).
- Wie viele Möglichkeiten gibt es, beim Lotto \(6\) aus \(49\) Zahlen (von \(1\) bis \(49\)) zu ziehen? Stelle dir für die Lösung vor, dass du die \(k=6\) Kugeln aus einer Urne mit \(n=49\) Kugeln, die mit den Zahlen \(1\) bis \(49\) beschriftet sind, ohne Zurücklegen auswählst.
--- Sind alle \(n\) Elemente der Grundmenge (\(49\) Ziffern) relevant? \(\Longrightarrow\) Nein (0), denn es könnten z. B. die Kugeln \(12\), \(15\), \(29\), \(36\), \(42\) und \(47\) gezogen werden und diese Kugelauswahl enthält z. B. nicht die \(49\). Mache also mit Schritt 3 weiter.
--- Spielt die Reihenfolge eine Rolle? \(\Longrightarrow\) Nein (0), denn es kommt beim Lotto nur auf die Kugeln selbst und nicht auf die Ziehungsreihenfolge an. Es liegt also eine Kombination vor. Mache mit Schritt 5 weiter.
--- Wird ohne Zurücklegen gezogen? \(\Longrightarrow\) Ja (1), denn beim Lotto werden die gezogenen Kugeln nicht wieder in die Urne zurückgelegt. Verwende also die Formel \(\binom{49}{6}\) mit \(n=49\) und \(k=6\).
--- Es gibt \(\binom{49}{6}\) Möglichkeiten beim Lotto aus \(49\) Zahlen \(6\) zu ziehen. Der Algorithmus erhält die Eingabe "001" und liefert als Formel \(\binom{n}{k}\).
Das Mitglied hat durch den Artikel 50 Bonuspunkte erhalten. Schreib auch du einen Artikel.
