Halskettenproblem mit Burnside Lemma

Question

Wie viele Halsketten können mit zwei roten Perlen, zwei grünen Perlen und vier violetten Perlen hergestellt werden? (Insgesamt 8)

Die Verwendung des Burnside-Lemmas ist für mich aufgrund meines mangelnden Verständnisses des Lemmas kompliziert. Ich möchte die Methode Schritt für Schritt kennenlernen.

Answer 1

Beginnen mit:

Wir haben $\frac{8!}{2!2!4!} = 420$Permutationen der acht Perlen. Wir werden sie um einen 8-Perlen-Gegenstand herum anordnen, was bedeutet, dass wir die Diedergruppe verwenden müssen$D_{16}$ und seine verschiedenen Aktionen.

Es gibt sieben Konjugationsklassen unter den Elementen dieser Gruppe, wir werden sie der Reihe nach betrachten.

• die Identitätsaktion macht nichts; Alle 420 Möglichkeiten bleiben bei dieser Aktion unverändert
• der Single $1/2$Rotation schreitet alles um vier Perlen. Dies hält die Dinge in Form$abcdabcd$ unverändert, so neclackes wie $VVRGVVRG$ oder $GVRVGVRV$zählen dafür. Es gibt 12 solcher Halsketten.
• die Zwei $1/4$Rotationen schreiten alles um zwei Perlen; Diese Aktion lässt keine Einträge unverändert, da sie die Form haben müssten$abababab$ und wir haben nur zwei rote Perlen.
• die Zwei $1/8$Rotationen schreiten alles um eine Perle; Diese Aktion lässt auch keine Einträge unverändert, da wir mehr als eine Perlenfarbe haben.
• die Zwei $3/8$Rotationen schreiten alles um drei Perlen; Diese Aktion lässt auch keine Einträge unverändert, da wir mehr als eine Perlenfarbe haben.
• Die vier Reflexionen über eine Linie durch Perlen drehen die Dinge hin und her, so dass zwei Perlen in Position bleiben. Halsketten der Form$abcdedcb$bleiben dadurch unverändert; da wir nur gleich viele perlen haben,$a = e$muss wahr sein. Wir haben noch 12 Einträge wie$VRGVVVGR$.
• Die vier Reflexionen über eine Linie zwischen den Perlen drehen die Dinge hin und her, sodass keine Perlen in Position bleiben. Diese sehen aus wie$abcddcba$und es gibt 12 solcher Einträge, wie z $VRGVVGRV$

Jetzt, wo Burnside's Lemma angewendet wird , gibt es

$$\frac{1\cdot420 + 1\cdot12 + 2\cdot0 + 2\cdot0 + 2\cdot0 + 4\cdot12 + 4\cdot12}{1+1+2+2+2+4+4} = \frac{528}{16} = 33$$

verschiedene Halsketten.

Unten ist die vollständige Liste dargestellt:

Diese 20 sind völlig asymmetrisch:

GGRRVVVV GGRVRVVV GGRVVRVV
GGRVVVRV GGVRRVVV GGVRVRVV
GRGRVVVV GRGVRVVV GRRVGVVV
GRRVVGVV GRRVVVGV GRVGRVVV
GRVGVRVV GRVGVVRV GRVGVVVR
GRVRVGVV GRVRVVGV GRVVGVRV
GRVVRVGV GVGVRRVV

Diese sechs sind unter einer Reflexion fixiert, die zwischen den Perlen verläuft:

GRVVVVRG GVRVVRVG GVVRRVVG
RGVVVVGR VRGVVGRV RVGVVGVR

Diese fünf sind unter einer Reflexion fixiert, die durch zwei Perlen verläuft:

RGVVRVVG VRGVVVGR GRVVGVVR
VVRGVGRV VGVRVRVG

Schließlich gibt es eine, die unter Rotation fixiert ist, GRVVGRVVund eine, die sowohl unter Rotation als auch durch Durchreflexion fixiert istGVRVGVRV

Answer 2

Wir können hier auch PET einsetzen, da wir den Zyklusindex benötigen $Z(D_8)$ der Diedergruppe $D_8$ der Ordnung $16$Burnside anwenden. Wir berechnen und mitteln die Anzahl der Zuordnungen von Farben zu den acht Slots, die durch Permutationen aus jeder Konjugationsklasse in festgelegt sind$D_8$unter Berücksichtigung der Reihenfolge der Klasse. Dies bedeutet, dass die Zuordnung in den Zyklen konstant ist, sodass wir genau eine Farbe in die Schlitze eines bestimmten Zyklus einfügen können, indem wir sie ersetzen$a_d$ aus dem Index mit $R^d + G^d + V^d,$ Das ist PET.

Den folgenden Index zu Halsketten und Armbändern finden Sie im Zyklusindex der Diedergruppe$D_8$

$$Z(D_8) = \frac{1}{16} a_1^8 + \frac{1}{4} a_1^2 a_2^3 + \frac{5}{16} a_2^4 + \frac{1}{8} a_4^2 + \frac{1}{4} a_8.$$

Wir suchen $$[R^2 G^2 V^4] Z(D_8; R+G+V).$$

Hier nehmen wir an, dass das OP nach der vollen Symmetrie fragt, dh nach Dieder, was bedeutet, dass das zu verwendende Etikett Armband ist. Wir arbeiten uns durch die fünf Seeschwalben im Zyklusindex, den wir erhalten

• $\frac{1}{16} a_1^8$ $$[R^2 G^2 V^4] \frac{1}{16} (R+G+V)^8 = \frac{1}{16} {8\choose 2,2,4}$$
• $\frac{1}{4} a_1^2 a_2^3$ $$[R^2 G^2 V^4] \frac{1}{4} (R+G+V)^2 (R^2 + G^2 + V^2)^3 \\ = [R^2 G^2 V^4] \frac{1}{4} (R^2 + G^2 + V^2) (R^2 + G^2 + V^2)^3 \\ = [R^2 G^2 V^4] \frac{1}{4} (R^2 + G^2 + V^2)^4 \\ = [R G V^2] \frac{1}{4} (R + G + V)^4 = \frac{1}{4} {4\choose 2,1,1}.$$
• $\frac{5}{16} a_2^4$ $$[R^2 G^2 V^4] \frac{5}{16} (R^2 + G^2 + V^2)^4 = \frac{5}{16} {4\choose 2,1,1}.$$
• $\frac{1}{8} a_4^2$ $$[R^2 G^2 V^4] \frac{1}{8} (R^4 + G^4 + V^4)^2 = 0.$$
• $\frac{1}{4} a_8$ $$[R^2 G^2 V^4] \frac{1}{4} (R^8 + G^8 + V^8) = 0.$$

Wir bekommen also für unsere Antwort

$$\frac{1}{16} {8\choose 2,2,4} + \frac{9}{16} {4\choose 2,1,1} = \bbox[5px,border:2px solid #00A000]{33.}$$