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

02.06.2012, 21:08

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?

03.06.2012, 09:14

HAL 9000

Auf diesen Beitrag antworten »

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

$\begin{eqnarray*} A(n,m,s) := \left| \left\{ T\subseteq \{1,2,\ldots,n\} \Bigm| |T|=m \,\wedge\, \sum_{k\in T} k = s \right\} \right| \end{eqnarray*}$

die von dir gesuchte Anzahl aller $\begin{eqnarray*} m \end{eqnarray*}$ -elementigen Teilmengen $\begin{eqnarray*} T \end{eqnarray*}$ von $\begin{eqnarray*} \{1,2,\ldots,n\} \end{eqnarray*}$ , deren Elementsumme gleich einem vorgegebenen Wert $\begin{eqnarray*} s \end{eqnarray*}$ ist.

Mit einer expliziten Darstellung von $\begin{eqnarray*} A(n,m,s) \end{eqnarray*}$ 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 $\begin{eqnarray*} n,m,s \end{eqnarray*}$ .

Fangen wir mit den Startwerten der Rekursion an: Für $\begin{eqnarray*} m=1 \end{eqnarray*}$ ist alles klar, da ist

$\begin{eqnarray*} A(n,1,s) = \begin{cases} 1 & \;\mbox{für}\, 1\leq s\leq n \\ 0 & \;\mbox{sonst} \end{cases} \end{eqnarray*}$ ,

ebenso klar ist im Fall $\begin{eqnarray*} m>1 \end{eqnarray*}$

$\begin{eqnarray*} A(n,m,s) = 0 \end{eqnarray*}$ für $\begin{eqnarray*} s < \frac{m(m+1)}{2} \end{eqnarray*}$ sowie $\begin{eqnarray*} s > nm-\frac{m(m-1)}{2} \end{eqnarray*}$ ,

einfach indem man die Summe der $\begin{eqnarray*} m \end{eqnarray*}$ kleinsten sowie $\begin{eqnarray*} m \end{eqnarray*}$ größten Werte aus $\begin{eqnarray*} \{1,2,\ldots,n\} \end{eqnarray*}$ in Rechnung stellt.

Für alle anderen Werte mit $\begin{eqnarray*} m>1 \end{eqnarray*}$ gilt nun iterativ

$\begin{eqnarray*} A(n,m,s) = A(n-1,m-1,s-m) + A(n-1,m,s-m)\qquad (*) \end{eqnarray*}$ ,

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:

$\begin{eqnarray*} A(10,3,11) &=& A(9,2,8) + A(9,3,8) \\ A(9,2,8) &=& A(8,1,6) + A(8,2,6) = 1+A(7,1,4)+A(7,2,4) = 2+A(6,1,2)+A(6,2,2) = 3 \qquad \mbox{die mit der 1}\\ A(9,3,8) &=& A(8,2,5) + A(8,3,5) = A(8,2,5) = A(7,1,3)+A(7,2,3) = 1 + A(6,1,1) + A(6,2,1) = 2 \qquad \mbox{die ohne die 1} \end{eqnarray*}$

macht also summa summarum $\begin{eqnarray*} A(10,3,11)=3+2=5 \end{eqnarray*}$ .

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

$\begin{eqnarray*} A(200,10,1000) = 49\,427\,802\,479\,445 \end{eqnarray*}$

schneller zum Ergebnis als die einfache Zählerei. Augenzwinkern

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.

03.06.2012, 22:10

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

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

04.06.2012, 11:28

Pangaia

Auf diesen Beitrag antworten »

Danke für die Rekursion. Die hilft schon etwas weiter.

05.06.2012, 15:12

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 $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ 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 $\begin{eqnarray*} x^m y^s \end{eqnarray*}$ des Polynoms

$\begin{eqnarray*} \prod_{k=1}^n (1+xy^k) \end{eqnarray*}$

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

Big Laugh

05.06.2012, 15:23

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

Big Laugh

Jetzt schreibst du auch schon die bisher mir vorbehaltenen Kommentare selbst. Respekt

Respekt

Anzeige

05.06.2012, 15:51

Mystic

Auf diesen Beitrag antworten »

Zitat:

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

Respekt

Mir scheint, du bist kein Freund von Quick-and-dirty-solutions... Big Laugh

Big Laugh

09.06.2012, 11:15

Pangaia

Auf diesen Beitrag antworten »

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

...das übersteigt meine Schulkenntnisse

22.01.2018, 16:14

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

22.01.2018, 16:57

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

verwirrt

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

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.

23.01.2018, 10:41

Nurtopek

Auf diesen Beitrag antworten »

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

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

23.01.2018, 11:33

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 $\begin{eqnarray*} P(n,k) \end{eqnarray*}$ arbeiten, die zählt die Anzahl der Möglichkeiten, die Zahl $\begin{eqnarray*} n \end{eqnarray*}$ in genau $\begin{eqnarray*} k \end{eqnarray*}$ positive ganze Summanden zu zerlegen.

Wenn hier $\begin{eqnarray*} a_k \end{eqnarray*}$ die Wegstrecke der Schnecke an Tag $\begin{eqnarray*} k \end{eqnarray*}$ bezeichne, dann kommt man aus Forderung $\begin{eqnarray*} 10 \leq a_1 < a_2 < \ldots \end{eqnarray*}$ via Substitution $\begin{eqnarray*} b_k := a_k-8-k \end{eqnarray*}$ zur Bedingung $\begin{eqnarray*} 1\leq b_1 \leq b_2 \leq \ldots \end{eqnarray*}$ , mit dann

$\begin{eqnarray*} b_1+\ldots+b_{33} = a_1+\ldots+a_{33} - 8\cdot 33 - \frac{33\cdot 34}{2} = 2508 \end{eqnarray*}$ .

Die von dir gesuchte Anzahl ist demnach $\begin{eqnarray*} P(2508,33) = 49\,868\,814\,356\,508\,083 \,160\,003\,688\,331\,698\,469\,951 \approx 5\cdot 10^{37} \end{eqnarray*}$ .

23.01.2018, 11:35

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

23.01.2018, 17:00

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

23.01.2018, 17:01

HAL 9000

Auf diesen Beitrag antworten »

"Korrigieren" ??? Meinst du nicht eher "kopieren" ? verwirrt

verwirrt

23.01.2018, 17:11

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

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »