Die Mathe-Redaktion - 26.09.2017 20:18 - Registrieren/Login
Auswahl
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Apr. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 491 Gäste und 26 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » Anzahl Möglichkeiten der Anordnung von Punkten in Gitter (mit Rotation, Spiegelung)
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Anzahl Möglichkeiten der Anordnung von Punkten in Gitter (mit Rotation, Spiegelung)
Yor
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 29.09.2009
Mitteilungen: 29
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2017-07-15


Hi,
(ich wusste nicht genau in welches Unterforum diese Frage am besten passt. Beinhaltet Teile aus verschiedenen Gebieten. ggf. verschieben)

Gegeben ist ein quadratisches Gitter mit der Größe m x m. Es hat also <math>m^2</math> Löcher die entweder voll oder leer sein können. Meine Frage ist nun wieviele unterschiedliche Möglichkeiten gibt es das Gitter zu füllen, unter der Bedingung, dass auch nach rotieren und/oder wenden es keiner anderen Konfiguration entspricht.
(Ohne die Bedingung wäre es einfach <math>2^{m^2}</math>)

Veranschaulicht mit Matrix aus 0en und 1en:
für m=2
ohne Füllung, gibt es eine Möglichkeit:
<math>\[
\begin{vmatrix}
0 & 0 \\
0 & 0
\end{vmatrix}
\]</math>
mit einer Füllung, gibt es auch nur eine Möglichkeit, da man die anderen durch Rotation erhalten kann.
<math>\[
\begin{vmatrix}
1 & 0 \\
0 & 0
\end{vmatrix}
\]</math>
mit 2 Füllung gibt es zwei
<math>\[
\begin{vmatrix}
1 & 1 \\
0 & 0
\end{vmatrix}
\]</math><math>\[
\begin{vmatrix}
1 & 0 \\
0 & 1
\end{vmatrix}
\]</math>
3 und 4 Füllungen ist dann analog zu einer und keiner Füllung, jeweils nur eine Möglichkeit.

Für m=2 gibt es also insgesamt 6 unterschiedliche Möglichkeiten der Anordnung.


für m=3
bei 0 wie immer nur eine
bei 1 gibt es 3
bei 2 gibt es 8:
<math>\[
\begin{vmatrix}
1 & 1 & 0\\
0 & 0 & 0\\
0 & 0 & 0
\end{vmatrix}
\]</math><math>\[
\begin{vmatrix}
1 & 0 & 1\\
0 & 0 & 0\\
0 & 0 & 0
\end{vmatrix}
\]</math><math>\[
\begin{vmatrix}
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 0
\end{vmatrix}
\]</math><math>\[
\begin{vmatrix}
1 & 0 & 0\\
0 & 0 & 1\\
0 & 0 & 0
\end{vmatrix}
\]</math><math>\[
\begin{vmatrix}
1 & 0 & 0\\
0 & 0 & 0\\
0 & 0 & 1
\end{vmatrix}
\]</math><math>\[
\begin{vmatrix}
0 & 1 & 0\\
0 & 1 & 0\\
0 & 0 & 0
\end{vmatrix}
\]</math><math>\[
\begin{vmatrix}
0 & 1 & 0\\
1 & 0 & 0\\
0 & 0 & 0
\end{vmatrix}
\]</math><math>\[
\begin{vmatrix}
0 & 1 & 0\\
0 & 0 & 0\\
0 & 1 & 0
\end{vmatrix}
\]</math>
Hier kommt neben dem Rotieren auch das "wenden" (spiegeln) ins Spiel.
So kann man <math>\[
\begin{vmatrix}
0 & 0 & 1\\
1 & 0 & 0\\
0 & 0 & 0
\end{vmatrix}
\]</math>nicht durch rotieren von<math>\[
\begin{vmatrix}
1 & 0 & 0\\
0 & 0 & 1\\
0 & 0 & 0
\end{vmatrix}
\]</math>erhalten. Betrachtet man das (Zaun-)Gitter von der anderen Seite, bzw. man wendet es oder spiegelt es, erhält man die andere Konfiguration.


Da es dann bei m=3 und 3 Füllungen schon langsam kompliziert wird. Ist meine Frage, ob man das auch ausrechnen kann.

Falls es einen Rechenweg gibt, wäre ggf. als zweite Frage noch, ob man alle Konfigurationen aufzählen kann bzw. geordnet angeben kann oder noch besser aus dem Index die dazugehörige Konfiguration bilden kann.



  Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 2828
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2017-07-16


Schau mal hier:
 
math.stackexchange.com/questions/387195

oeis.org/A054247 und oeis.org/A054252

Die Anzahl ist demzufolge
 
<math>\begin{cases} \frac{1}{8} (2^{m^2}+2 \cdot 2^{m^2/4}+3 \cdot 2^{m^2/2}+2 \cdot 2^{(m^2+m)/2}) & m \text{ gerade} \\ \frac{1}{8} (2^{m^2}+2 \cdot 2^{(m^2+3)/4}+2^{(m^2+1)/2}+4 \cdot 2^{(m^2+m)/2}) & m \text{ ungerade}\end{cases}</math>

Für <math>m=3</math> ist das z.B. <math>102</math>.



  Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 2828
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2017-07-17


Hier eine genauere Erklärung.

Es sei <math>X_n</math> die Menge der binären <math>n \times n</math>-Matrizen. Auf ihr wirkt die Diedergruppe <math>D_4</math> (die Isometriegruppe des Quadrats) auf natürliche Weise. Zum Beispiel wirkt die Drehung um 90° für <math>n=3</math> durch

<math>\begin{pmatrix} a_{11} & a_{12} & a_{13} \\
a_{21} & a_{22} & a_{23} \\
a_{31} & a_{32} &  a_{33}
\end{pmatrix} \mapsto \begin{pmatrix} a_{31} & a_{21} & a_{11} \\
a_{32} & a_{22} & a_{12} \\
a_{33} & a_{23} &  a_{13}
\end{pmatrix}. </math>
 
Das Ziel ist es, <math>\mathrm{card}(X_n / D_4)</math> zu bestimmen, die Kardinalität der Menge der <math>D_4</math>-Bahnen auf <math>X_n</math>. Dazu benutzt man das Lemma von Burnside: Wirkt eine endliche Gruppe <math>G</math> auf einer endlichen Menge <math>X</math>, so gilt

<math>\displaystyle\mathrm{card}(X/G) = \frac{1}{\mathrm{card}(G)} \cdot \sum_{g \in G} \mathrm{card}(X^g),</math>
 
wobei <math>X^g = \{x \in X : gx=x\}</math> die Fixpunktmenge von <math>g \in G</math> sei. Ein Beweis dieser Formel gelingt durch zweifaches Abzählen der Menge <math>\{(g,x) \in G \times X : gx=x\}</math> in Kombination mit der Bahngleichung.
 
Es gibt einen Zusatz: Wenn <math>g,h \in G</math> zueinander konjugiert sind, dann gilt <math>\mathrm{card}(X^g)=\mathrm{card}(X^h)</math>. Genauer gesagt ist, wenn <math>h=t g t^{-1}</math>, die Abbildung <math>X^g \to X^h</math>, <math>x \mapsto tx</math> ein Isomorphismus von Mengen. Wir können die Formel also auch schreiben als

<math>\displaystyle\mathrm{card}(X/G) = \frac{1}{\mathrm{card}(G)} \cdot \sum_{[g] \in C(G)} \mathrm{card}([g]) \cdot \mathrm{card}(X^g),</math>
 
wobei <math>C(G)</math> die Menge der Konjugationsklassen der Gruppe <math>G</math> bezeichnet.
 
Die Konjugationsklassen von <math>D_4 = \langle \sigma,\tau : \sigma^4=\tau^2=(\sigma\tau)^2=1 \rangle</math> sind gegeben durch:

<math>[1] = \{1\} \\
\vphantom{.}[\sigma] = \{\sigma,\sigma^3 \}\\
\vphantom{.}[\sigma^2] = \{\sigma^2 \}\\
\vphantom{.}[\tau] = \{\tau, \tau \sigma^2 \}\\
\vphantom{.}[\tau \sigma] = \{\tau \sigma,\tau \sigma^3 \}</math>
 
Man muss also lediglich 5 Fixpunktmengen berechnen. Dabei ist die erste sehr einfach, denn <math>X^1=X</math> hat die Kardinalität <math>2^{n^2}</math>. Bei den restlichen empfiehlt sich eine Fallunterscheidung, ob <math>n</math> gerade oder <math>n</math> ungerade ist. Beide Fälle sind sehr ähnlich zu behandeln und unterscheiden sich von der Vorgehensweise gar nicht, nur dass die vorkommenden Summen etwas anders enden. Ich beschränke mich daher auf den Fall, dass <math>n</math> ungerade ist.
 
Die Fixpunktmenge von <math>\sigma</math> lässt sich explizit bestimmen: Der Eintrag in der Mitte kann beliebig gewählt werden. Der "Rahmen" mit 8 Einträgen drum herum muss so beschaffen sein, dass er bei der Rotation um 90° invariant bleibt. Das bedeutet aber, dass er durch 2 Einträge, die aufeinanderfolgen, vollständig festgelegt ist. Zum Beispiel für <math>n=3</math>:
 
<math>\begin{pmatrix} \fbox{$a_{11}$} & \fbox{$a_{12}$} & a_{11} \\
a_{12} & \fbox{$a_{22}$} & a_{12} \\
a_{11} & a_{12} &  a_{11}
\end{pmatrix} </math>

