Kombinatorik berechnen: Permutation, Kombination und Variation

Starte mit der Grundfrage der Aufgabe: Geht es um eine Anordnung aller Elemente, um eine Auswahl ohne Reihenfolge oder um eine Auswahl mit Reihenfolge?

Genau daraus ergeben sich Permutation, Kombination oder Variation als die drei Grundtypen, zwischen denen der Rechner unterscheidet.

Frage dich außerdem, ob jedes Element nur einmal vorkommt oder ob Wiederholung erlaubt ist, denn diese zweite Entscheidung verzweigt jeden Typ noch einmal in zwei Varianten, sodass insgesamt sieben Modi zur Wahl stehen, einschließlich des Binomialkoeffizienten.

Eine falsche Moduswahl liefert zwar eine Zahl, beantwortet aber nicht die eigentliche Frage.

Beispiel: Beim Lottoziehen ohne Reihenfolge und ohne Wiederholung ist Kombination richtig, bei einem PIN-Code mit Reihenfolge und erlaubter Wiederholung dagegen Variation mit Wiederholung.

Bei der Anordnung von 5 verschiedenen Buchstaben liefert Permutation ohne Wiederholung sofort 5! = 120 mögliche Reihenfolgen. Lege also zuerst Modus und Wiederholung fest, bevor du n und k einträgst.

Permutation ordnet alle n vorhandenen Elemente vollständig an, Variation wählt k aus n Elementen aus und beachtet dabei die Reihenfolge, und Kombination wählt ebenfalls k aus n aus, ignoriert die Reihenfolge aber vollständig.

Zusätzlich entscheidet Wiederholung, ob ein Element mehrfach in derselben Auswahl vorkommen darf.

Diese zwei Weichenstellungen bestimmen fast den gesamten Rechenweg und erklären, warum ähnlich formulierte Aufgaben zu sehr unterschiedlichen Ergebnissen führen: 3 Elemente aus 5 ohne Wiederholung ausgewählt ergeben als Kombination 10 Möglichkeiten, als Variation dagegen 60, weil dort zusätzlich jede Reihenfolge einzeln zählt.

Permutation ist letztlich ein Sonderfall der Variation mit k gleich n.

Prüfe deshalb bei jeder Aufgabe bewusst, ob eine Rangfolge wie Gold, Silber, Bronze vorkommt (dann Variation oder Permutation) oder ob nur eine Gruppe ohne Rang gebildet wird (dann Kombination), denn genau hier entstehen die häufigsten Modellierungsfehler zwischen den drei Grundtypen.

Für 4 unterschiedliche Zahlen oder Ziffern, die jeweils genau einmal in wechselnder Reihenfolge verwendet werden, liefert die Permutation ohne Wiederholung 4! = 24 mögliche Anordnungen, für 5 Zahlen sind es 5! = 120, und für 6 Zahlen bereits 6! = 720.

Diese Fragestellung ist im Alltag doppeldeutig: Gemeint sein kann entweder das vollständige Durchmischen aller Zahlen (Permutation, n!) oder das Bilden von Teilmengen ohne Beachtung der Reihenfolge (Kombination, C(n,k)).

Im Kombinatorik-Rechner wählst du dafür bewusst Permutation ohne Wiederholung, trägst n als Anzahl der verschiedenen Zahlen ein und liest die Anzahl direkt ab.

Zum Vergleich: 3 Zahlen ergeben nur 3! = 6 Reihenfolgen, 7 Zahlen dagegen schon 7! = 5.040.

Prüfe bei jeder Aufgabe zuerst, ob wirklich alle Zahlen einmal verwendet werden sollen, denn sobald nur ein Teil ausgewählt wird oder Wiederholung erlaubt ist, gilt stattdessen Variation oder Kombination mit einem eigenen k-Wert.

Die Häufigkeiten-Liste brauchst du nur, wenn einzelne Elemente mehrfach identisch vorkommen, etwa bei Wörtern mit doppelten Buchstaben wie ANNA oder bei mehrfach gleichen Objekten in einer Anordnungsaufgabe.

