Formel für Anzahl der Möglichkeiten für eine Summe...

Neue Frage »

Pangaia Auf diesen Beitrag antworten »
Formel für Anzahl der Möglichkeiten für eine Summe...
Hallo,

ich versuche schon seit einiger Zeit durch Stichwortspielereien in der Googlesuche
n die Lösung meines Problems zu kommen. Nue leider nicht sonderlich erfolgreich.
Dafür bin ich bei dieser Suche über dies Forum hier gestolpert und ich stelle mal das
Problem ein:

Gegeben sind die natürlichen Zahlen von 1 bis n
Jetzt habe ich eine Summe s aus diesen natürlichen
Zahlen sowie i was die Anzahl der verwendeten
Summanden entspricht. Verwendet werden darf
aus dem Zahlenbereich 1 bis n eine Zahl nur einmal.
(also 1 bis 10, Summe 11, 3 Summanden: 1/2/8;
1/3/7; 1/4/6; 2/3/6; 2/4/5 -> 5 ist die gesuchte
Zahl)

Durch brute-force mit einem selbstgeschriebenen
Programm ist es für mich kein Problem an eine
Lösunge zu kommen, nur muß dies Programm den
Gegebeheiten immer angepasst werden (i einspricht
dabei die Anzahl der Schleifen die ich programmieren
[es gibt da als Programmiertrick verschachteltes Unter-
programm als Alternative] muß....und je mehr Schleifen
und je größer n, um so länger läuft das Programm)

Kann jemand mit einer Formel dazu aufwarten?
HAL 9000 Auf diesen Beitrag antworten »

Führen wir erstmal eine Bezeichnung ein, mit der wir arbeiten können: Sei



die von dir gesuchte Anzahl aller -elementigen Teilmengen von , deren Elementsumme gleich einem vorgegebenen Wert ist.


Mit einer expliziten Darstellung von kann ich (noch?) nicht dienen, wohl aber mit einem rekursiven Zugang, der schon mal wesentlich schneller ist als das einzelne Abzählen, gerade für große Werte von .

Fangen wir mit den Startwerten der Rekursion an: Für ist alles klar, da ist

,

ebenso klar ist im Fall

für sowie ,

einfach indem man die Summe der kleinsten sowie größten Werte aus in Rechnung stellt.

Für alle anderen Werte mit gilt nun iterativ

,

wobei der erste Summand diejenigen Teilmengen zählt, die eine 1 enthalten, und der zweite Summand dann die Teilmengen ohne 1.


Auf dein Beispiel angewandt:



macht also summa summarum .


Was hier so furchtbar aufwändig wirkt, ist aber leicht programmierbar, und führt dann etwa bei Berechnungen wie



schneller zum Ergebnis als die einfache Zählerei. Augenzwinkern


Bleibt die Frage, ob man (*) zusammen mit den Startwerten irgendwie doch in eine explizite Darstellung überführen kann? Ich sehe es momentan nicht, aber vielleicht hat ja jemand anderes eine geniale Eingebung.
 
 
Mystic Auf diesen Beitrag antworten »

Ja, ich kann nur bestätigen, dass deine Rekursionsvorschriften für die Berechnung durch ein Programm hocheffizient sind (s.u. eine Implementierung in Maple), sehe aber -jedenfalls für mich -keine realistische Chance, das in eine explizite Formel umzumünzen... Augenzwinkern

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
A:=proc(n,m,s) 
   option remember;
   if s<m*(m+1)/2 or s>n*m-m*(m-1)/2 then return 0 end if;
   if m=1 then return 1 end if;
   A(n-1,m-1,s-m)+A(n-1,m,s-m)
end:  

t:=time():A(200,10,1000);time()-t;
                          49427802479445
                             0.889
Pangaia Auf diesen Beitrag antworten »

Danke für die Rekursion. Die hilft schon etwas weiter.
Mystic Auf diesen Beitrag antworten »

Hier noch zwei Anmerkungen zu dieser Aufgabe...

1. Eine sinnvolle Relaxation des Problems in Hinblick auf eine explizite Formel könnte sein, dass man die Menge {1,2,..,n}, aus der die Summanden entnommen werden durch ersetzt wird... Dies vor allem auch deshalb, da dies mit Ausnahme der endlichen vielen n mit n< s -m(m-1)/2 de facto ohnehin der Fall ist und dann n nur unnötig durch alle Rekursionen "mitgeschleppt" wird...

2. Der Algebraiker sieht natürlich mit einem Blick, dass hier einfach nur der Koeffizient von des Polynoms



gesucht wird, der z.B. in Maple sofort mittels

code:
1:
A:=proc (n,m,s) coeff(coeff(product(1+x*y^k,k=1..n),x^m),y^s) end: 

