Collares bicolores – Conteo total

Seguimos con el tema de collares, pero sólo aquellos que están sometidos a giros planos, sin tener en cuenta simetrías. Hemos indicado que este otro caso, algo más complejo, lo dejamos como complemento.

Descubrimos en la entrada anterior que para n=7 existían 20 collares distintos, e igualmente se podría haber razonado que para n=6, caso que hemos estudiado exhaustivamente, serían 14.

Si consultas http://oeis.org/A000031 verás que los resultados son

N	0	1	2	3	4	5	6	7	8	9	10	11
C	1	2	3	4	6	8	14	20	36	60	108	188

Existe una fórmula, que puedes consultar en http://mathworld.wolfram.com/Necklace.html
para calcular esos números sin acudir a un análisis individual de cada collar. Es esta, adaptada al caso de 2 colores:

La variable d recorre todos los divisores de n desde 1 hasta n, y  φ(d)  es la función indicador de Euler que indica el total de números menores que d y primos con él incluido el 1.

Apliquemos la fórmula al caso 6:

Divisores: 1,2,3,6
Indicadores: φ(1)=1, φ(2)=1, φ(3)=2, φ(6)=2
Total: C=(1*26+1*23+2*22+2*21)/6=(64+8+8+4)/6=84/6=14, como ya sabíamos.

En el caso de 7:

Divisores:1,7
Indicadores: φ(1)=1, φ(7)=6
Total: C=(1*27+6*21)/7 = (128+12)/7 = 140/7 = 20, que también coincide.

Y aquí acabamos. El resto es cosa tuya. Puedes llegar por este camino hasta el Teorema de Enumeración de Polya.