Kombinationen-Rechner

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

n

wie viele verschiedene Dinge zur Auswahl stehen – die Größe des Vorrats, nicht die Zahl der Entnahmen

r

wie viele tatsächlich entnommen werden. Ohne Wiederholung darf r nicht größer als n sein; mit Wiederholung darf r über n hinausgehen, weil dasselbe Element mehrfach entnommen werden darf

Wiederholung

ob dasselbe Element mehrfach entnommen werden darf. Das ist keine Frage der Darstellung, sondern ein Satz anderer Formeln; und derselbe Schalter entscheidet darüber, ob „r größer als n“ zulässig oder schlicht unmöglich ist

C(n, r)

die Kombination, also nCr: die Zahl der Auswahlen von r Elementen ohne Berücksichtigung der Reihenfolge, ABC und CBA zählen deshalb als eine einzige

P(n, r)

die Permutation, also nPr: die Zahl der Auswahlen von r Elementen mit Reihenfolge, ABC und CBA sind hier also zwei verschiedene Ergebnisse. Sie ist stets gleich der Kombination mal r!

Der Rechner passt überall dort, wo wirklich nach der Zahl der Auswahlmöglichkeiten gefragt ist – und das ist die weit überwiegende Mehrheit der Fälle, in denen eine Wahrscheinlichkeit durch Abzählen statt durch eine Formel bestimmt wird. Eine Hand beim Kartenspiel, eine Zahlenkombination im Lotto, Personen aus einer Liste auswählen, Sitzplätze vergeben: immer dieselbe Rechnung. Vorher festgelegt werden muss dabei eine einzige Sache, nämlich ob die Reihenfolge zählt – eine Hand ist eine Kombination, die Platzierung auf dem Siegertreppchen eine Permutation. Der Schalter für die Wiederholung wirkt erst dort, wo dieselbe Wahl zweimal getroffen werden kann: Drei Kugeln aus mehreren Sorten zusammenzustellen zählt die Reihenfolge weiterhin nicht, lässt aber dieselbe Sorte mehrfach zu, und das ist eine Kombination mit Wiederholung und keine gewöhnliche. Diese Seite berechnet nur diese Anzahlen, keine Wahrscheinlichkeiten – für eine Wahrscheinlichkeit wird mit diesen Anzahlen einen Schritt weitergerechnet.

1. Drei aus zehn: 120 Kombinationen, 720 Permutationen

   1. Ohne Reihenfolge ist C(10,3) = 10! / (3! × 7!) = (10 × 9 × 8) / (3 × 2 × 1) = 120
   2. Mit Reihenfolge ist P(10,3) = 10 × 9 × 8 = 720
   3. Die beiden unterscheiden sich um 3! = 6, also um die Zahl der Anordnungen, die drei entnommene Dinge haben können
   4. Probe: 120 × 6 = 720

   Dieses Paar ist der Grund, warum es diese Seite gibt. Dieselben drei Dinge ergeben als Kombination genau eine Möglichkeit und als Permutation sechs, eine Zählung ohne die Angabe, welche der beiden gemeint ist, kann hier also um den Faktor sechs danebenliegen – bei fünf Entnahmen um den Faktor 120, und dann ist der Fehler so groß, dass er nicht mehr wie ein Fehler aussieht. Der letzte Schritt ist die Beziehung, die man behalten sollte: Die Permutation ist stets die Kombination mal der Fakultät von r, weil sich jede Auswahl ohne Reihenfolge auf genau r! Arten anordnen lässt, nicht auf mehr und nicht auf weniger.

2. Dieselben drei aus zehn, diesmal mit Wiederholung

   1. Mit Wiederholung und ohne Reihenfolge ist C = (10 + 3 − 1)! / (3! × 9!) = C(12,3) = 220
   2. Mit Wiederholung und mit Reihenfolge ist P = 10³ = 1000
   3. Die Kombination entspricht einem größeren Vorrat – die Formel addiert r − 1 auf n –, während die Permutation nur besagt, dass jede der Stellen n Möglichkeiten hat
   4. Probe: 220 ist nicht 120 und 1000 ist nicht 720, ein Umlegen des Schalters hat beide Zeilen bewegt

   Dass beide Zeilen sich ändern, ist der Sinn dieses Schalters und nicht sein Detail. Eine Umsetzung, die nur die Kombination umstellt, druckte 220 und 720 nebeneinander, zwei Zahlen, die beide vernünftig aussehen und doch zwei verschiedene Regelwerke beschreiben. Zu beachten ist außerdem, dass die Permutation zu einer Potenz wird und nicht zu einem fallenden Produkt: Mit Wiederholung hat jede der r Stellen n Möglichkeiten, gezählt wird also nʳ, statt bei jeder Entnahme eine Möglichkeit weniger zu haben.

3. Fünf Karten aus 52

   1. Eine Hand zählt die Reihenfolge nicht, gesucht ist also C(52,5) = 52! / (5! × 47!)
   2. Zuerst werden die fünf fallenden Faktoren multipliziert: 52 × 51 × 50 × 49 × 48 = 311.875.200
   3. Dann wird durch 5! = 120 geteilt: 311.875.200 / 120 = 2.598.960
   4. Die zweite Zeile ist genau der Zwischenwert vor dieser Division – „eine Hand ist die Zahl der geordneten Austeilungen geteilt durch die Permutation“ sagt nichts anderes

   Die 2.598.960 sind der Nenner, durch den jede Pokerwahrscheinlichkeit geteilt wird, und die am häufigsten nachgeschlagene Zahl dieser Seite. Die beiden Zeilen lohnen den Vergleich, weil die Permutationszeile wörtlich der Zähler vor der Division durch 5! ist: Fünf Karten lassen sich auf 311.875.200 geordnete Arten austeilen, und jede Hand entspricht davon 120. Zu verstehen, dass die Zahl ohne Reihenfolge die Zahl mit Reihenfolge geteilt durch die Permutation ist, ist der schnellste Weg, die beiden Zeilen auseinanderzuhalten.

4. Sechs aus sechs: eine einzige Kombination, 720 Permutationen

   1. Alles zu entnehmen geht auf genau eine Art, also ist C(6,6) = 1
   2. Die Permutation ist die Gesamtzahl der Anordnungen von sechs Dingen: P(6,6) = 6! = 720
   3. Zwischen den Zeilen liegt der Faktor 720 = 6!, also genau die r!-Beziehung für r = n

   Bei r = n liegen die beiden Zeilen am weitesten auseinander, und die Kombinationszeile fällt auf 1 zusammen – wenn alles entnommen wird, gibt es die Frage „welche davon“ nicht mehr. Der Vergleich mit der Pokerhand von oben ist nützlich: Dort liegt der Faktor bei 120, hier bei 720, und geändert hat sich nur, wie viele Anordnungen jede einzelne Auswahl zulässt. Wer eigentlich die Permutationszeile gebraucht hätte, sieht hier den Fehler in seiner deutlichsten Form.

5. Fünf Kugeln aus drei Sorten: r größer als n

   1. Fünf Kugeln aus drei Sorten, ohne Reihenfolge, mit Wiederholung: C = C(3 + 5 − 1, 5) = C(7,5) = 21
   2. Wird zusätzlich die Reihenfolge gezählt, ist P = 3⁵ = 243
   3. Beide Zahlen gelten nur mit Wiederholung – wird der Schalter ausgeschaltet, lassen sich aus drei Dingen keine fünf entnehmen, und die Seite lehnt diese Eingabe ab

   Diese Zeile macht deutlich, dass der Schalter eine Frage der Richtigkeit ist und keine bequeme Zusatzoption. Aus drei Dingen fünf zu entnehmen ist ohne Wiederholung nicht möglich, deshalb verweigert die Seite bei ausgeschaltetem Schalter die Antwort; eingeschaltet liefert dieselbe Eingabe zwei ganz gewöhnliche Zahlen. Die Kombinationszeile erklärt nebenbei, warum die Formel r − 1 auf den Vorrat addiert: Wiederholung zuzulassen vergrößert den Vorrat, drei Sorten fünfmal zu wählen ist gleichbedeutend damit, aus sieben Dingen fünf auszuwählen.

