Combination
Eine Kombination zählt die Arten, k Elemente aus n ohne Berücksichtigung der Reihenfolge zu wählen, C(n,k)=n!/(k!(n-k)!), also der Binomialkoeffizient.
Zweck
Ungeordnete Auswahlen zählen — eine Grundlage der Kombinatorik und Wahrscheinlichkeitstheorie.
Mechanismus
C(n,k) = n!/(k!(n-k)!) = C(n,n-k). Rekurrenz: C(n,k)=C(n-1,k-1)+C(n-1,k) (Pascalsches Dreieck). Für große Zahlen Logarithmen oder die Rekurrenz verwenden, um Überläufe zu vermeiden. C(n,0)=1, C(n,n)=1.
Anwendungsfälle
- Wahrscheinlichkeitsberechnung (Binomialverteilung)
- Kombinatorische Aufzählung
- Binomialkoeffizienten
- Hypergeometrische Verteilung
Beispiele
- Eingabe
C(5,2)=5!/(2!3!)=10Output10Choosing 2 of 5, unordered
Häufige Fehler
- Computing factorials directly overflows
- Use the recurrence or logarithms
Verwandte Begriffe
Permutation
Eine Permutation zählt die geordneten Wege, k aus n Elementen zu wählen, P(n,k)=n!/(n-k)!; die Anzahl vollständiger Permutationen ist n!. GLOSSAR
Factorial
Die Fakultät n! = n×(n-1)×...×1 ist die Grundlage von Permutationen und Kombinationen; sie wächst extrem schnell, 20! überschreitet bereits den 64-Bit-Integer-Bereich. GLOSSAR