collar único de 6 cuentas

Question

Estoy tratando de calcular el número de pulseras únicas de longitud $6$ que se puede hacer de $6$ cuentas de diferentes colores. Una cuenta del mismo color puede repetirse y utilizarse tantas veces como lo permita la longitud.

Mi intento inicial:

He subdividido la pulsera única en ciertas combinaciones como

$AAAAAA$ (donde $A$ es la misma cuenta de color) que sólo puede haber $6$ pulseras únicas. $AAAAAB$ (donde $A$ es un color $1$ y B es un color $2$ cuenta) que sólo puede haber $6\cdot5$ ( $30$ brazalete)

... y demás, resumí los resultados en esta tabla:

Terminé con $3267$ combinaciones únicas. ¿Es este un cálculo correcto?

Además, ¿hay una forma mejor de calcular este problema?

Answer 1

Paul Raff dio una fórmula tanto para los brazaletes como para los collares, así que en mi respuesta proporcionaré un método general que puedes utilizar para este tipo de problema. También funciona si quieres colorear un cubo por ejemplo.

Como ha señalado Paul Raff, te has confundido entre la pulsera y el collar, así que en mi respuesta incluiré la respuesta para ambos.

---

¿En qué te has equivocado?

Me parece que estás contando el número de formas de colorear una pulsera en lugar de un collar, así que he comprobado tu cálculo con respecto a la coloración de una pulsera. Diría que el principal problema de tu recuento es que, incluso para cada caso de la base, no siempre se puede garantizar que se obtenga el resultado final para ese caso multiplicando como has hecho. Por ejemplo, en el caso de $A^2B^2C^2$ Consideramos dos iteraciones siguientes:

El de la izquierda da $\frac{6\cdot5\cdot 4}{3!}=\frac{120}{6}$ formas de elegir tres colores $A,B,C$ que es lo que has dado en tu tabla. Sin embargo, la de la derecha da $\frac{6 \cdot 5 \cdot 4}{2}=\frac{120}{2}$ formas de elegir tres colores $A,B,C$ .

Colorear el collar

Puede utilizar Lema de Burnside donde puedes contar el número de formas de colorear el objeto mirando su grupo de simetría $G$ . Para el collar El grupo $G$ puede ser:

• Se considera que dos coloraciones del collar son iguales si a partir de una de ellas podemos girar el collar para llegar al otro colorido. Hay $5$ posibles rotaciones en los ángulos $60^{\circ}\cdot i \; (i=1,2,3,4,5)$ (sin incluir la rotación de no hacer nada). Por lo tanto, estas cinco rotaciones son del conjunto mencionado $G$ .
• La acción de "no hacer nada", es decir, no hacemos nada al collar. Esto también está en $G$ .

Dejemos que $X$ sea el conjunto de todas las coloraciones posibles para el collar en una orientación fija. De este modo $|X|=6^6$ ya que hay $6$ colores posibles para cada cuenta.

Ahora, en el lema de Burnside, esencialmente queremos contar el número de coloraciones de $X$ que permanece sin cambios bajo las acciones de $G$ . En particular:

• ¿Cuántos colorantes en $X$ para el collar para que siga siendo el mismo color después de que apliquemos $60^{\circ}$ ¿rotación al collar? Esto sólo ocurre cuando todas las cuentas tienen el mismo color. Por lo tanto, hay $6$ posibles coloraciones en este caso.

• La misma pregunta puede hacerse para $120^{\circ}$ rotación: Esto ocurre cuando tres de las cuentas (cada una a una distancia de la otra) tienen el mismo color y las tres restantes tienen el mismo color. Hay $6$ colores posibles para las tres primeras cuentas y hay $6$ otros posibles colores para el resto $6$ cuentas. Esto nos da $6^2$ posibles coloraciones.

• Del mismo modo, con $180^{\circ}$ rotación, una coloración se fija bajo esta rotación cuando cualquier par de cuentas opuestas tienen el mismo color. Hay $6$ formas de colorear cada par de cuentas opuestas para que haya $6^3$ posibles coloraciones.

• Con $240^{\circ}$ rotación, es lo mismo que $120^{\circ}$ por lo que tenemos $6^2$ posibles coloraciones. Con $300^{\circ}$ es lo mismo que $60^{\circ}$ por lo que tenemos $6$ posibles coloraciones.

• Con la acción "no hacer nada", todos los colores permanecen inalterados después de esta acción, por lo que hay $6^6$ posibles coloraciones.

El lema de Burnside dice que se pueden sumar todos estos números y dividirlos por el número de elementos de $G$ (que es $6$ ) para obtener todas las coloraciones posibles. Por lo tanto, la respuesta para colorear un collar es $$\frac{6^6 \cdot 1 +6 \cdot 2+ 6^2 \cdot 2+6^3 \cdot 1}{6}=7826.$$

