Kombinationen ohne Wiederholung

Kombinationen ohne Wiederholung beantworten eine grundlegende Zählfrage der Statistik und der diskreten Mathematik: Bei n verschiedenen Elementen — wie viele unterschiedliche Gruppen der Größe k können Sie bilden, wenn kein Element zweimal vorkommt und die Reihenfolge der Auswahl keine Rolle spielt? Diese Größe ist der Binomialkoeffizient C(n,k), auch n über k geschrieben. Es gibt keine Stichprobe, kein Netz und keine datumsabhängige Rundung: jedes gültige Paar (n, k) ergibt jedes Mal dieselbe ganze Zahl.

Was Kombinationen ohne Wiederholung zählen

Kombinationen ohne Wiederholung zählen, auf wie viele Weisen Sie eine Teilmenge von k Elementen aus einem Vorrat von n verschiedenen Elementen wählen können, wenn jedes Element höchstens einmal vorkommt und die Reihenfolge der Auswahl keine Rolle spielt. In der Unterrichtssprache heißt das n über k; in der Statistiknotation ist es der Binomialkoeffizient C(n,k). Die klassische Identität besagt, dass C(n,k) der Fakultät von n geteilt durch die Fakultät von k mal die Fakultät von (n minus k) entspricht.

Dieselbe Größe erscheint als Koeffizient in der Binomialentwicklung von (x plus y) hoch n und als Anzahl der k-Teilmengen einer n-elementigen Menge. Weil die Reihenfolge ignoriert wird, ist Alice und danach Bob dieselbe Kombination wie Bob und danach Alice; die Anzahl ist daher strikt kleiner als die zugehörige Permutation P(n,k), sobald k mindestens zwei ist. Weil Wiederholung verboten ist, können Sie dieselbe Person nicht zweimal ziehen — das ist der Unterschied zu Kombinationen mit Wiederholung, auch Multimengen-Kombinationen genannt, deren Anzahl C(n+k−1, k) beträgt.

Randfälle gehören zur Definition: C(n,0) und C(n,n) sind beide eins, C(n,1) gleicht n, und C(0,0) ist eins nach der Konvention des leeren Produkts. Ist k größer als n, gibt es keine k-Teilmenge einer n-Menge; dieser Rechner lehnt das Paar ab, statt null oder einen verallgemeinerten Binomialwert zurückzugeben.

Die Implementierung zieht niemals Stichproben, hängt niemals von der Uhr ab und rundet niemals: sie wertet das reduzierte Produkt von (n minus k plus eins) bis n aus, schrittweise geteilt durch eins bis k, mit exakter BigInt-Arithmetik, damit große Koeffizienten genaue ganze Zahlen bleiben und nicht die Mantisse einer Gleitkommazahl überlaufen.

Wie Sie n und k senden und die Anzahl lesen

Feld n ist die Größe des verschiedenen Vorrats — der obere Index von C(n,k) — und muss eine ganze Zahl von null bis zehntausend sein. Die Aliase total und N werden mit derselben Bedeutung akzeptiert. Feld k ist, wie viele Elemente Sie wählen, ohne eines zurückzulegen — der untere Index — und muss eine ganze Zahl von null bis n sein.

Die Aliase r, choose und K werden auf k abgebildet. Eine erfolgreiche Antwort wiederholt n und k als Zahlen, liefert count als Dezimalzeichenkette des exakten Kombinationswerts und enthält formula als die Identität C(n,k)=n! /(k!( n-k)!), damit Clients die Regel anzeigen oder protokollieren können, ohne sie fest einzucodieren.

Nutzen Sie den Endpunkt aus Hausaufgaben-Gradern, Wettbewerbs-Validatoren, Interview-Sandboxes, Tabellen-Anreicherungsjobs und Wahrscheinlichkeitsdemos, die C(n,k) vor jedem Gleitkommaschritt brauchen.

Einsatz in Unterricht, Stichproben und Wettbewerben

Statistiklehrkräfte nutzen Kombinationen ohne Wiederholung, wenn sie das Ziehen ohne Zurücklegen einführen: die Anzahl verschiedener k-Personen-Ausschüsse aus einer Klasse von n, die Anzahl der Hände mit k Karten aus einem 52er-Blatt oder die Anzahl der Wege, k defekte Einheiten aus einem Los von n für ein hypergeometrisches Modell zu ziehen. Diese Aufgaben teilen dieselbe ganze Zahl C(n,k); diese Seite ist für Menschen geschrieben, die genau diese Formulierung suchen, einschließlich Lernender, denen gerade gesagt wurde, sie nicht mit Kombinationen zu verwechseln, die Wiederholungen erlauben.

Klausurgeneratoren können den Erfolgspfad mit n gleich zehn und k gleich drei festnageln, was einhundertzwanzig ergibt, und den Ablehnungspfad mit jedem k, das n übersteigt, das fehlschlagen muss statt null zu liefern. Wettbewerbsprogrammierer und Interview-Sandboxes brauchen ein exaktes Orakel für Kombinationszählprobleme, ohne Multipräzisionsarithmetik in jedem Sprach-Harness neu zu implementieren. Geschwister-Landings können Permutationen, Kombinationen mit Wiederholung oder einen allgemeinen nCr-Rechner ansprechen; dieses Landing ist speziell die Formulierung ohne Wiederholung.

Kombinieren Sie die Anzahl mit eigenem Aufzählungscode, wenn Sie die Teilmengen selbst brauchen; diese Fähigkeit liefert nur die ganze Zahl.