Problema de colar com Burnside Lemma

Question

Quantos colares podem ser feitos com duas contas vermelhas, duas verdes e quatro violetas? (8 no total)

Usar o lema de Burnside é complicado para mim devido à minha falta de compreensão do lema. Quero conhecer o método passo a passo.

Answer 1

Começar com:

Nós temos $\frac{8!}{2!2!4!} = 420$permutações das oito contas. Iremos organizá-los em torno de um item de 8 contas, o que significa que precisamos usar o grupo diédrico$D_{16}$ e suas diversas ações.

Existem sete classes de conjugação entre os elementos deste grupo, vamos considerá-las separadamente.

• a ação de identidade não faz nada; todas as 420 possibilidades permanecem inalteradas sob esta ação
• o solteiro $1/2$a rotação gira em torno de quatro contas. Isso mantém as coisas na forma$abcdabcd$ inalterado, então neclackes gostam $VVRGVVRG$ ou $GVRVGVRV$conte para isso. Existem 12 colares.
• os dois $1/4$as rotações envolvem tudo em torno de duas contas; esta ação não deixa nenhuma entrada inalterada, uma vez que elas teriam que ser da forma$abababab$ e só temos duas contas vermelhas.
• os dois $1/8$as rotações colocam tudo em volta de uma conta; esta ação também não deixa nenhuma entrada inalterada, uma vez que temos mais de uma cor de cordão.
• os dois $3/8$as rotações envolvem tudo em torno de três contas; esta ação também não deixa nenhuma entrada inalterada, já que temos mais de uma cor de cordão.
• os quatro reflexos através de uma linha através das contas vira as coisas para frente e para trás de modo que duas contas permaneçam no lugar. Colares da forma$abcdedcb$permanecer inalterado por isso; já que só temos contagens pares de contas,$a = e$deve ser verdade. Ficamos com 12 entradas, como$VRGVVVGR$.
• os quatro reflexos através de uma linha entre as contas vira as coisas para frente e para trás, de forma que nenhuma conta fique no lugar. Estes parecem$abcddcba$, e há 12 entradas, como $VRGVVGRV$

Agora, aplicando o Lema de Burnside , existem

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

colares distintos.

Apresentada abaixo está a lista completa:

Esses 20 são completamente assimétricos:

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

esses seis são fixados sob um reflexo que passa entre as contas:

GRVVVVRG GVRVVRVG GVVRRVVG
RGVVVVGR VRGVVGRV RVGVVGVR

estes cinco são fixados sob um reflexo que passa por duas contas:

RGVVRVVG VRGVVVGR GRVVGVVR
VVRGVGRV VGVRVRVG

Finalmente, há um que é fixo sob rotação GRVVGRVVe outro que é fixo tanto sob rotação quanto através de reflexãoGVRVGVRV

Answer 2

Podemos também implantar PET aqui, pois precisamos do índice de ciclo $Z(D_8)$ do grupo diédrico $D_8$ de ordem $16$para aplicar Burnside. Calculamos e calculamos a média do número de atribuições de cores para os oito slots fixados por permutações de cada classe de conjugação em$D_8$, levando em consideração a ordem da aula. Isso significa que a atribuição é constante nos ciclos, então podemos colocar exatamente uma cor nas ranhuras de um determinado ciclo, substituindo$a_d$ do índice com $R^d + G^d + V^d,$ que é PET.

Consultando a seguinte ficha técnica sobre colares e pulseiras , obtemos o índice de ciclo do grupo diédrico$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.$$

Nós buscamos $$[R^2 G^2 V^4] Z(D_8; R+G+V).$$

Aqui assumimos que o OP pede a simetria total, ou seja, diedro, o que significa que o rótulo a ser usado é pulseira. Trabalhando através dos cinco termos no índice do ciclo, obtemos

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

Assim, obtemos nossa resposta

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