Was ist der Unterschied zwischen einer Kombination und einer Permutation?
Eine Permutation ist eine geordnete Anordnung, eine Kombination eine ungeordnete Auswahl. Ziehen Sie drei Karten aus einem Stapel und unterscheiden zwischen erster, zweiter und dritter Karte, zählen Sie Permutationen — Ass-König-Dame und Dame-König-Ass sind verschiedene Ergebnisse. Interessiert nur, welche drei Karten Sie am Ende halten, zählen Sie Kombinationen, und beide Züge ergeben dasselbe Blatt. Formal gilt für Permutationen P(n, k) = n! / (n − k)! und für Kombinationen C(n, k) = n! / (k! · (n − k)!). Die Formeln unterscheiden sich genau um den Faktor k!, der die Anzahl der Anordnungen jeder gewählten Teilmenge zählt. Daher ist P(n, k) immer k!-mal größer als C(n, k).
Wie hoch ist die Wahrscheinlichkeit für sechs Richtige im Lotto 6 aus 49?
Beim deutschen Lotto 6 aus 49 spielt die Reihenfolge der Zahlen keine Rolle, also liegt eine reine Kombinationsaufgabe vor. Die Anzahl aller möglichen Tippreihen ist C(49, 6) = 13.983.816, und genau eine davon entspricht der Gewinnreihe. Die Wahrscheinlichkeit für sechs Richtige beträgt damit 1 zu 13.983.816, also rund 1 zu 14 Millionen. Mit Superzahl (eine zusätzliche Zahl von 0 bis 9) sinkt die Wahrscheinlichkeit für den Jackpot auf 1 zu 139.838.160. Praktisch heißt das: Zehn Tippreihen erhöhen die Chance auf zehn zu 14 Millionen, also etwa 1 zu 1,4 Millionen — ein Glücksspiel mit langfristig negativem Erwartungswert nach Steuern und Quotenanteilen.
Was bedeutet n über k und wie hängt es mit dem Binomialkoeffizienten zusammen?
Der Ausdruck n über k, geschrieben als binom(n, k) oder C(n, k), ist der Binomialkoeffizient und gibt die Anzahl der k-elementigen Teilmengen einer n-elementigen Menge an. Die Formel lautet n über k = n! / (k! · (n − k)!). Der Name kommt vom binomischen Lehrsatz: Die Koeffizienten in der Entwicklung von (a + b)^n sind genau die Werte n über 0, n über 1 bis n über n. Eine wichtige Eigenschaft ist die Symmetrie n über k = n über (n − k), die anschaulich bedeutet, dass die Auswahl einer k-elementigen Teilmenge gleichbedeutend ist mit dem Weglassen einer (n − k)-elementigen Teilmenge. Außerdem gilt die Pascalsche Identität n über k = (n − 1) über (k − 1) + (n − 1) über k, die das Pascalsche Dreieck erzeugt.
Wie erkenne ich, ob die Reihenfolge in meiner Aufgabe wichtig ist?
Fragen Sie sich, ob das Vertauschen zweier ausgewählter Elemente ein anderes Ergebnis liefert, das die Aufgabe als unterschiedlich behandelt. Wenn ja, verwenden Sie Permutationen, wenn nein, Kombinationen. Podestplätze bei einem Wettkampf (Gold, Silber, Bronze) sind Permutationen, weil die Medaillen unterschiedlich sind. Ein dreiköpfiger Vereinsausschuss ist eine Kombination, denn der Ausschuss bleibt derselbe, unabhängig davon, wen Sie zuerst nennen. Passwörter und PINs sind Permutationen, weil 1234 und 4321 verschiedene Konten entsperren. Lottozahlen sind Kombinationen, weil der Tippschein gewinnt, egal in welcher Reihenfolge Sie die Zahlen aufgeschrieben haben. Im Zweifel zählen Sie einen kleinen Fall von Hand und prüfen, ob Ihre Zählung mit der Formel übereinstimmt.
Was ändert sich bei Ziehung mit Zurücklegen statt ohne Zurücklegen?
Ohne Zurücklegen kann jedes Element höchstens einmal gewählt werden — das ist die Voraussetzung der Standardformeln P(n, k) und C(n, k). Mit Zurücklegen darf dasselbe Element mehrfach gezogen werden, was die Anzahlen vergrößert. Permutationen mit Wiederholung ergeben einfach n^k, denn jede der k Positionen hat alle n Optionen. Kombinationen mit Wiederholung folgen der Sterne-und-Striche-Formel C(n + k − 1, k) und zählen Multimengen — zum Beispiel gibt es C(5 + 3 − 1, 3) = C(7, 3) = 35 Möglichkeiten, drei Kugeln Eis aus fünf Sorten mit erlaubter Wiederholung auszuwählen. Praktische Faustregel: Karten ohne Zurücklegen ziehen ist ohne Wiederholung, denselben Würfel k-mal werfen ist mit Wiederholung.
Warum verwenden Kombinatorik-Formeln Fakultäten und wie schnell wachsen sie?
Die Fakultät n! = n · (n − 1) · ... · 1 zählt die Anzahl der Anordnungen von n verschiedenen Elementen in einer Reihe und ist damit der Baustein für Permutationen und Kombinationen. Fakultäten wachsen extrem schnell — 10! ergibt bereits 3.628.800, 20! übersteigt 2,4 · 10^18, und 70! sprengt einen Standard-64-Bit-Gleitkommawert. Deshalb sollten Rechner gemeinsame Faktoren kürzen, bevor sie multiplizieren. Für C(100, 3) wäre 100! / (3! · 97!) direkt auszuwerten ineffizient, doch die Umformung (100 · 99 · 98) / (3 · 2 · 1) = 161.700 ist schnell und exakt. Gute Kombinatorik-Werkzeuge nutzen diese Kürzung oder rechnen intern mit logarithmierten Fakultäten.
Welche Bedingungen müssen n und k erfüllen?
Sowohl n als auch k müssen nicht-negative ganze Zahlen sein, und für die Standardformeln ohne Zurücklegen muss k kleiner oder gleich n sein. Wichtige Randfälle sind eindeutig festgelegt: C(n, 0) = 1, denn es gibt genau eine Möglichkeit, nichts auszuwählen (die leere Menge), C(n, n) = 1, weil es eine Möglichkeit gibt, alles auszuwählen, P(n, 0) = 1 per Konvention, und 0! = 1, damit die Formeln konsistent bleiben. Wenn Ihre Aufgabe ein nicht-ganzzahliges n, ein negatives k oder k > n erzeugt, ist die Standardzählung undefiniert oder null, und Sie sollten prüfen, ob Sie ein anderes Modell wie Multinomialkoeffizienten, Permutationen mit Wiederholung oder Kombinationen mit Zurücklegen brauchen.
