Encuentra cuántas pulseras circulares diferentes se pueden formar utilizando $6n$ azul y $3$ cuentas rojas, donde $n$ es un número entero positivo.

Question

Encuentra cuántas pulseras circulares diferentes se pueden formar utilizando $6n$ azul y $3$ cuentas rojas, donde $n$ es un número entero positivo.

---

Como se trata de permutaciones circulares en las que el volteo no supone ningún cambio $$ \frac{1}{2}\frac{(6n+2)!}{3!(6n)!}$$ Esto se simplifica a $$\frac{18n^2+9n+1}{6} $$ Pero la respuesta dada es $3n^2+3n+1$ .
Traté de pensar así que entre el $3$ rojas el número de cuentas azules se puede poner es número de solución integral a $$x+y+z=6n $$ Esto da $18n^2+9n+1$ . Seguramente estoy contando el mismo arreglo más de una vez. ¿Cómo puedo eliminarlas?

Answer 1

Aquí está la solución utilizando el Teorema de Enumeración de Polya (PET). En requerimos el índice de ciclo del grupo diedro que actúa sobre $m=6n+3$ ranuras. Observe que $m$ es impar. Así pues, tenemos para el índice del ciclo

$$Z(D_m) = \frac{1}{2m} \sum_{d|m} \varphi(d) a_d^{m/d} + \frac{1}{2} a_1 a_2^{(m-1)/2}.$$

La cantidad deseada viene dada por $$[A^{6n} B^3] Z(D_m)(A+B).$$

En realidad haciendo la sustitución obtenemos $$[A^{6n} B^3] \left(\frac{1}{2m} \sum_{d|m} \varphi(d) (A^d+B^d)^{m/d} + \frac{1}{2} (A+B) (A^2+B^2)^{(m-1)/2}\right).$$

Trabajando con el primer término vemos que podemos obtener $B^3$ sólo de los términos para $d=1$ y $d=3$ que da como resultado

$$\frac{1}{2m} [A^{6n} B^3] \left( (A+B)^m + 2(A^3+B^3)^{m/3} \right).$$

Esto es $$\frac{1}{2m} {m\choose 3} + \frac{1}{2m}2 {m/3\choose 1}.$$

Siguiendo con el segundo término debemos tener $B^2$ del término de potencia y obtener

$$\frac{1}{2} {(m-1)/2\choose 1}.$$

Si se reúnen las tres contribuciones, se obtiene

$$\frac{1}{12} (m-1)(m-2) + \frac{1}{3} + \frac{1}{4} (m-1) = \frac{1}{12} m^2 + \frac{1}{4} \\ = 3n^2+3n+1.$$

Answer 2

El problema es que el volteo puede dar como resultado la misma pulsera si se voltea a lo largo de una línea de simetría. El método general sería utilizar el teorema del conteo de órbitas (Wikipedia tiene un ejemplo en su artículo ). También se puede utilizar la inclusión-exclusión, pero casi siempre es más engorroso.

Aquí es lo suficientemente sencillo como para que podamos utilizar trucos ad-hoc para encontrar la respuesta. Considera cómo las cuentas rojas dividen a las azules:

1. Tres segmentos idénticos: $1$ formas.

2. Exactamente dos segmentos idénticos: $3n$ formas.

3. Tres segmentos diferentes: $\frac{\frac{1}{2}(6n+2)(6n+1)-1-3(3n)}{6} = 3n^2$ maneras, porque si se gira hasta que un rojo está en la parte superior, entonces hay $\frac{1}{2}(6n+2)(6n+1)$ formas de poner los otros dos, pero para evitar los casos anteriores hay que restar $1$ veces el número de vías en el caso 1 y $3$ veces el número de formas en el caso 2 (cada uno tiene 3 rotaciones distintas con el rojo en la parte superior).

El total es $3n^2 + 3n + 1$ .