Kombinatorik – Variation/Kombination

• Permutation, Kombination, Variation
• mit/ohne Reihenfolge, Ziehen mit Zurücklegen
• Auswahl der richtigen Formel
• Korrekte Anwendung der Formel – Beispiele

Allgemeine Informationen

Kombinatorik wird häufig als die Kunst des Zählens bezeichnet und beschäftigt sich mit der Anzahl der Möglichkeiten, wie man Elemente aus einer gegebenen Grundmenge auswählen oder anordnen kann. Sie ist eine wichtige Grundlage für viele Bereiche der Mathematik, Informatik und Statistik.

Begrifflichkeiten – kurze Übersicht:

Eine Permutation ist eine Anordnung aller Elemente einer Grundmenge.

Eine Variation ist eine Auswahl von Elementen, bei der die Reihenfolge berücksichtigt wird und eine Kombination ist eine Auswahl von Elementen ohne Berücksichtigung der Reihenfolge. 

Formel wählen

Wir sehen uns jetzt eine Übersicht an, wie ihr am besten unterscheiden könnt, welche Formel in eurem Kombinatorikproblem verwendet werden soll.

In erster Linie müsst ihr euch einmal überlegen, ob in eurer Aufgabe alle Elemente oder nur eine Teilmenge betrachtet werden soll. Wenn nämlich alle Elemente betrachtet werden sollen, ihr somit keine Auswahl trefft, dann handelt es sich um Permutation. Wenn ihr eine Auswahl trefft und somit nur eine Teilmenge betrachtet, dann liegt Variation bzw. Kombination vor.

Bei Variation und Kombination überlegt ihr euch als Nächstes, ob die Reihenfolge eine Rolle spielt oder nicht.

Wenn die Reihenfolge der Elemente wichtig ist, handelt es sich um eine Variation und wenn diese nicht relevant ist, um eine Kombination.

Zum Schluss müsst ihr noch unterscheiden, ob es sich um Ziehen mit Zurücklegen handelt. Ihr könnt auch stattdessen mit bzw. ohne Wiederholung sagen.

Schlussendlich kommt ihr dann bei einer von 6 Formeln zur Berechnung eurer Möglichkeiten an.

Beispiel zum Erkennen von Permutation, Variation, Kombination

Wir sehen uns nun anhand eines kurzen Beispiels an, wie ihr die soeben erwähnten Begriffe noch besser unterscheiden könnt. Gehen wir davon aus, wir haben 10 Kugeln in einer Urne mit den Zahlen von 1 bis 10.

Rechenbeispiele

In diesem Beitrag werden wir uns auf Variation und Kombination fokussieren. Für die Permutation erwartet euch ein eigener, detaillierter Beitrag.

Beispiel 1

Zuerst wollen wir die Möglichkeiten für ein 5-stelliges Passwort bestimmen. Wir dürfen für unser Passwort aus 26 Buchstaben und den Zahlen von 0 bis 9 wählen. Wie viele Möglichkeiten gibt es also für 5-stellige Passwörter?

Wir wollen ein Passwort mit 5 Zeichen bestimmen. Somit verwenden wir nicht alle möglichen Zeichen, sondern nur eine Teilmenge. Bei einem Passwort macht es einen Unterschied, ob ich 12345 oder 54321 eingebe. D.h. die Reihenfolge ist wichtig. Außerdem darf ich bei einem Passwort denselben Buchstaben auch mehrmals verwenden, was Ziehen mit Zurücklegen entspricht.

Die Formel, die wir hier also nehmen müssen, ist \(n^k\).

n steht in der Formel für unsere Grundmenge und k steht für die Auswahl, die wir treffen. Wir haben 26 Buchstaben und 10 Ziffern (0 bis 9). Das heißt, insgesamt dürfen wir aus 36 Zeichen wählen, was unsere Grundmenge n darstellt. Wir wollen ein 5-stelliges Passwort, daher ist k gleich 5.

$$n = 36 \quad k = 5$$

Das heißt, wir setzen diese Werte in die Formel ein.

$$36^5 = 60466176$$

und haben bestimmt, dass es etwas mehr als 60 Millionen Möglichkeiten gibt, ein 5-stelliges Passwort zu erstellen.

Beispiel 2

Nun zum nächsten Beispiel. Wie viele mögliche Lottozahlen gibt es beim deutschen Lotto 6 aus 49?

Beim Lotto werden 6 Kugeln aus den 49 gezogen – somit treffen wir erneut eine Auswahl und haben eine Teilmenge. Es handelt sich erneut nicht um Permutation. Beim Lotto geht es nur darum, die 6 Richtigen zu ziehen. Welche Kugel dabei zuerst gezogen wurde, ist egal. Somit ist die Reihenfolge nicht von Bedeutung. Zudem können beim Lotto gezogene Nummern nicht noch einmal gezogen werden. Es handelt sich also um eine Ziehung ohne Zurücklegen.

Die richtige Formel für diesen Fall ist also \({n\choose k} = \frac{n!}{(n-k)! \cdot k!}\) besser bekannt als Binomialkoeffizient.

Wir haben 49 Kugeln als Grundmenge (= n) und wollen 6 Kugeln (= k) ziehen.

$${n \choose k} = {49 \choose 6} = \frac{49!}{(49-6)! \cdot 6!} = \frac{49!}{43!\cdot 6!}= 13983816$$

Es ergeben sich etwas weniger als 14 Millionen mögliche Lottozahlen.

Ihr könnt den Binomialkoeffizienten ganz einfach mit dem Taschenrechner mit der Taste nCr berechnen. Bei den meisten Taschenrechnern müsst ihr dafür einfach 49 nCr 6 eingeben.

Beispiel 3

Als Nächstes sehen wir uns das Finale eines 100 m Sprints an. Dort nehmen normalerweise 8 Personen teil und die ersten 3 erhalten Medaillen. Wie viele verschiedene Podeste könnte es geben?

Nur 3 der 8 Läufer werden prämiert, somit haben wir erneut eine Auswahl vorliegen. Es ist natürlich wichtig, wer wo am Podest steht, also wer den 1., 2. und 3. Platz belegt. Die Reihenfolge muss beachtet werden. Eine Person kann natürlich nicht gleichzeitig den 1. und den 2. Platz belegen, deswegen Ziehen ohne Zurücklegen.

Unsere zu verwendende Formel ist somit \(\frac{n!}{(n-k)!}\)

n! (sprich n Rufzeichen) heißt n-Fakultät oder n-faktorielle und es werden alle natürlichen Zahlen von n bis 1 miteinander multipliziert.

$$n! = n \cdot (n-1) \cdot (n-2) \cdot …\cdot 1$$

Setzen wir die gegebenen Zahlen jetzt also in die Formel ein:

$$\frac{n!}{(n-k)!} = \frac{8!}{(8-3)!} = \frac{8!}{5!} = \frac{8\cdot 7\cdot 6\cdot 5 \cdot 4\cdot 3\cdot 2\cdot 1}{5 \cdot 4\cdot 3\cdot 2\cdot 1} \quad = 8\cdot 7\cdot 6 = 336$$

Wir erhalten 336 verschiedene Möglichkeiten, wie sich das Podest zusammensetzen kann.

Als kleine Info noch, mit der gekürzten Formel \(n \cdot (n-1) \cdot … \cdot (n-k+1)\) wärt ihr ebenfalls auf dasselbe gekommen.

Beispiel 4

Als letztes Beispiel werden im Büro der Statistikquelle Weihnachtskekse gebacken. Es stehen 6 verschiedene Zutaten zur Verfügung, wovon immer 3 Zutaten verwendet werden sollen, um die Keksrezepte zu variieren. Welche Zutat zuerst verwendet wird, spielt keine Rolle. Wie viele verschiedene Auswahlmöglichkeiten gibt es, wenn bereits verwendete Zutaten wieder verwendet werden dürfen?

Wir verwenden nur 3 Zutaten, treffen also wieder eine Auswahl. Es ist egal, welche Zutat wir zuerst verwenden, also ohne Reihenfolge und wir dürfen auch eine Zutat mehrmals verwenden, also mit Zurücklegen.

Die Formel, die wir somit verwenden, ist \({n+k-1 \choose k}\).

Wir haben insgesamt 6 mögliche Zutaten (= n), von denen wir 3 wählen (= k).

$${n+k-1 \choose k} = {6+3-1 \choose 3} = {8 \choose 3} = 56 $$

Wir finden heraus, dass es 56 mögliche Kombinationen für unsere Weihnachtskekse gibt.