Theorie:
Beginnen wir mit den Variationen. Zur Erinnerung:
Eine Variation ist eine Ziehung, bei der die Reihenfolge der gezogenen Elemente beachtet wird.
Die Anzahl der Variationen mit \(k\) Elementen aus einer Grundmenge \(n\) ist also die Anzahl der unterschiedlichen möglichen Ergebnisse einer \(k\)-maligen Ziehung aus einer Grundmenge von \(n\) Elementen.
Dabei müssen wir zunächst unterscheiden, ob die gezogenen Elemente "zurückgelegt" werden (und daher bei der nächsten der \(k\) Ziehungen wieder auftreten kann), oder ob jedes Ziehungsergebnis nur maximal ein Mal auftreten kann.
Variation mit Wiederholung
Die Variation mit Wiederholungist vermutlich die einfachste Anwendung der Kombinatorik. Typische Anwendungsbeispiele sind etwa Zahlen- oder Buchstabenkombinationen.
Gehen wir von einer allgemeinen Grundmenge mit \(n\) Elementen aus, aus der \(k\) Mal gezogen wird.
- Bei der ersten Ziehung gibt es \(n\) unterschiedliche Ergebnismöglichkeiten (jedes Element der Grundmenge kann gezogen werden).
- Bei der zweiten Ziehung kann - unabhängig vom Ergebnis der ersten - erneut jedes der \(n\) Elemente gezogen werden. Für die ersten beiden Ziehungen zusammen gibt es also \(n\cdot n = n^2\) unterschiedliche mögliche Ergebnisse.
- Ebenso verhält es sich bei der dritten und allen weiteren Ziehungen: Jedes Mal gibt es \(n\) verschiedene mögliche Ergebnisse, die der Anzahl der möglichen Gesamtergebnisse einen Faktor \(n\) hinzufügen.
Wir erhalten also für \(k\) Ziehungen \(n^k\) unterschiedliche mögliche Ergebnisse.
Beispiel:
Wie viele unterschiedliche Zahlenkombinationen können bei einem Zahlenschloss mit sechs Stellen (wobei jede Stelle alle Ziffern von \(0\) bis \(9\) annehmen kann) eingestellt werden?
Hier ist \(n = 10\) (da bei jeder Stelle zehn verschiedene Werte möglich sind) und \(k = 4\) (da vier Mal je ein Einzelwert gewählt wird).
Wir erhalten also
\(10^4 = 10\ 000\)
unterschiedliche Möglichkeiten.
Hier ist \(n = 10\) (da bei jeder Stelle zehn verschiedene Werte möglich sind) und \(k = 4\) (da vier Mal je ein Einzelwert gewählt wird).
Wir erhalten also
\(10^4 = 10\ 000\)
unterschiedliche Möglichkeiten.
Variationen ohne Wiederholung
Gehen wir wieder Schritt für Schritt vor.
- Bei der ersten Ziehung gibt es \(n\) verschiedene mögliche Ergebnisse.
- Bei der zweiten Ziehung können alle \(n\) Elemente der Grundmenge gezogen werden, außer jenes, das bei der ersten Ziehung gezogen wurde. Es gibt also nur noch \((n-1)\) Möglichkeiten. Für die ersten beiden Ziehungen zusammen ergibt das \(n\cdot (n-1)\) Möglichkeiten.
- Für die dritte Ziehung gibt es wieder um eine Möglichkeit weniger, nämlich \((n-2)\). Insgesamt macht das \(n\cdot (n-1)\cdot (n-2)\) Ergebnisse für die ersten drei Ziehungen.
- Für die \(k\)-te Ziehung schließlich stehen nur noch \(n-(k-1) = n - k + 1\) Elemente der Grundmenge zur Auswahl. Insgesamt erhalten wir also
\(n\cdot (n-1)\cdot (n-2)\cdot ... \cdot (n-(k-2)) \cdot (n- (k-1))\)
Möglichkeiten.
Um dieses Ergebnis übersichtlicher anschreiben (und auch einfacher in den Taschenrechner eingeben) zu können, wurde für solche Produkte aufeinanderfolgender ganzer Zahlen eine neue Rechenoperation eingeführt: die Fakultät. Wir schreiben dafür nach eine Zahl ein Rufzeichen und meinen damit das Produkt aller natürlichen Zahlen bis zu dieser Zahl.
Die Fakultät wird mit einem Ausrufezeichen nach einer Zahl dargestellt und ist definiert als
\(n! = n \cdot (n-1)\cdot (n-2)\cdot ... \cdot 3\cdot 2\cdot 1\).
Wir sprechen für \(n!\) 'n faktorielle' oder 'n Fakultät'.
Dabei gilt
\(1! = 0! = 1\).
\(n! = n \cdot (n-1)\cdot (n-2)\cdot ... \cdot 3\cdot 2\cdot 1\).
Wir sprechen für \(n!\) 'n faktorielle' oder 'n Fakultät'.
Dabei gilt
\(1! = 0! = 1\).
Da Taschenrechner Fakultäten automatisch berechnen können (die entsprechende Taste ist meist mit \(x!\) beschriftet) müssen wir diese langen Produkte nicht einzeln ausrechnen.
Mithilfe der Fakultät können wir unser Ergebnis einfacher schreiben, indem wir es als Bruch anschreiben und mit \((n-k)!\) erweitern:
\(n\cdot (n-1)\cdot (n-2)\cdot ... \cdot (n-(k-2)) \cdot (n- (k-1)) \cdot \frac{(n-k)!}{(n-k)!} = \frac{n\cdot (n-1)\cdot (n-2)\cdot ... \cdot (n-(k-2)) \cdot (n- (k-1)) \cdot (n-k) \cdot (n-k-1) \cdot ... \cdot 3\cdot 2\cdot 1}{(n-k)!} = \frac{n!}{(n-k)!}\)
Es gibt also \(\frac{n!}{(n-k)!}\) unterschiedliche Variationen ohne Wiederholung.
Beispiel:
Bei einem Kartenspiel wird aus einem Stapel von \(52\) Karten an vier Personen je eine Karte ausgeteilt. Wie viele verschiedene Situationen sind hierbei möglich?
Die Grundmenge besteht aus \(n = 52\) Karten, wovon \(k = 4\) gezogen (ausgeteilt) werden. Da es einen Unterschied macht, wer der vier Spielenden welche Karte bekommt, handelt es sich um eine Variation (und, da jede Karte nur ein Mal vorhanden ist, um eine Variation ohne Wiederholung).
Wir setzen also in unsere Formel ein und erhalten
\(\frac{n!}{(n-k)!} = \frac{52!}{48!} = \frac{8,06581...\cdot 10^{67}}{1,24139...\cdot 10^{61}} = 6\ 497\ 400\)
unterschiedliche Möglichkeiten.
Die Grundmenge besteht aus \(n = 52\) Karten, wovon \(k = 4\) gezogen (ausgeteilt) werden. Da es einen Unterschied macht, wer der vier Spielenden welche Karte bekommt, handelt es sich um eine Variation (und, da jede Karte nur ein Mal vorhanden ist, um eine Variation ohne Wiederholung).
Wir setzen also in unsere Formel ein und erhalten
\(\frac{n!}{(n-k)!} = \frac{52!}{48!} = \frac{8,06581...\cdot 10^{67}}{1,24139...\cdot 10^{61}} = 6\ 497\ 400\)
unterschiedliche Möglichkeiten.
Permutationen
Permutationen sind jener Sonderfall von Variationen ohne Wiederholung, bei dem alle Elemente gezogen werden (wenn also \(k = n\) ist). Die Anzahl der Permutationen von \(n\) Elementen ist schlicht die Anzahl der unterschiedlichen Reihenfolgen, in denen \(n\) Elemente angeordnet werden können.
Die Formel vereinfacht sich in diesem Fall. Indem wir \(k = n\) setzen erhalten wir
\(\frac{n!}{(n-k)!} = \frac{n!}{(n-n)!} = \frac{n!}{0!} = \frac{n!}{1} = n!\).
Beispiel:
Wie viele unterschiedliche Möglichkeiten gibt es, eine fünfköpfige Familie an einem Tisch mit fünf Sitzplätzen zu platzieren?
Hier ist \(n = k = 5\). Wir setzen ein und erhalten
\(n! = 120\) verschiedene Möglichkeiten.
Hier ist \(n = k = 5\). Wir setzen ein und erhalten
\(n! = 120\) verschiedene Möglichkeiten.