Dann muss der Rechner wissen, wie oft jede gleichartige Gruppe vertreten ist, um mehrfach gezählte identische Anordnungen wieder herauszukürzen; wichtig ist, dass sich alle angegebenen Häufigkeiten zusammen exakt zu n addieren.

Beim Wort ANNA mit dem Häufigkeitsvektor (2,1,1) liefert die Multinomialformel 4!/(2!·1!·1!) = 12 verschiedene Buchstabenanordnungen statt der naiven 24 Permutationen für vier komplett verschiedene Symbole.

Beim Wort MISSISSIPPI mit vier S, vier I, zwei P und einem M ergibt sich 11!/(4!·4!·2!·1!) = 34.650 verschiedene Anordnungen. Für Buchstabenrätsel oder Anagramme ist dieser Modus damit die richtige Wahl.

Lass die Liste leer, solange alle Elemente verschieden sind, und fülle sie erst bei echten Mehrfach-Buchstaben aus, sonst rechnet der Rechner mit einer zu großen Anzahl.

Bei Kombinationen oder Variationen ohne Wiederholung kannst du nicht mehr Elemente auswählen, als insgesamt vorhanden sind, weil jedes Element nur einmal gewählt werden darf; die Bedingung k kleiner oder gleich n ist deshalb zwingend.

Der Rechner blockiert Fälle mit k größer als n in diesen Modi und gibt eine Hinweismeldung aus, statt eine sinnlose Zahl zu liefern.

Mathematisch sichtbar wird das an C(n,k) = n!/(k!·(n−k)!): Für k größer als n würde (n−k)! die Fakultät einer negativen Zahl verlangen, die nicht definiert ist.

Nur bei Aufgaben mit Wiederholung darf die Auswahl größer sein als n, weil dort jedes Element beliebig oft erneut auftauchen kann.

Praktisches Beispiel: Wer aus 3 Zutaten 5 Portionen zusammenstellt und jede Zutat beliebig oft nehmen darf, braucht Variation mit Wiederholung, dort ist k=5 größer als n=3 ausdrücklich erlaubt.

Prüfe daher zuerst, ob Wiederholung erlaubt ist, wenn dir der Rechner k größer als n verweigert.

Der Binomialkoeffizient C(n,k), gelesen als n über k, zählt, wie viele Möglichkeiten es gibt, k Elemente aus n auszuwählen, wenn die Reihenfolge keine Rolle spielt, und entspricht damit exakt der Kombination ohne Wiederholung.

Im Rechner wählst du dafür den Modus Binomialkoeffizient, trägst n und k ein und erhältst das Ergebnis über die Formel C(n,k) = n!/(k!·(n−k)!); für n=9 und k=3 etwa ergibt das 84.

Im Pascalschen Dreieck enthält Zeile n genau die Folge C(n,0) bis C(n,n), und benachbarte Einträge addieren sich zum Wert darunter.

Als Gewichtungsfaktor im Binomialterm P(X=k) = C(n,k)·p^k·(1−p)^(n−k) gibt der Binomialkoeffizient an, auf wie viele Weisen sich k Treffer auf n unabhängige Versuche verteilen lassen.

C(49,6) etwa liefert 13.983.816 mögliche Tippreihen beim Lotto 6 aus 49. Nutze den Modus n über k als Schnellzugang, wenn eine Aufgabe bereits in dieser Schreibweise formuliert ist, statt sie erst in Kombination ohne Wiederholung zu übersetzen.

Die Fakultät n! ist das Produkt aller ganzen Zahlen von 1 bis n, und der Kombinatorik-Rechner berechnet sie direkt, sobald du den Modus Permutation ohne Wiederholung wählst: Dort steht n! als eigenständige Formel, ganz ohne separaten Fakultät-Modus.

Für n=5 ergibt das 5! = 120, für n=10 bereits 3.628.800. Fakultäten wachsen extrem schnell, weshalb sie kaum noch im Kopf zu bewältigen sind.

Für 0! legt die Mathematik den Wert 1 fest, keine willkürliche Konvention, sondern zwingend aus der Rekursionsformel n! = n·(n−1)!: Setzt man n=1, folgt 1! = 1·0!, also muss 0! = 1 sein.

Dieselbe Eins ergibt sich aus C(0,0) = 0!/(0!·0!) = 1, denn es gibt genau eine Auswahl von null Objekten aus null, nämlich die leere Menge.

Trage im Rechner einfach n ein und lies das Ergebnis unter dem Feld Formel ab, statt die Fakultät manuell auszumultiplizieren, denn schon ab etwa 20! wird die Zahl für Kopfrechnung praktisch unbrauchbar.

Ein dreistelliges Zahlenschloss mit Ziffern von 0 bis 9, bei dem jede Ziffer mehrfach vorkommen darf und die Reihenfolge zählt, hat V*(n,k) = 10³ = 1.000 mögliche Einstellungen; das ist Variation mit Wiederholung.

Ein vierstelliger PIN-Code funktioniert nach demselben Muster und ergibt V*(10,4) = 10^4 = 10.000 mögliche Codes.

Dürften sich die vier Ziffern dagegen nicht wiederholen, sänke die Zahl auf Variation ohne Wiederholung V(10,4) = 10·9·8·7 = 5.040, weil jede weitere Stelle nur noch aus den verbleibenden Ziffern wählen könnte.

Im Rechner bildest du das ab, indem du n=10 (die Ziffern 0 bis 9) und k als Stellenzahl einträgst und je nach Aufgabenstellung zwischen Variation mit und ohne Wiederholung wechselst.

Achte besonders darauf, ob eine Aufgabe Wiederholung ausdrücklich erlaubt oder ausschließt, denn genau dieser eine Schalter verzehnfacht oder verfünftelt das Ergebnis bei gleicher Stellenzahl.

Viele Wahrscheinlichkeitsaufgaben im Laplace-Modell brauchen zuerst die Gesamtzahl möglicher Ergebnisse und die Anzahl günstiger Ergebnisse, und genau diese Zählbasis liefert die Kombinatorik.

Der Kombinatorik-Rechner ist deshalb oft der Vorbau für Laplace- und Auswahlaufgaben: Du bestimmst mit ihm zuerst die günstigen und die möglichen Fälle und bildest danach den Quotienten als eigentliche Wahrscheinlichkeit, etwa im Wahrscheinlichkeitsrechner.

Im Binomialterm P(X=k) = C(n,k)·p^k·(1−p)^(n−k) ist C(n,k) genau die Anzahl der Möglichkeiten, k Treffer auf n Versuche zu verteilen.

Beim Lotto liefert C(49,6) = 13.983.816 mögliche Tippreihen, woraus sich die Gewinnwahrscheinlichkeit für einen Sechser unmittelbar als 1 geteilt durch diesen Wert ergibt.

Bei einem fairen Münzwurf mit n=4 Versuchen liefert C(4,2) = 6 die Anzahl der Wege zu genau zwei Köpfen.

Nutze den Kombinatorik-Rechner also nicht nur für Anordnungsaufgaben, sondern auch als ersten Rechenschritt, bevor du eine Lotto- oder Ziehungswahrscheinlichkeit ermittelst.

Zähle eine kleine Testversion der Aufgabe von Hand durch, etwa mit n=3 oder n=4 Elementen, denn stimmt dein Rechenweg schon dort nicht mit der Handauszählung überein, ist meist der gewählte Modus oder eine der beiden Entscheidungen Reihenfolge und Wiederholung falsch gesetzt.

Beispiel: Kombinationen ohne Wiederholung aus n=4 und k=2 ergeben C(4,2)=6, und eine manuelle Auszählung der Buchstaben A, B, C, D liefert tatsächlich genau die sechs Paare AB, AC, AD, BC, BD und CD.

Zeigt der Rechner hier stattdessen 12 oder gar 24, ist fälschlich der Variations- statt der Kombinationsmodus aktiv, weil Variation zusätzlich jede Reihenfolge separat zählt.

Ein zweites Signal ist die Größenordnung: Bleibt das Ergebnis überraschend klein, ist oft eine zu restriktive Einstellung ohne Wiederholung aktiv, obwohl Wiederholung eigentlich erlaubt wäre.

Starte den Gegencheck immer mit kleinen Werten, denn nur so lassen sich Modellierungsfehler in Sekunden erkennen, bevor du dich auf sehr große Kombinationszahlen verlässt.