Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Polya, Burnside: nichtäquivalente Färbungen eines

Polya, Burnside: nichtäquivalente Färbungen eines

Universität / Fachhochschule

Binomialkoeffizienten

Graphentheorie

Kombinatorische Optimierung

Rekursives Zählen

Tags: Binomialkoeffizient, Burnside, Färbung, Graphentheorie, Kombinatorische Optimierung, permutation, Polya, Rekursives Zählen, Zyklentyp, Zyklenzeiger

StuMath aktiv_icon

02:32 Uhr, 24.09.2019

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 =

x_{1}^{9}

2): Drehung um 90 Grad: ZT =

x_{1}^{1} x_{4}^{8}

3): Drehung um 180 Grad: ZT =

x_{1}^{1} x_{2}^{8}

4): Drehung um 270 Grad: ZT =

x_{1}^{1} x_{4}^{8}

5): Spiegelung entlang 1. Diagonale: ZT =

x_{1}^{2} x_{2}^{6}

6): Spiegelung entlang 2. Diagonale: ZT =

x_{1}^{3} x_{2}^{6}

7): Spiegelung entlang Horizontalen: ZT =

x_{1}^{3} x_{2}^{6}

8): Spiegelung entlang Vertikalen: ZT =

x_{1}^{3} x_{2}^{6}

Also ergibt sich der Zyklenzeiger als

\frac{1}{8} (x_{1}^{9} + 2 x_{1}^{1} x_{4}^{8} + x_{1}^{1} x_{2}^{8} + 4 x_{1}^{3} x_{2}^{6})

.
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:

\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})

.
Das habe ich mit der verallgemeinerten Binomischen Formel umgeschrieben, um den Koeffizienten

[w^{4} s^{5}]

ablesen zu können. Dieser ergibt sich bei mir als:

\frac{1}{8} (b i n o m i a l (9, 4) + 0 + 0 + 0 + 0 + 0) = 15, 75

.
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:

\frac{176}{8} = 22

Stimmt das oder ist das auch falsch?

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Kombinatorik: Ziehen ohne Reihenfolge und ohne Zurücklegen

HAL9000

12:16 Uhr, 24.09.2019

Zur Information: www.matheboard.de/thread.php?threadid=592589

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1480896

1480889

	Status: nicht eingeloggt	Noch nicht registriert?