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.

2 comentarios:

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)

polo outlet dijo...

http://www.burbagssale2014.com/ Burberry Outlet
http://www.airmaxshoesfactory.com/ Air Max Shoes
http://www.coachblackfriday2014.com/ Coach Black Friday
http://www.coach-storeoutletonline.com/ Coach Black Friday
http://www.coachcoachoutlet.com/ Coach Cyber Monday
http://www.coachxfactory.com/ Coach Factory
http://www.coach-factoryoutletonline.net/ Coach Outlet Factory
http://www.coach-outletonlineusa.com/ Coach Outlet USA
http://www.coach-pursesfactory.com/ Coach Purses Factory
http://www.coachpurseusa.com/ Coach Purses USA
http://www.coach-storeoutlet.com/ Coach Store Outlet
http://www.coach-pursesonline.com/ Coach Purses On Sale
http://www.monsterbeatsbydres.com/ Monster Beats Outlet
http://www.louis-vuittonblackfriday.com/ Louis Vuitton Outlet
http://www.lv-guccishoesfactory.com/ Louis Vuitton Factory
http://www.marcjacobsonsale.com/ Marc Jacobs On Sale
http://www.mcmworldwides.com/ MCM Outlet
http://www.mcmoutlet-jp.com/ MCM 店铺
http://www.oakleysunglassesfactory.com/ cheap oakley sunglasses
http://www.michael-korsmas.com/ Michael Kors Outlet
http://www.michaelkors.so/ Michael Kors Outlet
http://www.michaelkorsfactory-store.com/ Michael Kors Factory
http://www.michaelkorsoutletr.com/ Michael Kors Outlet
http://www.michael-korsfactoryonline.com/ Michael Kors Factory Online
http://www.newcoachfactoryoutlet.com/ Coach Factory Outlet
http://www.north-faceoutletonlines.net/ North Face Outlet Online
http://www.polo-outletstore.com/ Polo Outlet Store
http://www.ralph-laurenhome.com/ Ralph Lauren UK
http://www.saclongchamppairs.com/ Sac Longchamp Pairs
http://www.tcoachoutletonline.com/ Coach Outlet Online
http://www.the-coachfactoryoutlet.com/ Coach Factory Oultet
http://www.barbour-jacketsoutlet.com/ Barbour Jackets Outlet Online
http://www.canada-gooser.com/ Canada Goose Outlet
http://www.guccishoesuk-2014.com/ Gucci Outlet Online
http://www.michaelkorsstates.com/ Michael Kors Outlet
http://www.moncler-clearance.com/ Moncler Clearance
http://www.moncler-jacketsoutletonline.com/ Moncler Jackets Outlet Online
http://www.northsclearance.com/ North Clearace Outlet
http://www.polo-ralphlaurenonline.com/ Polo Ralph Lauren Outlet Online
http://www.woolrich-clearance.com/ Woolrich Clearance
http://www.cvshopfactory.com/ shop.coachfactory.com
http://www.mksfactoryoutlet.com/ Michael Kors Factory Outlet
http://www.zxcoachoutlet.com/ Coach Outlet Online USA
http://www.thebeatsbydre.net/ Beats by Dre
http://www.superbagsmarket.com/ Coach Outlet Online
http://www.nike-jordanshoes.com/ Nike Jordan Shoes
http://www.newoutletonlinemall.com/ Coach Purses Outlet Online
http://www.clickmichaelkors.com/ Michael Kors USA