Permutationen-Rechner

Permutation P(n, r) = n! / (n − r)! = nPr · Kombination C(n, r) = n! / (r!(n − r)!) · P(n, r) = C(n, r) · r! · mit Wiederholung: P = nʳ

n

die Größe des Vorrats – wie viele verschiedene Dinge es überhaupt zu nehmen gibt, höchstens 1000. Diese Grenze betrifft die Arithmetik und nicht die Vorstellung: Die Zählung wächst mit n außerordentlich schnell, und ab einem bestimmten Punkt liegt der genaue Wert nicht mehr in dem Bereich ganzer Zahlen, den diese Seite exakt darstellen kann

r

wie viele tatsächlich herausgegriffen werden. Ohne Wiederholung darf r nicht größer als n sein, denn es lassen sich nicht mehr verschiedene Dinge herausgreifen, als vorhanden sind; sobald Wiederholung erlaubt ist, darf r größer werden und ist nur noch dadurch begrenzt, wie weit sich die Potenz hier noch exakt berechnen lässt

n!

die Fakultät von n: n multipliziert mit jeder ganzen Zahl darunter bis hinunter zur 1. Sie ist die Zählung dafür, alles der Reihe nach herauszunehmen, und genau der Abschnitt, den die Division durch (n − r)! wieder entfernt

P(n, r)

die Permutationszahl: Für den ersten Platz gibt es n Möglichkeiten, für den zweiten bleiben n − 1, und so weiter über r Plätze. Dieses Produkt n × (n − 1) × … × (n − r + 1) ist das n! / (n − r)! der Formel

C(n, r)

die Zählung ohne Reihenfolge, gedruckt in der zweiten Zeile. Sie teilt die Permutationszahl durch r!, also durch die Zahl der Anordnungen, die eine herausgegriffene Gruppe selbst hat – der ganze Unterschied zwischen den beiden Zeilen steckt in dieser einen Division

Wiederholung

welches der beiden Regelwerke gerade gilt. Mit Wiederholung wird die Zählung zur r-ten Potenz von n, weil bei jedem der r Zugriffe der ganze Vorrat wieder zur Verfügung steht; die Zeile ohne Reihenfolge wechselt dann zur Zählung der Multimengen

Gebraucht wird der Rechner, wenn die Position zählt: die Rangfolge eines Wettkampfs, die Reihenfolge der ersten drei ausgegebenen Karten, ein Passwort oder ein Kennzeichen, jede Liste, in der zwei vertauschte Plätze ein anderes Ergebnis ergeben. Geht es um eine Gruppe von Personen, nimmt man die Kombinationszeile – oder die andere Seite dieses Seitenpaars –, weil dann zwei Anordnungen derselben r Dinge dieselbe Antwort ergeben und die Division durch r! genau diese Korrektur ist. Der Schalter für die Wiederholung gehört eingeschaltet, wenn ein Ding nach der Entnahme wieder zur Verfügung steht: Ein vierstelliger Code hat 10⁴ Möglichkeiten, weil jede Stelle erneut aus den zehn Ziffern gezogen wird, während die Kugeln einer Lottoziehung nicht doppelt vorkommen. Und selbst wer nur wegen der ersten Zeile hier ist, sollte die zweite mitlesen: Die beiden Zählungen nebeneinander sind die klarste Erklärung dafür, warum die Reihenfolge überhaupt etwas ausmacht, denn sie unterscheiden sich um genau einen Faktor. Ob die Reihenfolge zählt oder nicht, entscheidet die Frage, ob sich das Ergebnis ändert, wenn man zwei herausgegriffene Dinge vertauscht – ändert es sich, ist es eine Permutation, sonst eine Kombination.

