lunes, 1 de abril de 2013

Permutaciones con repetición

Vamos a calcular de cuántas formas se puede crear un mosaico cuadrado con 96 baldosines verdes, tres granate y uno azul. Todos los baldosines asimétricos deben estar igualmente orientados.

Se trata de un problema de matemática combinatoria. El número total de mosaicos son las permutaciones con repetición de 100 elementos, de los cuales, uno se repite 96 veces, otro, tres veces, y el último aparece una sola vez.
 
Si ningún baldosín tuviera un identificador que lo hiciera asimétrico, habría que dividir el resultado por cuatro. Se comprende mejor comparando estos cuatro mosaicos:
 
Los cuatro mosaicos deben contabilizarse como uno, ya que girando cualquiera de ellos 90º, 180º o 270º, coincide con otro. Sin embargo, con baldosines asimétricos no ocurre esto:
 
Por ejemplo, al girar 90º el primer mosaico, las letras quedarán giradas y ya no coincidirá exactamente con el segundo mosaico; son dos mosaicos distintos.
 
Pongamos todo en una hoja de cálculo. En O3:O5 ponemos los baldosines que hay de cada color, y debajo, en O6, la suma. En O8 calcularemos el número total de mosaicos posibles.
 
En O8:
=FACT(O6)/(FACT(O3)*FACT(O4)*FACT(O5))     [Resultado: 15.684.900]
 
Todo parece ir bien, pero si en vez construir mosaicos de 10 x 10 los hacemos de 15 x 15, tendremos problemas. En este caso, el número total de baldosines por mosaico será de 225 y al calcular el factorial de 225 se producirá un error por desbordamiento. 
 
Hay que aplicar logaritmos, como se explicó en el artículo Combinatoria: Variaciones. El desarrollo matemático es como sigue:
 
Tomamos logaritmos:
 
Calculamos el antilogaritmo de la expresión anterior.
 
Desarrollando el exponente:
 
Ahora, tenemos que crear cuatro nombres accediendo a Fórmulas + Administrador de nombres:

 Verde  =FILA(DESREF(Hoja1!$A$1;;;Hoja1!$O$3))
 Granate  =FILA(DESREF(Hoja1!$A$1;;;Hoja1!$O$4))
 Azul  =FILA(DESREF(Hoja1!$A$1;;;Hoja1!$O$5))
 Baldosines  =FILA(DESREF(Hoja1!$A$1;;;Hoja1!$O$6))

Finalmente, sustituimos la fórmula de O8 por la siguiente:

En O8:
=10^(SUMAPRODUCTO(LOG10(Baldosines))-SUMAPRODUCTO(LOG10(Verde))-SUMAPRODUCTO(LOG10(Granate))-SUMAPRODUCTO(LOG10(Azul)))     [Resultado: 415.850.400]

Descargar archivo (S105-Mosaico.xlsx)

Descargar archivo (S105-Mosaico.xls)

No hay comentarios:

Publicar un comentario