Formel für Max. Zahlenkombi. < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
Hallo, hoffe ich bekomme hier eine Lösung für mein Problem.
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
[http://www.mathe-profis.de/forum/thread.php?sid=e452fe2d42d969063ce46b23faaf3c1e&postid=7518#post7518]
Hier noch einmal das was auch unter oben genannter Adresse zu finden ist:
Ich suche nun schon einige Tage im web nach einer Lösung meines Problems:
Ich habe die Zahlen 1 bis 10 (1,2,3,4,5,6,7,8,9,10), nun möchte ich herausfinden wie viele Möglichkeiten es gibt Kombinationen zu bilden bei denen von einer zur nächsten Ziffer die max Differenz 4 nicht überschritten wird
z.B.:
1,4,8,10,9,7,6,5,3,2
oder
1,3,6,10,9,7,4,8,5,2
oder
1,3,2,4,6,9,10,8,7,5
oder
1,4,6,8,7,10,9,5,3,2
usw...
wichtig ist das wenn man bei der letzten Zahl angekommen ist, wieder von vorn anfangen kann und die max Differenz von 4 nicht überschritten wird
z.B.:
1,3,2,4,6,9,10,8,7,5
währe dann 5,1,3,2,4,6,9,10,8,7
Die Folgen die ich brauche fangen alle mit 1 an.
Wie müsste dazu die Formel aussehen?
Vielen Dank schon mal!
powerfisch
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:57 Di 02.05.2006 | | Autor: | powerfisch |
Hallo!
Ich bitte um Entschuldigung, nur leider bin ich das erste mal in einen Forum dieser Art und bitte hiermit um Nachsicht.
Mein Problem ist leider immer noch nicht gelöst und habe gehofft hier eine Lösung zu finden, wenn meine Frage auch nicht von richtigen Matte Profis beantwortet werden kann dann, dann scheint die Aufgabe unlösbar zu sein was ich aber bezweifle denn es sind Zahlen und es sollte immer eine Lösung geben.
Ok, wenn das nun falsch wahr hier zu Posten dann bitte ich noch mal um Entschuldigung, nur ich weiß nicht wo ich sonst noch hin soll.
MFG
powerfisch
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:45 Mi 03.05.2006 | | Autor: | DirkG |
Hallo Powerfish,
zunächst mal nehme ich an, es geht um Permutationen der Zahlen 1 bis 10 (nicht Kombinationen). Deine Bedingung mit der maximalen Differenz 4 ist vermutlich auf theoretischem Wege schwer zu bändigen, deswegen schlage ich hier Brute force vor: Gehe einfach alle 10!=3628800 Permutationen durch und zähle diejenigen, die deine Bedingung erfüllen. Bei 10 Zahlen ist das mit einem modernen PC auch noch kein Problem, bei 20 würde ich das nicht mehr so ohne weiteres vorschlagen. 
P.S.: Übrigens reicht wegen der zyklischen Symmetrie des Problems sogar die Untersuchung von 9!=362880 Permutationen, wenn man nämlich eine Stelle fixiert.
Gruß,
Dirk
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:57 Do 04.05.2006 | | Autor: | powerfisch |
Hallo!
Vielen Dank erst einmal für die Antwort hat mich schon etwas weiter gebracht nur leuchtet es mir nicht ein warum es dafür keinen Rechen weg geben soll.
Ich habe mir hier mit VB ne kleine Schleife gebastelt die mir solche Kombinationen ausgibt, wenn ich nun die Zahl 4 heraufsetze bekomme ich wesentlich mehr "gültige" Ergebnisse also sollte man doch die Zahl 4 irgendwie als Faktor betrachten können und eine Gleichung bilden können oder nicht?
powerfisch
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:02 Do 04.05.2006 | | Autor: | DirkG |
Original von Powerfisch
wenn ich nun die Zahl 4 heraufsetze bekomme ich wesentlich mehr "gültige" Ergebnisse
Klar - wenn man die Bedingungen herabsetzt, bekommt man mehr Permutationen, die diese herabgesetzten Bedingungen erfüllen.
Original von Powerfisch
also sollte man doch die Zahl 4 irgendwie als Faktor betrachten können und eine Gleichung bilden können oder nicht?
Das ist bloße Spekulation. Z.B. Kommt für dein Ursprungsproblem die Wahrscheinlichkeit [mm] $\frac{2670}{9!}$ [/mm] heraus. Im Zähler 2670 kann ich keinen Faktor 4 entdecken...
|
|
|
| |
|
Hallo und guten Morgen,
also probieren wir mal folgenden Ansatz:
Wir modellieren das Problem graphisch, d.h. wir nehmen natürlich nicht die Zahlen 1 bis 10, sondern direkt allgemein die
Zahlen 1 bis n. Die fassen wir auf als die Knoten eines Graphen [mm] G_n=(V_n,E_n) [/mm] mit
[mm] V_n=\{1,\ldots , n\}
[/mm]
und [mm] E_n=\{\{i,j\}|\:\: |i-j|\leq 4\}
[/mm]
Frage ist dann: Wieviele Hamilton'sche Kreise hat [mm] G_n [/mm] ?
Beobachtung:
Wir können [mm] G_n [/mm] gut rekursiv beschreiben [mm] (G_{n+1}: [/mm] Neuer Knoten n+1, dieser verbunden zu den Knoten
[mm] n-3,\ldots [/mm] n von [mm] G_n).
[/mm]
Die Nachbarn in einem Hamilton-Kreis von n+1 sind also zwei Knoten aus [mm] \{n-3,\ldots , n\}.
[/mm]
Also reicht es, rekursiv die Anzahl der Hamilton-Pfade in [mm] G_n [/mm] zu bestimmen, die die beiden Endpunkte in [mm] \{n-3,\ldots n\} [/mm] haben.
Das ist soweit der Ansatz, ich werd später noch was dazu schreiben.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:41 Fr 05.05.2006 | | Autor: | DirkG |
Klingt bis hierher sehr einleuchtend. Ich erwarte mit Spannung den Aufbau deiner Rekursion, die scheint mir nicht gerade einfach zu sein - aber vielleicht bin ich einfach nur zu blind...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:56 Sa 06.05.2006 | | Autor: | powerfisch |
Freut mich das es jemanden gibt der meint eine Lösung für das Problem zu finden. Ich hoffe nur ich werde die Formel dann auch verstehen, das ist meine größte Sorge.
Ihr müsst wissen das ich mich mit solchen schwierigen Formeln nur sehr selten rumquälen muss.
powerfisch
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 05:46 Mo 08.05.2006 | | Autor: | mathiash |
Hallo Dirk und powerfisch,
setzen wir uns also nochmal dran:
Bemerkung vorneweg: Zumindest mir ist nicht klar, ob wir eine Anzahlformel in geschlossener Form hinbekommen.
Mein erstes Ziel wäre eine Rekursionsformel. Diese könnte man immerhin implementieren und dann zu gegebenem n (zB n=10)
die Anzahl bestimmen lassen.
Wir müssen offenbar rekursiv die Zahl der Hamilton-Pfade bestimmen, deren Endpunkte unter den Zahlen
n-3,n-2,n-1,n sind (nur zu solchen kann n+1 adjazent sein).
Sei also
H(n,a,b)=Anzahl der Hamilton-Pfade in [mm] G_n [/mm] mit Endpunkten a und b (wir beschränken uns auf den Fall a<b).
Dann ist H(2,1,2)=1.
Offenbar ist dann die Anzahl der Hamilton-Kreise in [mm] G_n [/mm] gleich
[mm] \sum_{n-4\leq a
Nun müssen wir H(n,a,b) rekursiv bestimmen.
... Forts. folgt....
Gruss,
Mathias
|
|
|
|
