Polya, Burnside: nichtäquivalente Färbungen eines 3x3 Quadrates

24.09.2019, 02:26

Studentu

Polya, Burnside: nichtäquivalente Färbungen eines 3x3 Quadrates

Liebe Community,

gegeben ist ein Quadrat bestehend aus 3x3 Quadraten.
Die Frage ist, wieviele nichtäquivalente Färbungen mit weiß und schwarz es unter Drehungen und/oder Spiegelungen es gibt, sodass 4 Quadrate weiß und 5 schwarz sind.

Ich habe mir das Ganze sowohl mit Polya als auch mit Burnside überlegt.
Das Polya-Ergebnis muss jedenfalls falsch sein (weil es nicht ganzzahlig ist):
Zuerst bestimme ich die Zyklentypen für die Transformationen:
1) Identität: ZT = $\begin{eqnarray*} x_1^9 \end{eqnarray*}$
2): Drehung um 90 Grad: ZT = $\begin{eqnarray*} x_1^1 x_4^8 \end{eqnarray*}$
3): Drehung um 180 Grad: ZT = $\begin{eqnarray*} x_1^1x_2^8 \end{eqnarray*}$
4): Drehung um 270 Grad: ZT = $\begin{eqnarray*} x_1^1 x_4^8 \end{eqnarray*}$
5): Spiegelung entlang 1. Diagonale: ZT = $\begin{eqnarray*} x_1^2 x_2^6 \end{eqnarray*}$
6): Spiegelung entlang 2. Diagonale: ZT = $\begin{eqnarray*} x_1^3 x_2^6 \end{eqnarray*}$
7): Spiegelung entlang Horizontalen: ZT = $\begin{eqnarray*} x_1^3 x_2^6 \end{eqnarray*}$
8): Spiegelung entlang Vertikalen: ZT = $\begin{eqnarray*} x_1^3 x_2^6 \end{eqnarray*}$

Also ergibt sich der Zyklenzeiger als $\begin{eqnarray*} \frac{1}{8}(x_1^9+2x_1^1x_4^8 + x_1^1x_2^8 + 4x_1^3x_2^6) \end{eqnarray*}$ .
Benennt man nun das Gewicht von weiß als w und das von schwarz als s, so ergibt sich für die Anzahl an möglichen nichtäquivalenten Färbungen:
$\begin{eqnarray*} \frac{1}{8}((w+s)^9 + 2(w+s)(w^4+s^4)^8 + (w+s)(w^2+s^2)^8 + 4(w+s)^3(w^2+s^2)^6) \end{eqnarray*}$ .
Das habe ich mit der verallgemeinerten Binomischen Formel umgeschrieben, um den Koeffizienten $\begin{eqnarray*} [w^4s^5] \end{eqnarray*}$ ablesen zu können. Dieser ergibt sich bei mir als: $\begin{eqnarray*} \frac{1}{8}(\binom{9}{4} + 0 + 0 + 0 + 0 + 0) = 15,75 \end{eqnarray*}$ .
Dies ist offensichtlich falsch.

WO LIEGT DENN MEIN FEHLER?

Dann habe ich das Ganze noch mit Burnside gelöst, also die Fixpunkte beim 4 weißen und 5 schwarzen Quadraten gezählt. Das lautet bei mir wie folgt:
1) Identität: 126 Fixpunkte
2) Drehung um 90 Grad: 2 Fixpunkte
3) Drehung um -90 Grad: 2 Fixpunkte
4) Drehung um 180 Grad: 6 Fixpunkte
5) Spiegeln an 1. Diagonale: 8 Fixpunkte
6) Spiegeln an 2. Diagonale: 8 Fixpunkte
7) Spiegeln an Horizontalen: 12 Fixpunkte
8) Spiegeln an Vertikalen: 12 Fixpunkte
Somit ergibt sich für die Anzahl an nichtäquivalenten Färbungen mit 4 weißen und 5 schwarzen Quadraten: $\begin{eqnarray*} \frac{176}{8} = 22 \end{eqnarray*}$

Stimmt das oder ist das auch falsch?

24.09.2019, 09:06

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Studentu
5) Spiegeln an 1. Diagonale: 8 Fixpunkte
6) Spiegeln an 2. Diagonale: 8 Fixpunkte

Ich komme hier ebenfalls jeweils auf 12. Das macht in der Endabrechnung dann 23 statt 22.

P.S.: "Polya" kenne ich nicht, und kann daher dazu wenig sagen. So langsam ahne ich aber, was damit gemeint sein könnte - deine Exponenten für die $\begin{eqnarray*} x_k \end{eqnarray*}$ mit $\begin{eqnarray*} k>1 \end{eqnarray*}$ sind da sämtlich falsch, tatsächlich wird es wohl auf

$\begin{eqnarray*} \frac{1}{8}\left(x_1^9+2x_1^1x_4^2 + x_1^1x_2^4 + 4x_1^3x_2^3\right) = \frac{1}{8}\left((w+s)^9 + 2(w+s)(w^4+s^4)^2 + (w+s)(w^2+s^2)^4 + 4(w+s)^3(w^2+s^2)^3\right) \end{eqnarray*}$

hinauslaufen, mit Koeffizient 23 vor Monom $\begin{eqnarray*} w^4s^5 \end{eqnarray*}$ .

EDIT: Gelbe Karte wegen https://www.onlinemathe.de/forum/Polya-B...aerbungen-eines, das nächste mal dann Rot.

24.09.2019, 12:53

Studentu

Auf diesen Beitrag antworten »

Hallo Hal 9000, danke für deine Antwort!
Ich werde mir nochmal gründlich anschauen, wie du auf 12 kommst und ob bei Polya mit den anderen Exponenten dann auch 23 herauskommt. smile

Danke auch für die Warnung! Mir war nicht klar, dass hier crosspostings verboten sind (obwohl es wsl. in den Forenregeln steht, aber das ist schon so lange her, dass ich die gelesen habe) und nachdem ich dort einen ähnlichen Thread entdeckt hatte, dachte ich, ich stell die Frage auch dort. Wird aber selbstverständlich nicht wieder vorkommen, entschuldigung!

24.09.2019, 13:59

Studentu

Auf diesen Beitrag antworten »

Hallo nochmal!
Mit den 12 hattest du Recht, ich hatte 4 Fixpunkte übersehen. Nun komme ich auch auf 23. Gibt es einen Weg, wie man sich die Fixpunkte schnell überlegen kann oder muss man einfach eine Zeichnung anstarren und sich die Transformationen bildlich vorstellen?

Mit den Exponenten hattest du auch Recht! Es sind nicht die Anzahl an Elemente des entsprechenden Zyklentyps, sondern die Anzahl solcher Zyklen, die in den Exponenten wandert. Damit ergibt sich nun auch 23.

Vielen Dank für deine Hilfe und entschuldigung nochmals!

24.09.2019, 14:12

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Studentu
Gibt es einen Weg, wie man sich die Fixpunkte schnell überlegen kann

Man kann natürlich versuchen, unter festgelegten Rahmenbedingungen an das Problem dieses oder jenes Prinzip herauszuarbeiten - fragt sich nur, ob sich das lohnt: Dann kommt die nächste, dann doch erheblich andere Fragestellung um die Ecke, die diese Rahmenbedingungen sprengt, und man fängt von vorn an.

Was ich damit sagen will: Das sind i.d.R. keine Fragestellungen, die sich komplett mit Schema F bewältigen lassen. Burnside bzw. wohl auch dieses Polya geben den groben Rahmen vor, aber in der Detail-Zählarbeit hängt vieles doch sehr speziell vom genau vorliegenden Problem ab. Ist aber sicher keine neue Erkenntnis, wenn man sich generell komplexe kombinatorische Probleme anschaut. Augenzwinkern

24.09.2019, 20:36

Studentu

Auf diesen Beitrag antworten »

Verstehe. Sonst wäre es ja wohl auch ein bisschen langweilig. ^^ Danke dir! Freude

Neue Frage »

Antworten »

Polya, Burnside: nichtäquivalente Färbungen eines 3x3 Quadrates

Verwandte Themen