Mathematik: Berechnung von großen Binomialkoeffizienten
Released by matroid on Fr. 28. Dezember 2001 17:26:14 [Statistics]
Written by matroid - 20608 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\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
( 2002
 891
)
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.

 
Dieser Artikel ist enthalten in unserem Buch
Mathematisch für fortgeschrittene Anfänger
Mathematisch für fortgeschrittene Anfänger

\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Algorithmen :: Kombinatorik :: Schüler aufwärts :: Zahlentheorie :: Leicht verständlich :: Mathematik :
Berechnung von großen Binomialkoeffizienten [von matroid]  
Wie berechnet man "n über k" möglichst effizient?
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 20608
 
Aufrufstatistik des Artikels
Insgesamt 4270 externe Seitenaufrufe zwischen 2012.01 und 2021.10 [Anzeigen]
DomainAnzahlProz
https://www.bing.com260.6%0.6 %
https://google.com110.3%0.3 %
https://duckduckgo.com240.6%0.6 %
https://google.de54912.9%12.9 %
http://google.de226853.1%53.1 %
http://google.es2235.2%5.2 %
http://google.se1503.5%3.5 %
http://google.ru1242.9%2.9 %
http://google.si1232.9%2.9 %
http://google.fr1212.8%2.8 %
http://google.no801.9%1.9 %
http://google.pl2345.5%5.5 %
http://google.dk721.7%1.7 %
http://google.lu661.5%1.5 %
https://google.it892.1%2.1 %
https://www.ecosia.org260.6%0.6 %
http://google.at140.3%0.3 %
http://google.it80.2%0.2 %
https://www.startpage.com40.1%0.1 %
http://google.com60.1%0.1 %
http://int.search.myway.com50.1%0.1 %
http://www.brainboard.eu50.1%0.1 %
https://startpage.com20%0 %
http://suche.web.de20%0 %
http://o2suche.aol.de10%0 %
http://search.conduit.com60.1%0.1 %
http://suche.gmx.net10%0 %
http://at.search.yahoo.com10%0 %
http://suche.t-online.de20%0 %
http://start.mysearchdial.com10%0 %
http://www.claro-search.com10%0 %
http://www.buzzdock.com10%0 %
http://www.bing.com90.2%0.2 %
http://www.amazon.de20%0 %
http://ecosia.org10%0 %
http://search.babylon.com30.1%0.1 %
http://r.duckduckgo.com10%0 %
http://de.search.yahoo.com10%0 %
http://www.search.ask.com10%0 %
https://metager.de10%0 %
http://wissen-unserer-zeit.de20%0 %
http://suche.aol.de10%0 %
http://search.sweetim.com10%0 %
http://search.incredibar.com10%0 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 13 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2021.10.13-2021.10.22 (2x)https://www.bing.com/
2021.10.06-2021.10.21 (11x)https://google.com/

Häufige Aufrufer in früheren Monaten
Insgesamt 4196 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2020-2021 (385x)https://google.de/
2012-2013 (307x)http://google.de/url?sa=t&rct=j&q=wie rechnet man n über k
2015-2018 (229x)http://google.de/url?sa=t&rct=j&q=
2013-2014 (223x)http://google.es/url?sa=t&rct=j&q=
2012-2013 (181x)http://google.de/url?sa=t&rct=j&q=wie rechnet man n über k aus
202005-11 (157x)https://google.de/url?sa=t
2013-2014 (150x)http://google.se/url?sa=t&rct=j&q=
201301-01 (131x)http://google.de/url?sa=t&rct=j&q=wie rechnet man x über y
201211-11 (124x)http://google.ru/url?sa=t&rct=j&q=binomialkoeffizient berechnen online
201401-01 (123x)http://google.si/url?sa=t&rct=j&q=
201210-10 (121x)http://google.fr/url?sa=t&rct=j&q=n über k berechnen online große zahle...
2012-2014 (117x)http://google.de/url?sa=t&rct=j&q=wie berechnet man n über k
201304-04 (107x)http://google.de/url?sa=t&source=web&cd=1&ved=0CBAQFjAA
201201-01 (95x)http://google.de/url?sa=t&rct=j&q=wieviele nullen endet die zahl 2012 fakult...
201503-03 (86x)http://google.de/url?sa=t&source=web&cd=5&ved=0CDAQFjAE
201205-05 (85x)http://google.de/url?sa=t&source=web&cd=11&ved=0CFsQFjAAOAo
201405-05 (84x)http://google.de/url?sa=t&source=web&cd=7&ved=0CD8QFjAG
201303-03 (83x)http://google.de/url?sa=t&rct=j&q=wie rechnet man n über k aus??
201302-02 (82x)http://google.de/url?sa=t&rct=j&q=wie rechnet man n!
201501-01 (80x)http://google.no/url?sa=t&rct=j&q=
201403-03 (79x)http://google.de/url?sa=t&rct=j&q=große zahlen rechnen n uber k
201307-07 (74x)http://google.pl/url?sa=t&rct=j&q=binomialkoffizient schnell berechnen
2014-2015 (73x)http://google.de/url?sa=t&rct=j&q=n über k berechnen
201212-12 (72x)http://google.dk/url?sa=t&rct=j&q=wie berechnet man binomialkoeffizienten
201206-06 (70x)http://google.de/url?sa=t&rct=j&q=zwei binomialkoeffizienten berechnung
201306-06 (69x)http://google.pl/url?sa=t&rct=j&q=binomialkoeffizient berechnen
201412-12 (68x)http://google.de/url?sa=t&rct=j&q=n über k berechnen ohne taschenrechner
201312-12 (66x)http://google.lu/url?sa=t&rct=j&q=
201407-07 (66x)http://google.pl/url?sa=t&rct=j&q=wie rechnet man n über k
201202-02 (64x)http://google.de/url?sa=t&source=web&cd=1&ved=0CCEQFjAA
201406-06 (57x)http://google.de/url?sa=t&source=web&cd=1&ved=0CCUQFjAA
201502-02 (55x)http://google.de/url?sa=t&source=web&cd=5&ved=0CC8QFjAE
201404-04 (55x)http://google.de/url?sa=t&rct=j&q=binomial quotient
202103-03 (49x)https://google.it
202012-12 (40x)https://google.it/
201506-06 (38x)http://google.de/url?sa=t&source=web&cd=1&ved=0CBwQFjAA
201408-08 (32x)http://google.de/url?sa=t&source=web&cd=1&ved=0CBsQFjAA
201308-08 (25x)http://google.pl/search?ei=SjEfUsfMMorKsgaps4D4Bw&q=n über k bei großem...
2020-2021 (23x)https://www.ecosia.org/
2020-2021 (21x)https://www.bing.com/
201510-10 (20x)http://google.de/url?sa=t&rct=j&q=berechnen zahlenwerte binomialkoeffizienten
201511-11 (16x)http://google.de/url?sa=t&source=web&cd=1&rct=j&q=grosse binomialkoeffiziente...
2020-2021 (16x)https://duckduckgo.com/
2019-2020 (14x)http://google.at/url?sa=t&rct=j&q=
201611-11 (11x)http://google.de/url?sa=t&rct=j&q=binomialkoeffizient primzahl
201602-02 (11x)http://google.de/url?sa=t&source=web&cd=1&rct=j&q=n über k große zahlen
2015-2018 (10x)http://google.de/
2016-2020 (9x)http://google.de/search?safe=off&ei=vqpQS9reBpSO_Ab03s2ZCg&sa=X&oi=spell&resc...
201509-09 (8x)http://google.de/url?sa=t&source=web&cd=1&rct=j&q=binomialkoeffiziennt groÃ...
201604-04 (8x)http://google.it/search?q=n über k online berechnen
202108-08 (7x)https://google.de
2020-2021 (7x)https://duckduckgo.com
201609-09 (5x)http://google.de/search?ei=77XrV72ME8zgjwP215SICg&q=binomialkoeffizient schri...
202103-09 (4x)https://www.startpage.com/
201806-10 (4x)http://google.com/

[Top of page]

"Mathematik: Berechnung von großen Binomialkoeffizienten" | 2 Comments
The authors of the comments are responsible for the content.

Re: Berechnung von großen Binomialkoeffizienten
von: Ex_Mitglied_40174 am: Sa. 18. Juni 2011 23:56:48
\(\begingroup\) Muss es nicht "Wieviele Fünfen sind in der Primfaktorzerlegung von 2002!?" anstatt "Wieviele Fünfen sind in der Primfaktorzerlegung von 2002?" gegen Ende des Textes heißen? \(\endgroup\)
 

Re: Berechnung von großen Binomialkoeffizienten
von: fru am: So. 19. Juni 2011 14:11:35
\(\begingroup\)Hallo Anonymer! Du hast natürlich Recht, das ist ein Flüchtigkeitsfehler. Ich habe seine Behebung schon in die Wege geleitet. (EDIT: Der Fehler ist mittlerweile korrigiert worden). Vielen Dank für den Hinweis und Deine Aufmerksamkeit! Liebe Grüße, Franz \(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]