Wie errechne ich die Kombinationsmöglichkeiten

Wissenschaft Mathematik
#1

Guten Tag miteinander

Ich habe mal angefangen auf einem Notizblock herumzukrizzeln. Dabei habe ich ein Quadrat erstellt (5 Häuschen hoch und 5 Häuschen breit)… ich habe begonnen Häuschen (Felder) auszumalen und Förmchen zu zeichnen… Später habe ich mir Gedanken gemacht, wieviele 15er, 16er, u. 17er Förmchen es wohl gäbe innerhalb dieser 25 Felder und „zeichnete“, Tagen, Wochen, Monate… immer mal wieder… Irgendwann habe ich herausgefunden, das eine 17er Form die vollkommenste innerhalb dieser 25 Felder ist und bin bei 17 (Häuschen) geblieben. Ich habe dabei Regeln aufgestellt welche die Form erfüllen muss damit es eine „gültige“ Form ist (nicht zuletzt auch um die Anzahl Möglickeiten weiter einzuschränken) -
mit Hilfe dieser Regeln kann ich nun gemütlich weiter herumkrizzeln (gültige von ungültigen Formen unterscheiden) und auf ein baldiges Ende der Kombinationsmöglichkeiten hoffen.

Trotz dieser klaren Regeln hoffe ich jetzt aber auf eine mathematische Lösung, um Irrtümer (ich könnte eine Kombination übersehen haben…) auszuschliessen und eine klar errechnete Anzahl (Kombin.Möglichkeiten) zu finden.

So, erst Jetzt komme ich langsam zur Frage welche eine Mathematische ist. Dabei hoffe ich auf eine Formel od. auf die Lösung (Zahl).

>>Wieviel Kombinatins-Möglichkeiten gibt es allgemein innerhalb dieses 25er Raster (25 Häuschen) wenn man genau 17 Felder (Häuschen) ausfüllen muss. Logischerweise sind dabei immer 8 Häuschen leer!

Die Regeln: (der eigentliche Knackpunkt der Fragen)

  • Regel Nr. 1:
    Form muss „1 Häuschen dick“ sein und muss eine „verbundene“ und „offene Form“ sein. D.h. „eingeschlossene“ oder „nicht verbundene“ Quadrätchen od. „Teilformen“ sind ungültig!

  • Regel Nr. 2:
    Es dürfen nirgends „2x2 Häuschen Leerheit“ und/oder
    „2x2 Häuschen Form“ auftreten!
    Diese sogen. „4er Block’s“ sind ungültig!

  • Regel Nr. 3:
    Die Form darf „nur einmal“ vorkommen!
    D.h. „gedrehte“ od. „spiegelverkehrte“ „Doppelgänger“ derselben Form sind nicht zulässig = ungültig!

Ich habe versucht es mit Worten zu beschreiben - gerne würde ich eine Grafik einfügen um Beispiele zu zeigen.

Jemand sagte mir, dass dürfte für einen Mathematiker der sich mit Kombinatorik auskennt, kein komplexes Problem sein… Ich bin hier aber anderer Meinung … Was meint Ihr dazu ???

Ich bin der Meinung mithilfe diesen Regeln dürfte es nicht mehr als 200 Möglichkeiten geben! Momentan stecke ich bei der 134 igsten Form. Doppelgänger sind hier bereits ausgeschlossen!

Vielen Dank für Eure ehrlichen Bemühungen…
Flinkefinger

#2

Hallo Flinkefinger,

ich kann dir da im Moment leider nicht weiterhelfen, aber ich weiß jemanden, der richtig Spaß an solchen Sachen hat. Dem schicke ich dein Problem mal weiter.

LG Topat

#3

Hallo Flinkefinger,

hier ist die Antwort von meinem ‚Verbindungsmann für Mathe‘:

Hi

Mit Kombinatorik sehe ich da wenig Chance, da die Nebenbedingungen zu sehr konstruiert sind. Wäre eine nette Fingerübung für Programmierung eines Backtracking-Algorithmus, zB mit PHP. Vielleicht probiere ich das mal über die Feiertage.

Gruß
J

Gruß Topcat

#4

Hallo Topcat

Hast Du die Grafik gesehen die ich per Link aufs Netz gestellt habe ?
Ansonsten hier (lästige Werbung einfach wegklicken!):

http://www.bilderload.net/bild-Bsp_gltige_u_ungltige…

Betr. konstruierten Nebenbedingungen - Das kann schon sein was Du sagst, immerhin habe ich aus ursprünglich 7 Regeln nur 3 gemacht und musste mich an die Logik der Formen herantasten. Vielleicht müsste ich diese Regeln Schritt für Schritt wieder zerlegen …

