Binomialkoeffizient

Algorithmus zur effizienten Berechnung

Für ganzzahlige n existiert ein effizienter Algorithmus, der die Produktformel

des Binomialkoeffizienten anwendet. Auf Grund des stetigen Wechsels zwischen Multiplikation und Division wachsen die Zwischenergebnisse nicht unnötig an. Zusätzlich sind auch alle Zwischenergebnisse natürliche Zahlen.

Um unnötigen Rechenaufwand zu vermeiden, berechnet man im Fall k > n/2 den Binomialkoeffizienten:

Der folgende Pseudocode verdeutlicht die Berechnung: binomialkoeffizient(n, k) 1 wenn k = 0 dann rückgabe 1 2 wenn 2k > n 3 dann führe aus ergebnis binomialkoeffizient(n, n-k) 4 sonst führe aus ergebnis n-k+1 5 von i 2 bis k 6 führe aus ergebnis ergebnis (n - k + i) 7 ergebnis ergebnis : i 8 rückgabe ergebnis

Die Rechenmethode nutzen auch Taschenrechner, wenn sie die Funktion anbieten. Sonst wäre die Rechenkapazität für n=69 erschöpft. Die Beschriftung der Funktionstaste mit nCr beschreibt die Reihenfolge der Eingabewerte in Infixnotation; zunächst Anzahl der Elemente n, dann die Funktionstaste Combinations, dann Anzahl der gewählten Objekte r (im Artikel mit k abgekürzt).

Die Berechnung nPr (engl. Permutations) berücksichtigt die Permutationen der r Elemente, die Division durch r! unterbleibt:

P(n,r) = n! / (n - r)!.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Binomialkoeffizient aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung