Die Fakultät ist in der Mathematik eine Funktion, die einer natürlichen Zahl n das Produkt aller natürlichen Zahlen kleiner und gleich dieser Zahl zuordnet: n! = 1 * 2 * 3 * … * n. In der Kombinatorik spielt die Fakultät ebenfalls eine große Rolle, weil n! die Anzahl der Möglichkeiten ist, unterschiedliche Gegenstände der Reihe nach anzuordnen. Bei diesen Überlegungen kommen auch Binomialkoeffizienten ins Spiel. Sie geben an, auf wie viele verschiedene Arten man k Objekte aus einer Menge von n verschiedenen Objekten auswählen kann.
Sowohl Fakultäten als auch Binomialkoeffizienten weisen eine unangenehme Eigenschaft auf:
Ihre Werte können sehr schnell sehr groß werden – und sind damit in Variablen des Typs long
oder size_t
nicht mehr darstellbar. Ein Satz von Legendre verschafft hier Abhilfe:
Er befasst sich mit der Frage, wie oft ein Primfaktor in der Primfaktorzerlegung von n! für ein n ∈ N vorkommt –
um damit eine alternative Darstellung für Fakultäten und Binomialkoeffizienten zu ermöglichen, die das Problem des Überlaufs umgehen kann.
Wir betrachten in dieser Fallstudie die Berechnung von Fakultäten und Binomialkoeffizienten sowohl in ihrer klassischen Definition als auch mit Hilfe des Satzes von Legendre als Produkt von Primfaktorzerlegungen.
[Read More]