Beide Anzahlen sind innerhalb einer gewissen Grenze exakte ganze Zahlen; jenseits dieser Grenze verweigert die Seite die Antwort, statt zu runden. Diese Zahlen wachsen außerordentlich schnell – fünfzig aus hundert hat etwa dreißig Stellen –, und die Gleitkommazahlen, mit denen gerechnet wird, können ab etwa der sechzehnten Stelle nicht mehr jede ganze Zahl exakt darstellen, ein so großer Zählwert käme also mit einem Anhang zurück, der normal aussieht und in den letzten Stellen falsch ist. Statt eine Zahl zu drucken, bei der niemand erkennen kann, wo der Fehler sitzt, wirft die Seite bei Zählungen außerhalb des exakten Bereichs einen Fehler; dieselbe Ablehnung gilt für einen Vorrat über tausend Elementen und für jede negative Entnahme. Zwei weitere Punkte: Diese Seite zählt nur – sie listet die Auswahlen nicht auf, druckt sie nicht einzeln hin und berechnet auch nicht die Wahrscheinlichkeit, eine bestimmte davon zu ziehen (dafür wäre die Zählung durch die Gesamtzahl zu teilen). Und der Schalter für die Wiederholung bedeutet allein, dass dasselbe Element mehrfach entnommen werden darf; er bildet nicht das dünner werdende Kartenblatt nach – das leistet bereits das fallende Produkt in den Formeln ohne Wiederholung.

Worin unterscheiden sich Kombination und Permutation?

Die Kombination zählt die Reihenfolge der Entnahme nicht mit, die Permutation tut es. Drei Personen aus zehn für eine Arbeitsgruppe auszuwählen ist eine Kombination, weil die Gruppe ABC dieselbe ist wie die Gruppe CBA; denselben drei Personen einen ersten, zweiten und dritten Preis zuzuteilen ist eine Permutation, weil die Preise unterschiedlich verteilt sind. Die beiden Zahlen liegen nie nahe beieinander: Die Permutation ist stets die Kombination mal der Fakultät von r, also mal der Zahl der Anordnungen, die die r entnommenen Dinge haben können. Diese Seite druckt beide Zeilen, damit dieser Faktor nicht geraten werden muss – bei drei Entnahmen ist er 6, bei fünf Entnahmen 120, und je weiter die beiden auseinanderliegen, desto unwahrscheinlicher fällt der Fehler von selbst auf.

Was bedeutet nCr auf dem Taschenrechner?

nCr ist die Kombination: n ist die Größe des Vorrats, r die Zahl der Entnahmen, und das Ergebnis ist die Zahl der Arten, diese ohne Berücksichtigung der Reihenfolge zu entnehmen – also die Zahl, die diese Seite in der Kombinationszeile ausgibt. Das danebenstehende nPr ist die Permutation mit Reihenfolge und entspricht der unteren Zeile. Um schnell zu entscheiden, welche der beiden eine Aufgabe verlangt, hilft eine Frage: Ändert sich das Ergebnis, wenn man zwei entnommene Dinge miteinander vertauscht? Wenn nicht, ist die Antwort nCr.

Was ändert sich, wenn die Wiederholung eingeschaltet wird?

Es ändern sich beide Formelsätze, und es ändert sich die Zulässigkeit. Ohne Wiederholung ist die Permutation ein fallendes Produkt – n × (n − 1) × … – und die Kombination teilt dieses Produkt durch r!; mit Wiederholung ist die Permutation einfach n hoch r, und die Kombination wechselt zur Zählung der Multimengen, für n Dinge in r Entnahmen also C(n + r − 1, r). Wirklich stolpern lassen einen die Zulässigkeitsregeln: Ohne Wiederholung ist ein r größer als n schlicht unmöglich und wird abgelehnt, mit Wiederholung ist es eine ganz normale Anfrage, etwa fünf Kugeln aus drei Sorten.

