 \(\begingroup\)\(\newcommand{\IX}{\mathbb{X}}
\newcommand{\IW}{\mathbb{M}}
\newcommand{\politician}[1]{\text{Ich habe die Frage nicht verstanden. #1}}
\newcommand{\ba}{\begin{aligned}}
\newcommand{\ea}{\end{aligned}}
\newcommand{\bpm}{\begin{pmatrix}}
\newcommand{\epm}{\end{pmatrix}}
\newcommand{\bc}{\begin{cases}}
\newcommand{\ec}{\end{cases}}
\newcommand{\on}{\operatorname}
\newcommand{\ds}{\displaystyle}\)
Wie berechnet man "n über k"? Ganz einfach, könnte man sagen. Es ist n!
binomial(n;k) = -------------
k! * (n-k)!
mit n! = n*(n-1)*(n-2)* ... *2*1.
Also muß man 'nur' diese Formel ausrechnen. Für binomial(10;3) ergibt sich
10*9*8*7*6*5*4*3*2*1
--------------------- = (Taschenrechner) = 120
3*2*1 * 7*6*5*4*3*2*1
Man hätte vorher auch kürzen können
10*9*8*7*6*5*4*3*2*1 10*9*8
--------------------- = ------ = 5*3*8 = 120
3*2*1 * 7*6*5*4*3*2*1 3*2
Aber was ist z.B. mit Wie groß ist 2002! ?
Mein Taschenrechner kann das nicht mehr.
Nun kann man Binomialkoeffizienten rekursiv berechnen: ( n ) ( n-1 ) ( n-1 )
( k ) = ( k-1 ) + ( k )
also ( 2002 ) ( 2001 ) ( 2001 )
( 891 ) = ( 890 ) + ( 891 )
Diese Rekursionsformel ist für viele formale Rechnungen der Schlüssel, zur Berechnung taugt sie aber auch nicht. Der Speicherbedarf eines Programmes nach diesem Rekursionsverfahren ist gigantisch groß. Eine weitere Möglichkeit 2002 / 891 * 2001 / 890 * ... * (2002 - 891 +1)/1 Man faßt jeweils einen Faktor im Zähler und einen im Nenner zu einem Bruch zusammen und multipliziert die Quotienten - und erreicht damit, daß die Zahlen, mit denen man rechnet (hier sind das die Quotienten) alle eine ähnliche Größenordnung haben. Für manche Zahlen ist das noch ein beherrschbarer Ausdruck.
Für große n, wie 2002, ist auch diese Rechnung zwecklos. Das Ergebnis liegt ganz grob in der Größenordnung von Unendlich (sagt mein Taschenrechner). Teile und (be)-herrsche
Es gibt ein anderes exaktes und von der Rechenzeit schnelles Verfahren.
Dabei berechnet man die Primfaktorzerlegung von n!, k! und (n-k)! und kürzt die Exponenten. Beispiel: binomial(27;15)
= 27! / (15! * 12!)
= 2² * 3² * 5 * 13 * 17 * 19 * 23
denn 27! = 223 * 313 * 56 * 7³ * 11² * 13² * 17 * 19 * 23
15! = 211 * 36 * 5³ * 7² * 11 *13
12! = 210 * 35 * 5² * 7 *11 Bleibt die Frage, wie man zu den Primzahlexponenten in der Zerlegung der Fakultät kommt. Dafür gibt es eine Formel aus der Zahlentheorie, die auf Legendre zurückgeht. Wir wissen, daß jede positive ganze Zahl eine eindeutige Primfaktorzerlegung hat. Es gibt zu einer positiven ganzen Zahl m somit Primzahlen p1, p2, ..., pk und Exponenten e(pi), i=1,...,k, für eine (bis auf die Reihenfolge der pi) eindeutige Darstellung der Form: m = Pi pie(pi) Die Faktorisierung großer Zahlen ist im allgemeinen nicht leicht zu finden. Aber die Primfaktoren von n! sind leicht zu berechnen. Satz
In der Primfaktorzerlegung von m = n! gilt für alle Primzahlen p:
e(p) = [n/p] + [n/p²] + [n/p³] + [n/p4] + ...
Mit [..] bezeichne ich die "größte ganze Zahl kleiner gleich ..."
Probiere diese Formel am kleinen Beispiel: Die 2 hat in der Primfaktorzerlegung von 27! den Exponenten: e(2) = [27/2] + [27/4] + [27/8] + [27/16] = 13 + 6 + 3 + 1 = 23 Die 3 hat den Exponenten: e(3) = [27/3] + [27/9] + [27/27] = 9 + 3 + 1 = 13 Es ist schon zu sehen, das Verfahren erfordert die Primzahlen bis m zu kennen. Ein Programm zur Faktorisierung von m! muß zunächst einmal eine Primzahltabelle erstellen, etwa mit dem Sieb des Eratosthenes. Dann durchläuft man die Liste der Primzahlen und berechnet die e(p) für alle p kleiner gleich m. Berechne die Primzahlpotenzen pk und die Quotienten [m/pk] solange, bis pk > m wird.
Die Summe der Quotienten ist der Exponent der Primzahl p in der Faktorisierung von m!. Algorithmus zur Faktorisierung von m!:
\sourceon Pseudo-C
Vorbereitung: bestimme die Menge P(m) aller Primzahlen <= m
Schleife 1 über die Primzahlen p aus P(m)
 Setze sum := 0
Setze quotient := floor(n/p)
 Schleife 2 bis Abbruch
  if(quotient<1) Abbruch Schleife 2
  add := floor(n/div)
  sum := sum + quotient
quotient := floor(quotient/p)
 Ende Schleife 2
 print p "^" sum
Ende Schleife 1
\sourceoff
Den beschriebenen Algorithmus habe ich mit PHP implementiert.
Zum Programm. Warum ist die Formel von Legendre richtig? Kein Primteiler von m! ist größer als m.
Von den m Faktoren in m! sind [m/p] Faktoren einmal durch p teilbar.
Durch p² sind weitere [m/p²] Faktoren teilbar, durch p³ sind [m/p³] Faktoren teilbar usw.
Die Anzahl der Faktoren p in der Primfaktorzerlegung ist also gleich der Summe dieser Anzahlen. Wo kann man mit diese Formel noch anwenden? Gelegentlich werde Aufgaben gestellt wie die folgende: Auf wieviele Nullen endet 2002! ? Antwort: Eine Null bedeutet, daß die Zahl durch 10 teilbar ist.
Wie oft ist 2002! durch 10 teilbar? Sie ist so oft durch 10 teilbar, wie in der Primfaktorzerlegung genügend Zweien und Fünfen vorkommen, um den Faktor 10 zu bilden. Weil es häufiger den Primfaktor 2 als den Faktor 5 gibt, ist diese Anzahl allein durch die Anzahl der Fünfen bestimmt. Wieviele Fünfen sind in der Primfaktorzerlegung von 2002!? Es sind [2002/5] + [2002/25] + [2002/125] + [2002/625] = 499 Fünfen. Also endet 2002! auf 499 Nullen.
\(\endgroup\)
| 
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Printer-friendly version
Get link to this article
Comments
Für diesen Artikel gibt es keine pdf-Datei
Dieser Artikel ist im Verzeichnis der 