1. Drei aus zehn: 720 Permutationen, 120 Kombinationen

   1. Für den ersten Platz gibt es zehn Möglichkeiten, für den zweiten bleiben neun, für den dritten acht
   2. Multipliziert: 10 × 9 × 8 = 720 Permutationen
   3. Ohne Reihenfolge wird durch 3! = 6 geteilt, das ergibt 120 Kombinationen
   4. 720 / 120 = 6, und das ist genau 3!

   Die beiden Zeilen nebeneinander sind der Grund, warum es diese Seite gibt: dieselben zehn Dinge, dieselben drei herausgegriffen, mit Reihenfolge 720 und ohne Reihenfolge 120, und ihr Verhältnis ist 3! – also die Zahl der Anordnungen, die drei herausgegriffene Dinge haben. Wann immer Permutation und Kombination nicht zusammenzupassen scheinen, ist die Division der beiden Zahlen die schnellste Prüfung: Ist der Quotient keine Fakultät, liegt der Fehler in der Aufgabenstellung und nicht in der Rechnung.

2. Acht Läufer kämpfen um drei Plätze

   1. Für den Sieg gibt es acht Möglichkeiten, für den zweiten Platz bleiben sieben, für den dritten sechs
   2. 8 × 7 × 6 = 336 Arten, das Siegerpodest zu besetzen
   3. Ohne Reihenfolge sind dieselben drei Personen in jeder Anordnung dieselbe Gruppe: 336 / 6 = 56
   4. Mit einem anderen Weg nachgerechnet: 8!/(8−3)! = 40.320/120, ebenfalls 336

   Das ist die alltäglichste Gestalt dieser Unterscheidung: Ein Rennergebnis ist eine Permutation, weil Silber nicht Gold ist; wer weiterkommt, ist dagegen eine Kombination, weil die drei Schnellsten dieselben drei bleiben, egal in welcher Reihenfolge sie gelaufen sind. Beachten Sie auch, dass dasselbe Zahlenpaar auf der Kombinationen-Seite mit vertauschten Zeilen auftaucht – dieses Seitenpaar arbeitet dort wie vorgesehen, das ist keine doppelte Darstellung derselben Sache.

3. Fünf Karten der Reihe nach ausgeben

   1. Für die erste Karte gibt es 52 Möglichkeiten, für die zweite 51, bis hinunter zu 48 für die fünfte
   2. 52 × 51 × 50 × 49 × 48 = 311.875.200 geordnete Ausgaben
   3. Ein Blatt aus fünf Karten kennt keine Reihenfolge, also wird durch 5! = 120 geteilt
   4. 311.875.200 / 120 = 2.598.960 – die vertraute Zahl aus der Pokerrechnung

   2.598.960 ist der Nenner, durch den jede Pokerwahrscheinlichkeit geteilt wird, diese Zeile ist also die Stelle, an der Leser eine Zahl abgleichen können, die sie anderswo schon gesehen haben. Sie zeigt zugleich am deutlichsten, wie groß der Faktor der Reihenfolge wird: Dieselben fünf Karten in anderer Folge sind eine andere geordnete Ausgabe, aber dasselbe Blatt, und der Faktor zwischen den beiden Zählungen ist hier 120 statt 6. Beide Zählungen sind exakte Werte, ohne jede Rundung.

4. Ein dreistelliger Code mit Wiederholung

   1. Mit Wiederholung greift jede der drei Stellen unabhängig auf alle zehn Ziffern zu
   2. 10 × 10 × 10 = 1000 Zifferncodes
   3. Die Zeile ohne Reihenfolge ist jetzt nicht mehr 1000 / 6, denn ein Code wie 777 hat keine sechs verschiedenen Anordnungen
   4. Sie wechselt zur Zählung der Multimengen: C(10 + 3 − 1, 3) = C(12, 3) = 220

   Interessant ist hier die zweite Zeile. Solange die Dinge alle verschieden sind, ist die Zählung ohne Reihenfolge einfach die Permutationszahl geteilt durch r!, sobald aber Wiederholung erlaubt ist, schießt diese Division über das Ziel hinaus – 777 hat nur eine Anordnung und nicht sechs –, deshalb wechselt die Seite die Formel, statt weiter zu teilen. 220 ist die Zahl der Multimengen von drei aus zehn Ziffern, und genau deshalb ändert dieser Schalter beide Zeilen und nicht nur die erste.

Zwei Grenzen werden abgefangen und nicht wegerklärt, und beide sollte man kennen, bevor einen die Zahlen überraschen. Ohne Wiederholung darf r nicht größer als n sein: Aus drei verschiedenen Dingen vier herauszugreifen ist kein unwahrscheinliches Ereignis, sondern ein unmögliches Verlangen, und die Seite sagt das, statt 0 zurückzugeben. Die Größe des Vorrats ist auf 1000 begrenzt. In der Praxis stößt man aber zuerst an die zweite Grenze: Die Permutationszahl ist ein außerordentlich schnell wachsendes Produkt, und diese Seite druckt exakte ganze Zahlen und keine Näherung in wissenschaftlicher Schreibweise. Jenseits der Linie, ab der der wahre Wert nicht mehr exakt darstellbar ist, verweigert sie die Antwort, statt eine ganze Zahl mit falschen Endziffern zu drucken – hier ist eine plausibel aussehende falsche Zahl weit schlimmer als eine klare Absage, weil diese falsche Zahl in alles abgeschrieben wird, was auf ihr aufbaut. Der Zweig mit Wiederholung hat eine noch kleinere Rechengrenze: Dort ist die Zählung eine Potenz, und ein großer Exponent läuft ebenfalls über. Zwei Bemerkungen zur Bedeutung kommen hinzu. Beide Zeilen sind keine Wahrscheinlichkeiten, sondern Zählungen gleich möglicher Anordnungen; um aus einer Zählung eine Wahrscheinlichkeit zu machen, muss man noch durch die Gesamtzahl der Möglichkeiten teilen, und diese Gesamtzahl hängt vom Verfahren ab und nicht von dem Zahlenpaar auf dieser Seite. Und diese Seite hat keine Tabelle mit Fakultäten, Binomialkoeffizienten oder dem Pascalschen Dreieck – der Grund steht in der fünften Frage unten.

Worin unterscheidet sich die Permutationszahl von der Kombinationszahl?

Die Permutationszahl zählt Anordnungen, die Kombinationszahl zählt Mengen: Zwei herausgegriffene Dinge zu vertauschen ergibt für die Permutation ein anderes Ergebnis und für die Kombination nicht. Diese Seite druckt beide Zahlen zusammen, damit dieses Verhältnis sichtbar wird und nicht nur behauptet bleibt – die Permutationszahl ist stets die größere, und geteilt durch die Fakultät von r ergibt sie die andere Zeile. In der Praxis ist die Frage, ob der Platz eine Bedeutung hat. Wenn der dritte Platz ein anderer ist als der zweite, wie bei einer Rangfolge oder der Reihe nach ausgegebenen Karten, ist die Permutationszahl gefragt; wenn die ausgewählten Dinge austauschbar sind, die Kombinationszahl.

Warum unterscheiden sich die beiden Zeilen genau um die Fakultät von r?

Weil sich irgendwelche r ausgewählten Dinge auf r! Arten anordnen lassen und die Permutationszahl jede dieser Anordnungen als eigenes Ergebnis zählt. Bei r = 3 lassen sich drei beliebige Dinge auf sechs Arten anordnen, einer Kombination entsprechen also sechs Permutationen, und die Permutationszahl ist sechsmal so groß. Das ist zugleich die schnellste Probe: Teilt man die beiden Zeilen durcheinander, muss der Quotient eine Fakultät sein. Ist er das nicht, steckt der Fehler in der Aufgabenstellung und nicht in der Rechnung – am häufigsten darin, dass Vorratsgröße oder Wiederholungsschalter nicht zu dem Fall passen, der beschrieben wurde.

Wann zählt dasselbe Ding zweimal zu nehmend als zwei Ergebnisse?

Genau dann, wenn der Vorgang es zulässt, zweimal genommen zu werden – das ist es, was der Wiederholungsschalter steuert, und er ändert beide Zeilen und nicht nur die erste. Bei einem vierstelligen Code wird jede Stelle erneut aus den zehn Ziffern gezogen, eine Wiederholung wie 0000 ist also ein gewöhnliches Ergebnis und die Zählung ist 10⁴; bei einer Lotterie werden die Kugeln aus der Trommel genommen, keine Nummer kann zweimal erscheinen, und die Zählung ist das absteigende Produkt. Mit Wiederholung ist die Kombinationszeile nicht mehr die Permutationszahl geteilt durch r!, weil eine Auswahl wie 777 nur eine Anordnung hat und nicht sechs; die Seite wechselt diese Zeile dann auf die Zählung der Multimengen.

Warum weigert sich die Seite, mehr Dinge herauszugreifen, als im Vorrat sind?

Ohne Wiederholung beschreibt ein r, das größer als n ist, einen unmöglichen Vorgang: Wenn nur drei Dinge zur Verfügung stehen, gibt es kein viertes verschiedenes Ding. Die Seite meldet diesen Widerspruch, statt 0 zurückzugeben, weil die 0 unter anderen Einstellungen eine gültige Zählung ist und dann als Antwort weitergelesen würde. Schaltet man die Wiederholung ein, wird dieselbe Anfrage ganz gewöhnlich – drei Dinge jeweils einmal zu nehmen und das fünfmal hintereinander mit Wiederholung sind 3⁵ = 243 Permutationen –, diese Einschränkung hängt also an der Kombination der beiden Einstellungen und nicht an r allein.

Warum gibt es auf diesem Seitenpaar keine Tabelle mit dem Pascalschen Dreieck oder mit Fakultäten?

Weil eine Tabelle an dieser Stelle die beiden Zahlen, die Sie eintragen, nicht sehen kann und die Tabelle, die man sich wünscht – Fakultäten, Binomialkoeffizienten, die Zeilen des Pascalschen Dreiecks – eine feste Liste kleiner Werte ist. Stünde sie hier, beantwortete sie eine andere Frage als das Panel darüber und widerspräche gelegentlich offen der Zeile, die Sie gerade lesen, was schlimmer wäre als keine Tabelle. Das Panel ist diese Tabelle: Ändern Sie n, ändern Sie r, stellen Sie den Wiederholungsschalter um, und beide Zeilen rechnen sich neu. Dieses Seitenpaar gibt dieselbe Auskunft wie die anderen Zählwerkzeuge, und nicht die eine Seite eine Tabelle und die andere keine, weil die beiden Seiten ohnehin zwei Richtungen derselben Frage sind.

Warum kommt bei einem großen Vorrat keine Antwort mehr?

Weil die Permutationszahl ein langes Produkt ganzer Zahlen ist und die größte ganze Zahl, die diese Seite noch exakt darstellen kann, viel früher überschritten wird, als die meisten erwarten – schon die Fakultät von 19 liegt darüber, obwohl sie nur 18 Stellen hat und harmlos aussieht. Ab diesem Punkt verweigert die Seite die Antwort, statt eine Zahl mit falschen Endziffern zu drucken, und genau diese Ziffern sind der ganze Wert einer exakten Zählung: Eine falsche ganze Zahl sieht völlig gewöhnlich aus und wird in jede Rechnung übernommen, die auf ihr aufbaut. Die Obergrenze von 1000 für den Vorrat ist eine zweite, lockerer gezogene Verteidigungslinie um dieselbe Sache – sie fängt die Eingabe bei einer Größe ab, bei der die Arithmetik noch einen Versuch lohnt.

• Permutation — DWDS, Digitales Wörterbuch der deutschen Sprache: der Terminus, den diese Seite zählt, und der Wortgebrauch, der zwischen «mit» und «ohne Wiederholung» unterschieden wird — Berlin-Brandenburgische Akademie der Wissenschaften
• Permutation — from Wolfram MathWorld (English original; rearranging the elements of an ordered list, and counting the rearrangements of a given size — the definition behind the primary result on this page) — Wolfram MathWorld
• Combination — from Wolfram MathWorld (English original; the number of ways to choose from a collection without regard to order, also called a binomial coefficient and read as «n choose k» — the definition behind the second line on this page) — Wolfram MathWorld
• 1.3.6.1. What is a Probability Distribution — e-Handbook of Statistical Methods (English original; the frequency reading of probability as a share of the whole, which is the step that turns a count of equally likely arrangements into a probability) — National Institute of Standards and Technology (NIST)