Wieviele Kombinationsmöglichkeiten gibt es

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

Hi,

naja, du kreuzt 7 Felder von 25 an. Das klingt doch sehr nach Lotto :smile:

Die Anzahl Kombinationen ergibt sich als

{n \choose k} = \frac{n!}{k(n-k)!}

wobei n = Anzahl der Felder und k = Anzahl der Kreuzchen. Bei dir ergibt sich

{25 \choose 7} = \frac{25!}{7!(25-7)!} = 480700

Viel Spaß beim durchprobieren und nachzählen :smile:

VG
Jochen

PS: n! spricht sich „n-Fakultät“ und ist das Produkt aus n*(n-1)*(n-2)*…*3*2*1. 25! ist riesig (25*24*23…), 7! = 5040 (7*6*5*4*3*2*1).

#3

naja, du kreuzt 7 Felder von 25 an. Das klingt doch sehr nach
Lotto :smile:

Hallo,

die obige Aussage enthält drei Fehler:

  • es sind 8 von 25
  • Symmetrische Lösungen werden mehrfach gezählt
  • die Randbedingung: keine Viererblöcke ist damit nicht berücksichtigt.

Das Symmetrische ist schon nicht so einfach, weil man nicht generell durch 8 teilen kann (4 Orientierungen und Spiegelbild), es gibt nämlich verschieden symmetrische Lösungen, die in sich selbst übergehen, z. B. die Lücke und in jeder der Ecken, die nur durch die Viererblock-Regel herausfällt. Solche Überlegungen sind mir unter dem Stichwort „Diedergruppen“ schon einmal begegenet, das habe ich aber nicht mehr präsent.
Die Vierblockregel kommt mir mathematisch schon ziemlich ungriffig vor, ob durch die Regel 1 (zusammenhängen) noch weitere Lösungen wegfallen, ist mir auch nicht klar.

Grüße, guidot

#4

Für Eure ersten Überlegungen muss ich mich bedanken…
Vielleicht sollte ich betonen, dass mir die Komplexität bewusst ist und ich von niemandem erwarten kann auf die Schnelle eine Lösung zu finden.

Wenn mir eine Mathematiker mitteilen kann wo die Probleme bei der Berechnung liegen (im Zusammenhang mit meinen 3 Regeln), wäre ich schon sehr dankbar!
Wenn es aber eine Lösung eine Formel od. Teilformeln gibt, bin ich natürlich noch dankbarer!

#5

Hallo,

die obige Aussage enthält drei Fehler:

  • es sind 8 von 25
  • Symmetrische Lösungen werden mehrfach gezählt
  • die Randbedingung: keine Viererblöcke ist damit nicht
    berücksichtigt.

Oh Mist, man. Ich hätte doch weiterlesen sollen |-.

Jetzt kann ich die dreifachfalsche Antwort nicht mehr löschen…

Für die drei Regeln habe ich natülich und leider keine einfache Lösung. Ich vermute auch nicht, dass es da einen eleganten Löungsweg gibt.

Für einen Computer ist es aber kein großer Aufwand, die 480700 infrage kommenden Möglichkeiten auf die Regeln zu testen.

Sorry nochmal für die zu schnelle und „unhilfreiche“ Antwort!

mea culpa,
Jochen

#6

Fürs bessere Verständniss hier ein Beispiel (Link):

#7

Hallo

Ist ein bisschen offtopic, aber es ist unfreundlich dieselbe Frage auch als Expertenanfrage zu posten.
Zum Thema: vermutlich gibt es (auch wg. der Randbedingungen) keinen geschlossenen mathematischen Ansatz. Hier hilft nur Simulieren (engl.:„trial and error“) mit einem Computer, der alle Kombinationen durchnimmt und kontrolliert, ob es passt.

mfg M.L.

#8

Diese Antwort habe ich auch erwartet …

2 Dinge möchte ich dazu noch sagen:

  1. Irgend jemand müsste das erstmal programmieren - Wer ? und aufgrund welcher mathematischen Basis ? gibt es hierzu bereits schon fertige Algorythmen - Wo ?

  2. Sicherlich kann ich auch Programmierer anfragen - nur müsste ich herausfinden, dass es mit Mathematik od. Geometrie nicht zumutbar ist.

Vorschläge nehme ich dankend entgegen - ebenso Eingeständnisse, dass man zu keiner Lösung kommt. Auch das bringt mich weiter!

#9

Eine Lösung
Ok, ich habe mal ein Programm geschrieben. Ich habe es in R geschrieben, weil R ganz nette Matrizen-Funktionen bietet und diese Programmiersprache frei erhältlich ist (http://www.r-project.org). Du kannst das Programm also selbst ausprobieren und verändern.

Ich habe es auf einem Intel i5-750 mit 2.8GHz gerechnet. Ich habe nur einen Kern belastet. Man kann das aus so programmieren, dass mehrere Kerne parallel benutzt werden, was die Rechenzeit verringert. Die unten angegebenen Rechenzeiten beziehen sich aber auf 1 x 2.8GHz. Das Programm ist auch nicht sonderlich auf Geschwindigkeit getrimmt. Hier geht sicher noch was. Natürlich kann man mit einer systemnäheren Programmersprache wie C nochmal ordentlich was an Rechenzeit sparen, aber das mag angehen, wer will.

Die Kriterien sind:

a) Alle gesetzten Felder müssen zusammenhängen
b) Es darf keine 2x2-Bereiche geben (weder gesetzt noch ungesetzt)
c) Es darf keine „Eckberührungen“ gesetzter Felder geben (d.h. 2x2-Bereiche dürfen nicht diagonal besetzt sein)
d) Die Figur muß „offen“ sein, d.h. es darf keine umschlossenen ungesetzten Bereiche beben (alle nichtbesetzten Bereiche müssen eine Verbindung zum Rand haben)
e) Es dürfen nur nicht-kongruente Figuren gezählt werden (d.h. Figuren, die durch Drehung oder Spiegelung und Kombinationen daraus ineinander überführt werden können, gelten als die gleiche Figur)

