Número de collares distintos con $12$ cuentas, cada cuenta roja o azul (¡las rotaciones no cuentan!)

Question

Supongamos que quiero formar un collar de 12 cuentas de manera que cada una de ellas sea roja o azul. Los collares que se diferencian por un giro se consideran iguales y las cuentas del mismo color son indistinguibles. ¿Cuántos collares distintos puedo hacer de esta manera?

---

Mi planteamiento de este problema es el siguiente. Sólo tenemos que considerar los casos en los que el número de cuentas rojas está entre $0$ y $6$ ya que el resto de los casos son simétricos. Si el número de cuentas rojas es $0,1,2$ el número de collares se encuentra fácilmente para ser $1,1,6$ respectivamente. Para $3$ a $6$ leer cuentas el recuento se hace más difícil. Así que supongamos que tenemos $k$ cuentas rojas (así $12-k$ cuentas azules). Empezando por alguna cuenta roja y moviéndose en el sentido de las agujas del reloj, deja que el número de cuentas azules entre cuentas rojas consecutivas sea $x_1,x_2,...,x_k$ (son enteros no negativos). Necesitamos $x_1+...+x_k=12-k$ y por lo tanto el número de collares con $k$ cuentas de lectura es el número de conjuntos (recordemos que los elementos de un conjunto no están ordenados) de $k$ enteros no negativos con suma $12-k$ que llamaremos $f(k)$ . Así que la respuesta al problema se suma desde $k=0$ a $5$ de $2f(k)$ , además $f(6)$ . El problema es encontrar $f(k)$ . ¿Quizás este sea el enfoque equivocado?

Answer 1

Deberías usar el lema de Burnside.

Hay $4$ rotaciones de orden $12$ . Cada uno de ellos estabiliza $2$ colores.

Hay $2$ rotaciones de orden $6$ . Cada uno de ellos estabiliza $4$ colores.

Hay $2$ rotaciones de orden $4$ . Cada uno de ellos estabiliza $8$ colores.

Hay $2$ rotaciones de orden $3$ . Cada uno de ellos estabiliza $16$ colores.

Hay $1$ rotación del orden $2$ . Cada uno de ellos estabiliza $64$ colorantes

Hay $1$ rotación del orden $1$ . Estabiliza el $4096$ colores.

Ahora aplicamos Burnside y obtenemos:

$\frac{4\cdot2+2\cdot4+2\cdot8+2\cdot16+1\cdot64+1\cdot 4096}{12}=352$ collares.

Answer 2

El teorema de Polya es más potente que el teorema de Burnside, porque entonces no hay que considerar cómo actúa el grupo de simetría sobre las coloraciones, sino que sólo hay que considerar cómo actúa sobre la estructura que está coloreada, lo cual es mucho más fácil.

Esto funciona de la siguiente manera. Para cada elemento del grupo de rotación, se calcula cómo la aplicación repetida de ese elemento al collar dividirá las cuentas en grupos que se mapean entre sí. Por ejemplo, si rotamos por $2 \pi/6$ entonces esto mapea cada cuenta a su segunda vecina, por lo tanto si aplicamos repetidamente este mapeo dividimos el collar en dos conjuntos de 6 cuentas. Entonces decimos que bajo la acción de ese elemento del grupo de rotación tenemos dos órbitas de longitud 6. Lo que se hace entonces es escribir el término:

$$T_{1}^{n_1}T_{2}^{n_2}T_{3}^{n_3}\ldots$$

cuando hay $n_k$ órbitas de longitud $k$ . Así, para el caso de la rotación por $2\pi/6$ , tiene el término $T_6^2$ . Sumando todos los términos de todos los elementos del grupo y dividiendo por el número de elementos del grupo se obtiene el polinomio de índice de ciclo del grupo. Entonces podemos hacer un recuento ponderado de coloraciones tal que el peso es el producto de alguna función arbitraria $w$ de cada color de cada cuenta. El teorema de Polya dice que hay que tomar el polinomio de índice de ciclo y sustituir $T_i$ por la suma de las potencias ith de los pesos asociados a cada color.

El polinomio de índice de ciclo para este problema viene dado por:

$$\frac{1}{12}\left[T_{1}^{12} + T_{2}^6 + 2 T_{3}^4 + 2 T_{4}^3 + 2 T_{6}^2 + 4 T_{12}\right]$$

Si damos a cada color un peso de 1, entonces podemos sustituir el $T_n$ por el número total de colores, así que puedes poner $T_i = 2$ . Pero también se puede dar a una cuenta roja un peso de x, entonces se obtiene un polinomio (que se llama función generadora). El coeficiente de $x^r$ es entonces el número total de coloraciones con r cuentas rojas. Para ello, es necesario poner:

$$T_{k} = 1 + x^k$$

La función generadora viene dada, pues, por:

$$S(x) = \frac{1}{12}\left[\left(1+x\right)^{12} +\left(1+x^2\right)^6 + 2 \left(1+x^3\right)^4 + 2 \left(1+x^4\right)^3 + 2 \left(1+x^6\right)^2 + 4 \left(1+x^{12}\right)\right]$$

Por ejemplo, el coeficiente de $x^6$ es 80, por lo que hay 80 collares con exactamente 6 cuentas rojas y 6 azules.