Ist nun <math>n</math> beliebig, so geht man mit den Rahmen weiter außen genauso vor. Man erhält insgesamt <math>1+2+4+\dotsc+(n-1)</math> Einträge, die die Matrix vollständig festlegen. Das ist also gleich
 
<math>\displaystyle 1+\sum_{k=1}^{\frac{n-1}{2}} 2k = 1 + \tfrac{n-1}{2} \cdot \tfrac{n+1}{2} = \tfrac{n^2+3}{4}.</math>
 
Es folgt also <math>\mathrm{card}((X_n)^{\sigma})=2^{\frac{n^2+3}{4}</math>.
 
Bei <math>\sigma^2</math>, der Rotation um 180°, kann man ähnlich vorgehen, nur dass man mehr Einträge festlegen muss:

<math>\begin{pmatrix} \fbox{$a_{11}$} & \fbox{$a_{12}$} & \fbox{$a_{13}$} \\
a_{23} & \fbox{$a_{22}$} & \fbox{$a_{23}$} \\
a_{13} & a_{12} &  a_{11}
\end{pmatrix} </math>
 
Die Zahl der festzulegenden Einträge ist damit

<math>\displaystyle 1+4+8+\dotsc+(2n-2) = 1+\sum_{k=1}^{\frac{n-1}{2}} 4k = \tfrac{n^2+1}{2}.</math>
 
Es folgt also <math>\mathrm{card}((X_n)^{\sigma^2}) = 2^{\frac{n^2+1}{2}}</math>.
 
Kommen wir nun zu den Fixpunkten der vertikalen Spiegelung <math>\tau</math>. Hier muss man lediglich die oberen <math>\frac{n+1}{2}</math> Zeilen festlegen. Die unteren Zeilen ergeben sich dann eindeutig. Das macht <math>\frac{n(n+1)}{2}</math> Einträge und damit insgesamt <math>2^{\frac{n(n+1)}{2}}</math> Fixpunkte.

Für <math>\sigma \tau</math> funktioniert ein ähnliches Argument, nur dass die Spiegelachse hier die Diagonale ist, die von unten links nach oben rechts verläuft. Die Zahl der festzulegenden Einträge bleibt gleich, und daher auch die Zahl der Fixpunkte.
 
Das beweist die genannte Formel

<math>\mathrm{card}(X_n/D_4)=\frac{1}{8} ( 2^{n^2} + 2 \cdot 2^{\frac{n^2+3}{4}} + 2^{\frac{n^2+1}{2}} + 4 \cdot 2^{\frac{n(n+1)}{2}} )</math>
 
für ungerade <math>n</math>. Für gerade <math>n</math> kann man wie gesagt sehr ähnlich vorgehen.



  Profil  Quote  Link auf diesen Beitrag Link
Yor
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 29.09.2009
Mitteilungen: 29
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2017-07-17


Hallo Triceratops,
vielen Dank für die ausführliche Antwort. Da scheine ich ja nicht der erste mit dem Problem gewesen zu sein :)
Auf oeis ist ja genau dieses schon eingetragen. Auch danke für den Link.

Den Anfang und untere Erklärung des Beweises habe ich denke ich auch kapiert. Lemma von Burnside kannte ich noch nicht und muss ich mir wohl noch einmal genauer anschauen.

Abzählbar sind die ja dann somit auch, einfach die Anzahl der Möglichkeiten je "Rahmen" durchgehen.

Danke nochmal!



  Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 2828
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2017-07-17


2017-07-17 17:39 - Yor in Beitrag No. 3 schreibt:
Abzählbar sind die ja dann somit auch, einfach die Anzahl der Möglichkeiten je "Rahmen" durchgehen.

Wie meinst du das genau?



  Profil  Quote  Link auf diesen Beitrag Link
Yor
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 29.09.2009
Mitteilungen: 29
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2017-07-17


mathematisch korrekt is das zwar nicht. Aber jeder "Rahmen" hat ja eine Anzahl Möglichkeiten in der die 1en positioniert werden können. Die Möglichkeiten könnte man dann auch je nach Anzahl der 1en sortieren. Erst geht man alle mit 0 durch (=1), dann die mit 1er 1, mit 2 usw.

Eine Konfiguration könnte man dann zb. mit 1.3.7 angeben (für n=5). Das wäre dann die erste Anordnung in der Mitte, die 3. in der erste Reihe und 7. in der zweiten. Dann könnte man wie bei normalen Zahlen durchzählen, jedoch mit anderer Basis (statt 10) an jeder Stelle.



  Profil  Quote  Link auf diesen Beitrag Link
Yor hat die Antworten auf ihre/seine Frage gesehen.
Yor hatte hier bereits selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]