Das Programm arbeitet in drei Schritten:

  1. Zusammenstellen aller „17 aus 25“-Kombinationen
  2. Aussortieren aller Figuren, die nicht den Kriterien a-d entsprechen
  3. Aussortieren aller „doppelten“ weil kongruenten Figuren

Ergebnis:

  1. Es gibt 1081575 Möglichkeiten, 17 von 25 Feldern zu besetzen. Zeit zum Zusammenstellen all dieser Kombinationen: ca. 9s.

  2. Es gibt 1072 Figuren, welche die Kriterien a-d erfüllen. Zeit zum Aussortieren: ca. 15s

  3. Es gibt 150 Figuren, die außerdem das Kriterium e erfüllen. Zeit zum Aussortieren: ca. 2s

Insgesamt liegt die Rechenzeit also bei ca. 26s. Das kann man ertragen. Hpiig wird es natürlich, wenn man nicht vorgibt, wieviele Felder besetzt sein müssen und/oder wenn man größere Matrizen angeht.

So, hier das Programm. Es erstellt auch noch ein PDF mit allen 150 Lösungen. Die kann ich dir auf Wunsch emailen.

##### TEIL 1 ######

library(combinat)
a = combn(25,17)


##### TEIL 2 ######

# test-Funktion
# Parameter "gesetzt" gibt an, welche Positionen in der 5x5-Matrix gesetzt sind
# (Werte 1 bis 25 von links oben nach rechts unten)
# Die Funktion gibt TRUE zurück, wenn die Regeln erfüllt sind

test = function(gesetzt) {

 # 5x5 Matrix vorbereiten
 m = matrix(0,5,5)
 m[gesetzt] = 1

 # Viererblöcke und Eckberührungen?
 for (i in 1:4) {
 for (j in 1:4) {
 s = sum(m[i:frowning:i+1),j:frowning:j+1)])
 if (s==0 | s==4) return(FALSE)
 if (s==2 && m[i,j]==m[i+1,j+1]) return(FALSE)
 }
 }
 # alle gesetzten Bereiche zusammenhängend?
 # alle ungesetzte Bereiche mit Verbindung zum Rand?

 bereich0 = bereich1 = 0
 feld0 = feld1 = matrix(0,5,5)

 for (i in 1:5) {
 for (j in 1:5) {
 if (m[i,j]) {
 # gesetze bereiche
 bereich1 = bereich1 + 1
 feld1[i,j] = bereich1
 if (i\>1) {f = feld1[i-1,j]; if (f\>0) feld1[feld1==f] = bereich1}
 if (j\>1) {f = feld1[i,j-1]; if (f\>0) feld1[feld1==f] = bereich1}
 } else {
 # nicht gesetze bereiche
 bereich0 = bereich0 + 1
 feld0[i,j] = bereich0
 if (i\>1) {f = feld0[i-1,j]; if (f\>0) feld0[feld0==f] = bereich0}
 if (j\>1) {f = feld0[i,j-1]; if (f\>0) feld0[feld0==f] = bereich0}
 }

 }#j
 }#i

 # wenn alle gesetzten Bereiche zusammenhängend sind, gibit es in feld1 außer der Null
 # genau noch eine weitere Zahl:

 if (length(unique(c(feld1))) != 2) return(FALSE)

 # wenn alle ungesetzte Bereiche mit Verbindung zum Rand stehen, 
 # dann ist jede Zahl im Innenbereich von feld0 auch im Außenbereich

 bereiche0.innen = unique(c(feld0[2:4,2:4]))
 feld0[2:4,2:4] = 0
 bereiche0.aussen = unique(c(feld0))
 if (identical(bereiche0.aussen,0) || length(setdiff(bereiche0.innen,bereiche0.aussen))) return(FALSE)

 return(TRUE)
}

# Aufruf der test-Funktion für jede Spalte von a

ok = apply(a,2,test)
a.ok = a[,ok]


##### TEIL 3 ######

a. = a.ok
n = ncol(a.)
i = 1

# Für jede Spalte in a.
# (a. wird in jedem Durchlauf um die Spalten mit Duplikaten 
# verkleinert, n ist immer die aktuelle Zahl der Spalten von a.

while(i 

VG
Jochen
#10

Hallo,

es gibt einen kleinen Fehler im Skript. Diesen Fehler hat „Martin“ gefunden und mir per Email mitgeteilt:

Die beiden letzten Figuren der Lösung (Spalte 15, Zeilen 9 und 10) sind kongruent. Es gibt also nur 149 Lösungsfiguren.

In Teil 3 muss die while-Schleife natürlich "while(i