| Autor |
Beitrag |
    
Carmichael (Carmichael)
| | Veröffentlicht am Dienstag, den 20. Februar, 2001 - 22:54: | 
|
Weiß jemand, ob es eine explizite Formel gibt, die beschreibt, auf wie viele Weisen eine natürliche Zahl n als Summe natürlicher Zahlen darstellbar ist, wenn man nur zwischen Wahl der Summanden und nicht zwischen Reihenfolge unterscheidet?
also: 5 = 5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1; |
Michael
| | Veröffentlicht am Samstag, den 03. März, 2001 - 09:57: |
|
Hallo Carmichael!
Ich hab gestern mal folgendes Konstrukt "zusammengewurschtelt". Solltest du ein Gegenbeispiel haben, dann meld dich, hab bis 7 die Richtigeit der Formel überprüft.
Also: Ich benutze im folgenden die Gaußklammer [x] und die Signumfunktion sgn(x).
R(n)=sgn(n-2)*[n/2]+1+sgn(n-1)*(1+0.5*(n-3)*(n-2))
R(1)=1 ; R(2)=2 ; R(3)=3 ; R(4)=5 usw...
R(n) gibt jeweils die Anzahl der "Repräsentationen" für die Zahl n an.
P.S.: Wie gesagt, sehr toll sieht die Formel nicht aus, meld dich also, wenn du ein Gegenbeispiel findest!
mfg, Michael :-) |
Martin (Martin243)
| | Veröffentlicht am Samstag, den 03. März, 2001 - 10:28: |
|
Das kannst du vergessen, Michael. Ich glaube, das ist ein ziemlich hoffnungsloses Unterfangen, denn man müsste deine Formel bei bestimmten Zahlen immer wieder erweitern, da es immer wieder Sprünge gibt.
Du wolltest ein Gegenbeispiel. Hier nur eines von unendlich vielen:
Die Zahl 10 lässt sich auf 42 (oder mehr, falls ich mich verzählt habe) Arten zerlegen, währen deine Formel ergibt:
R(10) = sgn(10-2)*[10/2] + 1 + sgn(10-1)*(1+0,5*(10-3)(10-2))
= sgn(8)*[5] + 1 + sgn(9)*(1+0,5*7*8)
= 1*5 + 1 +1*29
= 35
Carmichael, könnte es sein, dass man hierfür etwas anderes braucht? Etwas Komplizierteres? |
Michael
| | Veröffentlicht am Samstag, den 03. März, 2001 - 10:47: |
|
Hallo Martin!
Ich kann dir zumindest meine Idee erklären, an das Problem ranzugehen. Die Zahl n besteht minimal aus einer Summe aus 1 Glied (die Zahl selbst) und maximal aus einer Summe bestehend aus n Summanden (n*1). Also "zählt" man einfach alle Summen, die 1,2,3...,n Summanden aufweisen.
Das ist zumindest meine Grundidee. Wie klingt das?
mfG, Michael :-) |
Martin (Martin243)
| | Veröffentlicht am Samstag, den 03. März, 2001 - 11:09: |
|
Genau das habe ich mir auch gedacht. Und genau daran ist es auch gescheitert. Denn mit jeder nächsthöheren Zahl wächst auch Anzahl der maximal möglichen Summanden. Wenn man also die Gesamtsumme der Zerlegungen errechnen will, muss man seine Formel jedesmal erweitern. Und das ist (glaube ich) nicht so ohne Weiteres möglich. |
Carmichael (Carmichael)
| | Veröffentlicht am Samstag, den 03. März, 2001 - 15:19: |
|
Ja, also ich kenn auch keine explizite Darstellung, deshalb hab mein Problem auch hier gepostet.
Eine rekursive Darstellung findest sich allerdings leicht, vielleicht hilft euch die weiter:
für k<=[1/2*(n+1)]<-abgerundet:
a(n+1,k) = a(n+1-k,k) + a(n+1-k,k+1) + .... +
+ a(n+1-k,n+1-k);
für [1/2*(n+1)] < k < n+1:
a(n+1,k) = 0;
für k = n+1:
a(n+1,k) = 1;
b(n) = a(n,1) + a(n,2) + .... + a(n,n);
b(n) bezeichnet die Möglichkeiten der Darstellung von n als Summe.
[ a(n,k) bezeichnet die Möglichkeiten der Darstellung von n als Summe mit größtem Summanden k ] |
Martin
| | Veröffentlicht am Samstag, den 03. März, 2001 - 21:20: |
|
Viele Grüße,
Martin |
|
