Permutations- & Kombinationsrechner

Permutationen ohne Wiederholung — P(n, k) = n! / (n−k)!. Auswahl von k aus n Elementen, bei denen die Reihenfolge wichtig ist und kein Element doppelt vorkommt. Beispiel: Wie viele Möglichkeiten gibt es, 3 von 10 Personen auf ein Podium für den 1., 2. und 3. Platz zu setzen.

Kombinationen ohne Wiederholung — C(n, k) = n! / (k!(n−k)!). Die Reihenfolge spielt keine Rolle, keine Wiederholungen. Beispiel: 5-Karten-Pokerblätter aus einem Deck mit 52 Karten.

Permutationen mit Wiederholung — nᵏ. k Plätze, die jeweils unabhängig voneinander aus n Möglichkeiten besetzt werden. Beispiel: Eine 4-stellige PIN aus 10 Ziffern = 10⁴ = 10000.

Kombinationen mit Wiederholung (Multisets) — C(n+k−1, k). k Elemente werden aus n Typen ausgewählt, Wiederholungen sind zulässig, die Reihenfolge spielt keine Rolle. Beispiel: Das Schöpfen von 3 Eiskugeln aus 5 Geschmacksrichtungen.

Eine Lotterie „6 aus 49“: Wie viele mögliche Ziehungen gibt es? Die Reihenfolge spielt keine Rolle und keine Zahl wiederholt sich — Kombinationen ohne Wiederholung.

C(49, 6) = 49! / (6! · 43!) = 13 983 816. Ein Tipp hat eine Gewinnchance von 1 zu 13,98 Millionen.

Im Gegensatz dazu hat eine 6-stellige Zahl mit erlaubten Wiederholungen = 10⁶ = 1 000 000 — viel bessere Gewinnchancen, aber weitaus kleinere Preispools, da die Anzahl der Möglichkeiten viel geringer ist.

Ein 8-stelliges Passwort aus 62 alphanumerischen Zeichen mit Wiederholungen: 62⁸ ≈ 2.18 × 10¹⁴. Deshalb benötigt ein Brute-Force-Angriff einen Offline-Hash, um vernünftige Passwörter zu knacken.

Pokerblätter: Gesamt = C(52, 5) = 2 598 960. Royal Flushes = 4. P(Royal) = 4 / 2598960 ≈ 1 zu 650 000.

Dasselbe Prinzip — „wähle k aus n“ — angewandt auf völlig unterschiedlichen Skalen.

C(n, k) = C(n, n−k). Die Auswahl der „eingeschlossenen“ Gruppe ist das gleiche Problem wie die Auswahl der „ausgeschlossenen“ Gruppe.

P(n, k) = k! · C(n, k). Permutationen entsprechen den Kombinationen multipliziert mit den Anordnungen der gewählten k Elemente.

n! wächst rasant: 10! ≈ 3,6 Millionen, 20! ≈ 2,4 × 10¹⁸, 70! überschreitet die IEEE 754 doppelte Genauigkeit. Dieser Rechner ist bei 170! (≈ 1,7 × 10³⁰⁶) gedeckelt — alles darüber hinaus ergibt „Infinity“.

Geordnete Probleme als ungeordnet behandeln. „Wie viele mögliche Podiumsplatzierungen?“ ist P, nicht C.

Wiederholungen vergessen. „Wie viele 7-stellige Telefonnummern?“ nutzt Wiederholung (10⁷); das Ranking von 7 verschiedenen Kandidaten hingegen nicht (7!).

Multinomialkoeffizienten — das Anordnen von n Elementen, von denen sich einige wiederholen (wie die Buchstaben in MISSISSIPPI), erfordert n! / (n₁! · n₂! · …). Dies wird nicht durch die vier obigen Regeln abgedeckt.

In der Informatik treibt die Kombinatorik die Algorithmenanalyse voran. Das Sortieren von n Elementen verfügt über n! mögliche Anfangsordnungen, weshalb vergleichsbasierte Sortierverfahren im Worst Case O(n log n) nicht unterschreiten können. Die Passwort-Entropie beträgt log₂(nᵏ) — dies entspricht der Anzahl der Sicherheitsbits bei einem k-Zeichen langen Passwort, das aus n Symbolen besteht.

In der Genetik bestimmen Kombinationen die Anzahl möglicher Genotypen. Bei zwei Allelen an einem einzelnen Locus gibt es C(2+2−1, 2) = 3 Genotypen (AA, Aa, aa). Über mehr als 20.000 Gene hinweg ist der kombinatorische Raum der menschlichen Variation astronomisch — weshalb sich Zwillingsstudien auf den Vergleich von eineiigen gegenüber zweieiigen Paaren konzentrieren, um genetische von Umwelteinflüssen zu isolieren.