Abt. Ungeordnete Partitionen natürlicher Zahlen
==============================
Die Zahl 4 kann auf p(4)=5 verschiedene Arten zusammengesetzt werden:
(1) 4, (2) 3+1, (3) 2+2, (4) 2+1+1, (5) 1+1+1++1. Das war ja leicht. Aber wie ist das bei der Zahl 114 ? Oder bei 1024 ?
Die Anzahl der unterschiedlichen Zusammensetzungsarten bei ungeordneter Anordnung der Teilsummanden und mit erlaubter Wiederholung nennt sich Partitionszahl. Sie spielt gleich in mehreren Gebieten der Mathematik eine Rolle, etwa bei topologischen Fragen, Gruppentheorie, auch in der Graphentheorie. Manche Beweise müssen z.B. alle Partitionen eines Problems einzeln behandeln, um als gültig angesehen zu werden.
Naja, so weit wollen wir´s ja nicht treiben. Anbei ein Progi, daß einige genaue Werte sowie eine bekannte Abschätzungsformel für größere Zahlen enthält.
Gruss
Windowtitle "Anzahl der ungeordneten Partitionen einer natürlichen Zahl"
Windowstyle 24:Window 0,0-%maxx,%maxy:showmax:cls rgb(190,190,190):font 2
declare z!,p!,antw$,p$,part$[],part![],max&,n&,sum!,k&,i1&,i2&
p$="1,1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,297,385,490,627,\
792,1002,1255,1575,1958,2436,3010,3718,4565,5604,6842,8349,10143,\
12310,14883,17977,21637,26015,31185,37338,44583,53174,63261,75175,\
89134,105558,124754,147273,173525,204226,239943,281589,329931,386155,\
451276,526823,614154,715220,831820,966467,1121505,1300156,1505499,\
1741630,2012558,2323520,2679689,3087735,3554345,4087968,4697205,\
5392783,6185689,7089500,8118264,9289091,10619863,12132164,13848650,\
15796476,18004327,20506255,23338469,26543660,30167357,34262962,\
38887673,44108109,49995925,56634173,64112359,72533807,82010177,\
92669720,104651419,118114304,133230930,150198136,169229875,190569292,\
214481126,241265379,271248950,304801365,342325709,384276336,431149389,\
483502844,541946240,607163746,679903203,761002156,851376628,952050665"
part$[]=explode(p$,","):part![]=val(part$[&index]):max&=sizeof(part![]):clear part$[]
Nochmal:
Print "\n Zahl = ";:input z!:print
if z!<0:p!=0:print " Von negativen Zahlen gibt es keine Partitionen!":goto "nochmal"
endif
if (z!>=0) and (z!<115)
p!=val(substr$(p$,int(z!+1),",")):goto "showit"
else
SELECT z!
'caseof 2:p!=2
'caseof 4:p!=5
'caseof 8:p!=22
'caseof 16:p!=231
'caseof 32:p!=8349
'caseof 64:p!=1741630
'caseof 100:p!=190569292
caseof 128:p!=4351078600
caseof 200:p!=3972999029388
caseof 256:p!=365749566870782
caseof 512:p!=4453575699570940947378
caseof 1024:p!=61847822068260244309086870983975
'caseof 2048:p!="18116048323611252751541173......020513022685"
OTHERWISE
p!=round( (exp(1)^(Pi()*sqrt(z!*2/3))) / (4*z!*sqrt(3)) ,0)
Print " Gemäß Näherung von Hardy & Ramanujan [1918]: \n"
print " Von ";format$("%g",z!);" gibt es ungefähr ";format$("%g",p!);
print " ungeordnete Partitionen."
goto "nochmal"
ENDSELECT
endif
showit:
print " Von ";format$("%g",z!);" gibt es ";format$("%g",p!);" ungeordnete Partitionen."
Goto "Nochmal"
Alles anzeigen