berechnet werden kann... Dieses Programm ist dann aber vermutlich zugleich Rekordhalter für das sowohl kürzeste, also auch ineffizienteste Programm zur Berechnung der gesuchten Anzahl... Big Laugh
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
Dieses Programm ist dann aber vermutlich zugleich Rekordhalter für das sowohl kürzeste, also auch ineffizienteste Programm zur Berechnung der gesuchten Anzahl... Big Laugh

Jetzt schreibst du auch schon die bisher mir vorbehaltenen Kommentare selbst. Respekt
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Jetzt schreibst du auch schon die bisher mir vorbehaltenen Kommentare selbst. Respekt

Mir scheint, du bist kein Freund von Quick-and-dirty-solutions... Big Laugh
Pangaia Auf diesen Beitrag antworten »

So...und mit der Variante habt ihr mich überfordert...

...das übersteigt meine Schulkenntnisse
Nurtopek Auf diesen Beitrag antworten »

7 Jahre später ein herzliches Dankeschön - und mein erstes Posting bei Matheboard.de wo ich seit einer halben h Mitglied bin.

Ich habe beim Lösen eines Geocache Mysteries die Aufgabe zu finden, wieviel Möglichkeiten der Summierung es für 33 Summenden (natürliche Zahl >=10) gibt, um auf die Summe von 3333 zu kommen. Die Bing Suche hat mich sofort hierher geführt.

Implementierung erfolgt mit Python. Danke, Danke, Dankeschön
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Nurtopek
wieviel Möglichkeiten der Summierung es für 33 Summenden (natürliche Zahl >=10) gibt, um auf die Summe von 3333 zu kommen.

Entscheidend für das hier im Thread diskutierte Problem war aber, dass die Summanden sämtlich voneinander verschieden sind - das ist bei dir auch so (trotzdem jetzt in deinem Text nichts dazu steht) ? verwirrt

Ohne diese Forderung wird das ganze wesentlich leichter, es reicht dann eine kombinatorische Grundformel. Augenzwinkern


EDIT: Ok, stimmt doch nicht ganz, das hab ich verwechselt: Wirklich einfach wird die Anzahlberechnung nur bei Zerlegungen mit Berücksichtigung der Reihenfolge (d.h. Tupel). Ohne Berücksichtigung landet man bei der Partitionsfunktion, die im wesentlichen auch nur rekursiv zugänglich ist.
Nurtopek Auf diesen Beitrag antworten »

Na klar ist das so, sonst hätte ich doch nicht "danke" gesagt Augenzwinkern Augenzwinkern

einziger Unterschied, es beginnt nicht mit 1 sondern 10.

Deinen Beitrag und das Board finde ich auch toll, weil es mich zu den Wurzeln zurück geführt hat. Habe von1964 bis 1971 Mathematik an der TU Dresden studiert. Ab 5. Semester Fachrichtung "Kybernetik und Rechentechnik" - so hieß Informatik damals. Daß jetzt vieles anders ist habe ich festgestellt, als ich vor ca. 10 Jahren mal neben einer Mathestudentin im Zug saß. Ihre Analysisaufzeichnungen waren für mich "Böhmische Dörfer" - obwohl ich damals eine 1 hatte.

gern übermittle ich Dir auch den Text der Aufgabe dazu - wie gesagt, es geht um einen sogenannten Mysteriecache.:

Text auf Wunsch des Schreibers nachträglich gelöscht. Steffen

Viele herzliche Grüße aus DD
HAL 9000 Auf diesen Beitrag antworten »

Da es hier bei dem Problem keine Obergrenze für die Einzelschrittgröße gibt, kann man auch mit der normalen (und oben bereits verlinkten) Partitionsfunktion arbeiten, die zählt die Anzahl der Möglichkeiten, die Zahl in genau positive ganze Summanden zu zerlegen.

Wenn hier die Wegstrecke der Schnecke an Tag bezeichne, dann kommt man aus Forderung via Substitution zur Bedingung , mit dann

.

Die von dir gesuchte Anzahl ist demnach .
Steffen Bühler Auf diesen Beitrag antworten »

Willkommen im Matheboard, Nurtopek!

Ein kurzer Hinweis: wir geben prinzipiell keine Hilfestellung bei Geocaching-Aufgaben, weil wir Respekt vor dem Owner des Caches haben.

Viele Grüße und viel Spaß noch im Board
Steffen
Nurtopek Auf diesen Beitrag antworten »

in aller Eile von unterwegs:

Danke Steffen. Den Cachetext hätte ich nicht kopieren dürfen. Was kann ich jetzt machen? Edit bzw. löschen ist nur 15 min möglich. Entweder Textpassage raus, oder schlimmstenfalls den gesamten Beitrag löschen.

Danke - Nurtopek
HAL 9000 Auf diesen Beitrag antworten »

"Korrigieren" ??? Meinst du nicht eher "kopieren" ? verwirrt
Steffen Bühler Auf diesen Beitrag antworten »

Ok, ich lösche dann die Passage. HALs Komplettlösung hat dann zwar keine zugrundeliegenden Daten mehr, aber sei's drum.

Viele Grüße
Steffen
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »