Grundlagen der Statistik: Kombinatorik – Variationen und Kombinationen

Um Wahrscheinlichkeiten auf Basis der klassischen Wahrscheinlichkeitsdefinition nach Pierre Simon de Laplace (Anzahl der für das gesuchte Ereignis relevanten Ergebnisse dividiert durch die Anzahl aller möglichen Ergebnisse) berechnen zu können, muss in vielen Fällen erst ermittelt werden, wie viele mögliche Ergebnisse eines Zufallsvorgangs überhaupt existieren. Um die Wahrscheinlichkeit dafür zu berechnen, eine 4-stellige PIN im ersten Versuch zu knacken, muss man beispielsweise wissen, wie viele Möglichkeiten es eigentlich gibt, vier Ziffern aus den Ziffern von 0 bis 9 zu einer 4-stelligen PIN zu kombinieren. Hierfür bedienen wir uns der sogenannten Kombinatorik, die wiederum vier “Basisfälle” kennt: die Variation mit Zurücklegen, die Variation ohne Zurücklegen, die Kombination mit Zurücklegen und die Kombination ohne Zurücklegen. In diesem Blogpost soll kurz dargestellt werden, worin sich diese vier Fälle unterscheiden.

Variation ohne Zurücklegen: Eine Variation ohne Zurücklegen liegt vor, wenn die Reihenfolge der k Elemente, die aus n Elementen gezogen werden, eine Rolle spielt und die einzelnen Elemente sich nicht wiederholen können, d.h. nach dem “Ziehen” nicht mehr in die “Wahlurne” zurückgelegt werden. Die Beachtung der Reihenfolge spielt etwa bei PINs eine große Rolle – werden die korrekten Zahlen in der falschen Reihenfolge eingegeben, erfolgt kein Zugriff. Bei Lottozahlen ist es dagegen anders – hier kommt es nur darauf an, die korrekten Zahlen angekreuzt zu haben, nicht aber auf die Reihenfolge, in der diese gezogen werden. Ein Sonderfall der Variation ohne Zurücklegen ist die Permutation, bei der alle Elemente gezogen werden (d.h. k = n).

(im Sonderfall der Permutation gilt: n!)

Variation mit Zurücklegen: Eine Variation mit Zurücklegen liegt vor, wenn die Reihenfolge der k Elemente, die aus n Elementen gezogen werden, eine Rolle spielt und die einzelnen Elemente sich beliebig wiederholen können, d.h. nach dem “Ziehen” immer wieder in die “Wahlurne” zurückgelegt werden. Ein klassisches Beispiel für eine Variation mit Zurücklegen sind Passwörter und PINs, da hier sowohl die Reihenfolge der Anordnung von Zeichen und Ziffern eine Rolle spielt als auch (zumindest in den allermeisten Fällen) Zeichen und Ziffern beliebig oft im gleichen Passwort bzw. in der gleichen PIN vorkommen können.

Kombination ohne Zurücklegen: Eine Kombination ohne Zurücklegen liegt vor, wenn die Reihenfolge der k Elemente, die aus n Elementen gezogen werden, keine Rolle spielt und die einzelnen Elemente sich nicht wiederholen können, d.h. nach dem “Ziehen” nicht wieder in die “Wahlurne” zurückgelegt werden. Ein eingängiges Beispiel für eine Kombination ohne Zurücklegen ist die Ziehung der Lottozahlen – hier spielt die Reihenfolge, in der die Zahlen gezogen bzw. angekreuzt werden, für den Gewinn keine Rolle – und die einmal gezogenen Kugeln werden nicht wieder in die Trommel zurückgelegt bzw. es können auf dem Lottoschein keine Zahlen mehrfach angekreuzt werden.

Kombination mit Zurücklegen: Eine Kombination mit Zurücklegen liegt vor, wenn die Reihenfolge der k Elemente, die aus n Elementen gezogen werden, keine Rolle spielt und die einzelnen Elemente sich beliebig wiederholen können, d.h. nach dem “Ziehen” immer wieder in die “Wahlurne” zurückgelegt werden. Als Beispiel für eine Kombination mit Zurücklegen wird in Lehrbüchern häufig ein recht generischer “Urnenfall” verwendet: Aus einer Urne mit n schwarzen und weißen Kugeln werden zufällig k Kugeln gezogen und wieder zurückgelegt, wobei als Ergebnis die absolute Zahl gezogener schwarzer und weißer Kugeln gilt – natürlich ohne Beachtung der Reihenfolge.

Beispielrechnungen

Ein Koffer ist mit einem dreistelligen Zahlenschloss gesichert, wobei jede Stelle auf die Ziffern 0 bis 9 eingestellt werden kann und sich die Ziffern wiederholen dürfen. Wie viele potentiell korrekte Ziffernkombinationen gibt es, wenn…

a) …über die korrekte Ziffernkombination nichts bekannt ist?
b) …bekannt ist, dass die korrekte Ziffernkombination nur aus Ziffern größer als 5 besteht?

a) Anzahl der Kombinationen bei fehlenden Informationen

Hier handelt sich um eine Variation (bei einer PIN spielt die Reihenfolge der Ziffern eine Rolle) mit Zurücklegen (alle Ziffern können mehrfach auftreten). Wenn über die korrekte Kombination nichts bekannt ist, kommen für jede Stelle der PIN alle 10 Ziffern in Frage, daher gilt:

10 * 10 * 10 = 1000

b) Anzahl der Kombinationen bei Ziffern > 5

Wenn bekannt ist, dass die Kombination nur aus Ziffern größer 5 (6, 7, 8, 9) besteht, berechnet sich die Zahl der möglichen Kombinationen wie folgt:

4 * 4 * 4 = 64

Übungsaufgabe

Eine Festplatte wurde mit einer Software verschlüsselt, die ein 5-stelliges Passwort verlangt, das sich aus den 10 Ziffern von 0 bis 9 sowie den 26 Buchstaben von A bis Z zusammensetzen kann, wobei alle Ziffern und Buchstaben auch mehrfach auftreten können. Die Besonderheit des Systems besteht darin, dass das Passwort jeweils abwechselnd aus Buchstaben und Ziffern – beginnend mit einer Ziffer – zusammengesetzt werden muss.

Wie viele mögliche Passwörter gibt es?

Zur Anzeige der Lösungen bitte hier klicken.

Die hier vorgestellten Inhalte und Aufgaben sind Teil der Vorlesung “Grundlagen der Statistik” im berufsbegleitenden Bachelor-Studiengang Betriebswirtschaftslehre an der Hochschule Harz. Eine vollständige Übersicht aller Inhalte dieser Vorlesung im Wissenschafts-Thurm findet sich hier: Grundlagen der Statistik.