matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenKombinatorikFormel für Max. Zahlenkombi.
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
Forum "Kombinatorik" - Formel für Max. Zahlenkombi.
Formel für Max. Zahlenkombi. < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Formel für Max. Zahlenkombi.: Formel
Status: (Frage) beantwortet Status 
Datum: 14:04 Fr 28.04.2006
Autor: powerfisch

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

        
Bezug
Formel für Max. Zahlenkombi.: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
        
Bezug
Formel für Max. Zahlenkombi.: Antwort
Status: (Antwort) fertig Status 
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


Bezug
        
Bezug
Formel für Max. Zahlenkombi.: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                
Bezug
Formel für Max. Zahlenkombi.: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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...

Bezug
        
Bezug
Formel für Max. Zahlenkombi.: Hamilton-Pfade
Status: (Antwort) fertig Status 
Datum: 08:37 Fr 05.05.2006
Autor: mathiash

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

Bezug
                
Bezug
Formel für Max. Zahlenkombi.: Details?
Status: (Mitteilung) Reaktion unnötig Status 
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...

Bezug
                
Bezug
Formel für Max. Zahlenkombi.: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                
Bezug
Formel für Max. Zahlenkombi.: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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



Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]