Warum beantwortet die Seite manche großen Eingaben nicht?

Weil die Antwort in den letzten Stellen falsch wäre und dabei nicht falsch aussähe. Diese Zählungen wachsen außerordentlich schnell – fünfzig aus hundert hat rund dreißig Stellen –, und die Zahlen, mit denen gerechnet wird, können ab etwa der sechzehnten Stelle nicht mehr jede ganze Zahl exakt darstellen. Jenseits dieser Grenze ist das Ergebnis eine benachbarte Zahl, die vorne richtig aussieht und hinten falsch ist; muss damit eine Wahrscheinlichkeit berechnet oder ein Bericht gefüllt werden, ist das schlimmer als keine Antwort. Deshalb wirft die Seite bei nicht exakt darstellbaren Zählungen einen Fehler – dieselbe Behandlung wie bei einem Vorrat über tausend Elementen und bei negativen Entnahmen.

Ist „mit Wiederholung“ dasselbe wie „mit Zurücklegen“?

Nicht ganz, denn in der Vorstellung vom Kartenblatt steckt eine zweite Bedeutung. Der Schalter sagt allein, dass dasselbe Element mehrfach entnommen werden darf, also dass die Möglichkeiten im Vorrat voneinander unabhängig sind. Bei Kartenfragen wird der Vorrat dagegen kleiner, sobald eine Karte entnommen ist, und diese Ebene steckt bereits im fallenden Produkt der Formeln ohne Wiederholung – eine Hand aus fünf Karten ist C(52,5) und nicht 52 hoch 5. Der Schalter regelt also, ob dasselbe mehrfach entnommen werden darf; dass der Vorrat kleiner wird, regeln die Formeln und nicht der Schalter.

Warum steht unter dem Rechner keine Tabelle zum Nachschlagen?

Weil eine solche Tabelle dem Ergebnisbereich zwangsläufig widersprechen würde. Die Tabelle, die hier nützlich wäre, hätte n in der einen und r in der anderen Richtung, und die Antwort im Ergebnisbereich wird aus den eingegebenen Werten für n und r berechnet – eine feste Tabelle lieferte bei derselben Eingabe also andere Zahlen. Die Seiten dieses Projekts, die tatsächlich Referenztabellen mitbringen, beschreiben jeweils eine von der Eingabe unabhängige feste Wertemenge – eine Klassengrenze, eine Standardskala – und nicht eine Rechnung über die Eingabe. Auf dieser Seite sind die beiden Zeilen im Ergebnisbereich die Antwort, und sie ändern sich mit jeder Eingabe.

• Kombination — DWDS, Digitales Wörterbuch der deutschen Sprache: der Terminus für die Auswahl ohne Berücksichtigung der Reihenfolge, den diese Seite durchgehend benutzt — Berlin-Brandenburgische Akademie der Wissenschaften
• Permutation — DWDS: der Terminus für die Auswahl mit Reihenfolge, also die zweite Zeile des Ergebnisbereichs — Berlin-Brandenburgische Akademie der Wissenschaften
• Fakultät — DWDS: der Terminus hinter dem Ausrufezeichen, das in beiden Formeln und im Faktor r! zwischen den beiden Zeilen steht — Berlin-Brandenburgische Akademie der Wissenschaften
• Combination — MathWorld: the number of ways to choose a subset of a given size without regard to order, also called the binomial coefficient and read as «n choose k»: the definition behind the combination row — Wolfram MathWorld
• Permutation — MathWorld: the rearrangement of the elements of an ordered list and the count of such arrangements for a given size: the definition behind the permutation row — Wolfram MathWorld
• Multichoose — MathWorld: the number of multisets of a given length drawn from a set of symbols, i.e. the counting the combination row switches to once repetition is allowed — Wolfram MathWorld