Problème de collier avec Burnside Lemma

Question

Combien de colliers peuvent être faits avec deux perles rouges, deux perles vertes et quatre perles violettes? (8 au total)

Utiliser le lemme de Burnside est compliqué pour moi en raison de mon manque de compréhension du lemme. Je veux connaître la méthode étape par étape.

Answer 1

Commencer avec:

Nous avons $\frac{8!}{2!2!4!} = 420$permutations des huit perles. Nous les organiserons autour d'un article à 8 perles, ce qui signifie que nous devons utiliser le groupe dièdre$D_{16}$ et ses différentes actions.

Il existe sept classes de conjugaison parmi les éléments de ce groupe, nous les considérerons tour à tour.

• l' action d' identité ne fait rien; les 420 possibilités restent inchangées sous cette action
• Le seul $1/2$la rotation met tout autour de quatre perles. Cela garde les choses de la forme$abcdabcd$ inchangé, donc neclackes comme $VVRGVVRG$ ou $GVRVGVRV$comptez pour cela. Il y a 12 de ces colliers.
• les deux $1/4$les rotations mettent tout autour de deux perles; cette action ne laisse aucune entrée inchangée, car elles devraient être de la forme$abababab$ et nous n'avons que deux perles rouges.
• les deux $1/8$les rotations mettent tout autour d'une perle; cette action ne laisse aucune entrée inchangée, car nous avons plus d'une couleur de perle.
• les deux $3/8$les rotations mettent tout autour de trois perles; cette action ne laisse pas non plus aucune entrée inchangée, car nous avons plus d'une couleur de perle.
• les quatre reflets sur une ligne à travers des perles font basculer les choses d'avant en arrière pour que deux perles restent en place. Colliers de la forme$abcdedcb$rester inchangé à travers cela; puisque nous n'avons que des nombres égaux de perles,$a = e$doit être vrai. Il nous reste 12 entrées telles que$VRGVVVGR$.
• les quatre reflets sur une ligne entre les perles font basculer les choses d'avant en arrière pour qu'aucune perle ne reste en place. Ceux-ci ressemblent à$abcddcba$, et il y a 12 entrées de ce type, telles que $VRGVVGRV$

Maintenant, en appliquant le lemme de Burnside , il y a

$$\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$$

colliers distincts.

Vous trouverez ci-dessous la liste complète:

Ces 20 sont complètement asymétriques:

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

ces six sont fixés sous une réflexion qui passe entre les billes:

GRVVVVRG GVRVVRVG GVVRRVVG
RGVVVVGR VRGVVGRV RVGVVGVR

ces cinq sont fixés sous une réflexion qui passe à travers deux billes:

RGVVRVVG VRGVVVGR GRVVGVVR
VVRGVGRV VGVRVRVG

Enfin, il y en a un qui est fixe en rotation GRVVGRVVet un qui est fixé à la fois sous rotation et à travers la réflexionGVRVGVRV

Answer 2

Nous pouvons aussi bien déployer PET ici car nous avons besoin de l'indice de cycle $Z(D_8)$ du groupe dièdre $D_8$ d'ordre $16$pour appliquer Burnside. Nous calculons et faisons la moyenne du nombre d'attributions de couleurs aux huit emplacements fixés par les permutations de chaque classe de conjugaison dans$D_8$, en tenant compte de l'ordre de la classe. Cela signifie que l'affectation est constante sur les cycles, nous pouvons donc placer exactement une couleur dans les fentes d'un cycle donné, en substituant$a_d$ de l'index avec $R^d + G^d + V^d,$ qui est le PET.

Consulter la fiche d'information suivante sur les colliers et les bracelets que nous obtenons pour l'indice de cycle du groupe dièdres$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.$$

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

Ici, nous supposons que l'OP demande la symétrie complète, c'est-à-dire le dièdre, ce qui signifie que l'étiquette à utiliser est le bracelet. En parcourant les cinq sternes de l'indice de cycle, nous obtenons

• $\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.$$

Nous obtenons donc pour notre réponse

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