Mathe-Artikel #025: Der Kombinatorik-Algorithmus

Question

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.

Comments

Pah, das habe ich vor Jahren schon entwickelt! :-)

https://www.mathelounge.de/532412/permutation-kombination-variation-…

Also in einer etwas weniger ausführlichen Form :D

---

Soso ... warum hast du da keinen Artikel draus gemacht? :)

---

toller artikel, tolles video, tolle idee!

---

Hallo André,

Gleich vorneweg; ich bin in Stochastik nicht so bewandert. Zu meiner Zeit stand das weder an der Schule noch an der Uni auf dem Lehrplan. (was ich bedauere!)

Du beginnst den Algorithmus mit:

1. Sind alle $n$ Elemente der Grundmenge relevant?

Oje - was ist ein Element? und was ist die Grundmenge? Na ja - ich stell mich jetzt ein wenig dümmer als ich bin, Kann man ja bei Wikipedia nachlesen. Aber damit ich es besser verstehe, bin ich gleich zum Beispiel über gegangen:

Am Drive-In eines McDonalds stehen 8 unterscheidbare Autos. Wie viele unterschiedliche Warteschlangen mit 8 Autos sind hier möglich?

hätte ich jetzt gewusst: stellt man die Autos in beliebiger Reihenfolge in die Schlange hat man für den ersten Wagen 8 Möglichkeiten, für den zweiten 7, usw. - macht $8!$.

Sind alle n Elemente (Autos) der Grundmenge (die 8 Autos am Drive-In) relevant?

Ops! - ich hätte jetzt intuitiv angenommen, dass eine mögliche Warteschlange ein Element ist. Jetzt erklär' mir doch mal, woher man das wissen, kann, dass ein Auto ein Element ist?

Und die Grundmenge sind die 8 Autos am Drive-In - hätte ich jetzt nicht gedacht! Wie kann man sich das als Stochastik-Laie vorstellen?

Gruß Werner