Vielen Dank
flinkefinger

#5

Hallo Topcat

Hier mein neuer Text - Du könntest ihn auch Deinem Kollegen weiterleiten. Sorry für die Umstände!

Ich musste einsehen, dass ich bei meinem Problem mit dem Stichwort „Kombinatorik“ nicht weit kommen kann…
Deshalb habe ich versucht, meine Regeln (Bedingungen) etwas auseinanderzunehmen und übersichtlicher aufzugliedern.

Gegeben ist ein Raster mit 25 Häuschen:

  • Regel Nr. 1 = die Form muss 17 Häuschen ausfüllen - Logischerweise bleiben immer 8 leere Häuschen übrig!

  • Regel Nr. 2 = Form muss zusammenhängend sein! - d.h. Keine unabhängigen Einzelformen! (Ecken-Berührung allein genügt nicht - 1 Häuschen muss flächig mit dem Rest der Form verbunden sein!)

  • Regel Nr. 3 = Form darf nicht auf allen 4 Aussen-Seiten geschlossen sein! min. 1 Häuschen muss nach aussen offen bleiben! Dasselbe gilt für alle vollständig eingeschlossene Leer-Flächen (od. nur an den Ecken eingeschlossene Leer-Flächen)

  • Regel Nr. 4 = Keine 4er Form-Blocks (Klumpen) - diese sind nicht im Sinne der Ästhetik und fallen weg!

  • Regel Nr. 5 = Alle gespiegelten od. gedrehten Doppelgänger fallen ebenfalls weg!
    Einige Formen gehen aufgrund ihrer Symmetrie nur teilweise, andere vollständig ineinander über.
    (Dies ist eindeutig die komplexeste Bedingung und eliminiert tausende von Möglichkeiten!)

siehe neue Bsp.Grafik:
http://www.bilderload.net/bild-Bsp_gltige_ungltige_j…

Bemerkungen:

> Es ist nicht möglich „Regel 1“ einzuhalten wenn irgendwo ein 4er Block-Leerheit (4 leere Häuschen) auftritt!

> Im Zweifelsfalle darf man die Ecken-Regel (siehe „Nebenregel 3“) vernachlässigen, wenn diese Form alle übrigen Regeln erfüllt (1, 2, 4 u. 5).
(Der Idealfall wäre hier eine Lösung mit der „Ecken-Regelung“ und eine ohne)

…

Wichtiger Hinweis:

Bitte nicht auf die Idee kommen alle Möglichkeiten aufzuzeichnen… Ich spreche aus Erfahrung!
Selbst wenn die Anzahl der Formen-Vielfalt vermutlich nicht sehr hoch ist!
Bisher habe ich erst 135 verschiedene gefunden.

Aber die Preisfrage ist - wieviele gibt es genau !?!?

Ich denke die Anzahl-Möglichkeiten für die „Regel 1“ allein, müssten mit einer Formel zu definieren sein.
Bei den übrigen Bedingungen wirds aber ungleich schwieriger …

Für Hinweise, Denkanstösse u. Bemühungen wie ich der Lösung näher kommen kann, bin ich jedenfalls sehr dankbar!

#6

Hallo,
ich habe darüber nachgedacht, aber keinen mathematischen Ansatz gefunden, wie das zu lösen wäre.
Daher würde ich vorschlagen, wie folgt vorzugehen:
Es gibt (bei z.B. dem Fall 16) 25 über 16 (=2.042.975)16 Felder von 25 auszuwählen.
Ich würde ein Programm schreiben, um zu testen, welche dieser Kombiationen den Bedingungen genügen, und welche der Lösungen Drehungen von vorigen Lösungen sind.
Ich hoffe, dieser Vorschlag bringt Dich weiter.
Gruß
Franz-Josef

#7

Hallo Franz-Josef

Ich weiss zwar noch nicht genau was du mit dem Fall 16 meinst… wahrscheinlich bezieht sich das auf meine ganz oben erwähnten 16er Förmchen - Oder?
Ich hoffe es wurde gelesen, dass es mir momentan nur um die 17er Förmchen geht!
Sollte es dir mit Programmieren gelingen der Lösung etwas näher zu kommen - ziehe ich meinen Hut.

Jedenfalls vielen Dank für die Bemühungen …

flinkefinger

#8

Sorry, keine Ahnung.

#9

Sorry, keine Ahnung.

Kein Problem … ich bin der Lösung durch auspröbeln sowieso schon sehr nahe! Habe leider haupsächlich nur Mathematiker gefragt, jedoch noch keine Programmierer.
Ist also mein Fehler !
Danke