martes, 1 de abril de 2008

Permutaciones circulares repetición

Expresión cerrada para el numero de permutaciones circulares con elementos repetidos para cualquier multiconjunto de elementos. Su fórmula es:
(1/N)Suma(phi(d)(N/d)!/((b1/d)!(b2/d)!(b3/d)!), dB)
Esta suma está extendida a todos los divisores de B
N=Suma de todas las bolas de distintos colores b_1+b_2+b_3
Phi(d) es Euler totient para cada divisor de B
B=mcd(b_1,b_2,b_3)

d=divisores de B
Si el máximo común divisor de los bi es 1, esto se reduce a (N-1)!/(b1! b2!b3!).


Apliquemos esto al caso de 20 bolas 4 de un color,6 de otro y 10 de otro
Mcd(4,6,10)=2 por lo que la suma hemos de extenderla a los divisores de 2
que son 1 y 2
Para el 1 phi(1)*N/1=1*20=20
Para el 2 phi(2)*N/2=1*10=10 y la formula con estos dos sumandos quedará:
(1/20)*[20!/4!6!10!+10!/2!3!5!]=1940064


Todo esto lo tenemos ampliado aqui:
En este hilo se obtenia una
expresión cerrada para el numero de permutaciones circulares con elementos repetidos para cualquier multiconjunto de elementos
http://groups.google.es/group/es.ciencia.matematicas/browse_thread/thread/99cfa637abc4d3dc/8a9e0da5c29b2cdc?hl=es&lnk=gst&q=elementos+repetidos#8a9e0da5c29b2cdc.

Si aplicamos lo que creo nos indica el hilo de arriba al caso de 3 bolas de un color y 3 de otro tenemos
N=3+3=6
B=Mcd(3,3)=3 y la suma que nos indica la fórmula (1/N)Suma(phi(d)(N/d)!/((b1/d)!(b2/d)!(b3/d)!), dB) hay
que extenderla a los divisores de 3 es decir al 1 al 3.
Para el 1 phi(1)*(N/1)!=1*6=6
Para el 3 phi(3)*(N/3)!=2*(6/3)!=2*2! 4 con lo que quedaria:
(1/6)(phi(1)(6/1)!/((3/1)!(3/1)!) + phi(3)(6/3)!/((3/3)!(3/3)!)) =
(1/6)(6!/(3!3!) + 2*2!/(1!1!)) = (1/6)(20 + 4) = 24/6 = 4
Que es lo que obteniamos para el número de permutaciones circulares. Quedaban reducidas a 3, considerando la simetría.
Aquí tenemos:
http://theory.cs.uvic.ca/gen/neck.html
que salen 3 para los brazalets y 4 para los Necklaces
A bracelet is a necklace that can be turned over.

1 comentario:

Anónimo dijo...

Muy, pero que muy útil. Estuve tiempo intentando encontrar cómo hacer Permutaciones Circulares con Repetición y nada. Además está muy bien explicado. Gracias por el artículo.

Jorge (jorgeberbel@hotmail.com)