Colorear la pulsera

La diferencia entre pulseras y collares está en el grupo de simetría $G$ . En particular, para las pulseras, $G$ tiene algunos elementos adicionales: Dos coloraciones de la pulsera se consideran iguales si a partir de una de ellas podemos reflejar la pulsera a través de una línea para obtener la otra coloración. Hay dos tipos de líneas:

• Una línea que une dos cuentas opuestas (véase el diagrama de la derecha). Hay $3$ pares de cuentas opuestas para que haya tres reflexiones a través de este tipo de líneas. Estas acciones están en $G$ .
• Una línea que divide el $6$ cuentas en partes iguales (diagrama de la izquierda). Hay $3$ tales líneas correspondientes a tres reflexiones adicionales en $G$ .

Esta vez $G$ tiene $12$ elementos.

A continuación, hacemos lo mismo con el collar, es decir, contamos el número de coloraciones que permanece fijo bajo estos reflejos:

• Para la reflexión a través del eje de la izquierda, dos cuentas que aparezcan simétricamente a través de ese eje deben tener el mismo color. Hay $3$ pares de tales cuentas para que haya $6^3$ posibles coloraciones. Como hay tres ejes de este tipo, tenemos $3 \cdot 6^3$ .
• En el caso de la reflexión a través del eje de la derecha, hay que tener en cuenta que podemos elegir libremente cualquier color para las cuentas que pasan por el eje, manteniendo el mismo colorido de la pulsera al reflejar. Por lo tanto, esto da $6^2$ para esas dos cuentas, y $6^2$ para $2$ pares de cuentas simétricas. Obtenemos $6^4$ posibles coloraciones para dicho eje. Como hay tres ejes de este tipo es $3 \cdot 6^4$ .

Ahora, aplicando el lema de Burnside, sumamos todos estos números contados para cada elemento en $G$ entonces dividimos por el número de elementos en $G$ (que es $12$ ). La respuesta final es $$\frac{1}{12}\left( 6^6 \cdot 1+6 \cdot 2+ 6^2 \cdot 2+6^3 \cdot 1+6^3 \cdot 3+ 6^4 \cdot 3 \right)=4291.$$

Answer 2

Sus referencias al título collares pero su contenido y sus ejemplos parecen hablar de pulseras . Hay una distinción entre los dos que se trata en este artículo de Wikipedia junto con una fórmula útil.

En resumen, una pulsera permite que dos configuraciones sean equivalentes si una se refleja en la otra (como sacarla de la muñeca y darle la vuelta). Así que el número de pulseras será como máximo el número de collares, en igualdad de condiciones.

El número de collares con $n$ cuentas totales, creadas a partir de un máximo de $k$ diferentes tipos de cuentas, es

$$N_k(n)=\frac{1}{n}\sum_{d\mid n}\varphi(d)k^\frac{n}{d}$$

Dónde $\varphi$ es la Función Totiente. Véase este artículo para una explicación de esta fórmula.

A partir de esto, obtenemos el número de pulseras a través de

$$B_k(n) = \begin{cases} \tfrac12 N_k(n) + \tfrac14 (k+1)k^\frac{n}{2} & \text{if }n\text{ is even} \\[10px] \tfrac12 N_k(n) + \tfrac12 k^\frac{n+1}{2} & \text{if }n\text{ is odd} \end{cases}$$

Si se combina todo esto, el número de collares con 6 cuentas en total, utilizar como máximo 6 cuentas únicas es

$$ N_6(6) = \frac{1}{6}\left( 1 \cdot 6^6 + 1 \cdot 6^3 + 2 \cdot 6^2 + 2 \cdot 6^1\right) = 7826 $$

y el número de pulseras con 6 cuentas en total, usar como máximo 6 cuentas únicas es

$$ B_6(6) = \frac{1}{2} N_6(6) + \frac{1}{4}(7)6^{3} = 4291 $$

Es difícil saber dónde te has equivocado en tus cálculos; por un lado, en el $AAAAAA$ escenario sólo hay un collar/pulsera único. No importa la forma en que lo gires/rotes, siempre tiene el mismo aspecto.

Answer 3

Bueno, podemos hacer un trabajo de caso sobre las formas en que se puede girar para ser único (que puede ser $1,2,3,6$ ).

1) Hay $6$ combinaciones.

2) Hay $\frac{6^2-6}2=15$ combinaciones.

3) Hay $\frac{6^3-6}3=70$ combinaciones.

6) Hay $\frac{6^6-6-6^2-6^3+12}6=7735$ combinaciones.

El número total de combinaciones es $7735+70+15+6=\boxed{7826}.$