sábado, 28 de febrero de 2009

Permutaciones con elementos repetidos

En nuestro artículo anterior, hemos supuesto que todos los elementos son diferentes. Supongamos que queremos encontrar todos los reordenamientos de tres pelotas verdes y dos azules. Aquí tenemos cinco elementos {a1,a2,v1,v2,v3}, donde a1 es la primera pelota azul y a2, la segunda; de igual manera con las "v". Así que podríamos pensar que el número de reordenamientos es 5!

Sin embargo, debes tomar en cuenta que al momento de reordenar, para nosotros nos dará lo mismo el reordenamiento a1-v2-v3-a2-v1 que el reordenamiento a2-v1-v2-a1-v3 ¡De cualquier forma veremos (en este orden) una pelota azul, dos verdes, una azul y una verde!

El secreto esta en que no importa que orden tomemos las pelotas verdes, ni las pelotas azules. Digamos que el numero de reordenamientos donde identificamos pelotas del mismo color es D. Sabemos que el numero de reordenamientos (permutaciones) de las pelotas, sin identificarlas por color es 5!. Ahora por cada reordenamiento de las pelotas donde identificamos las pelotas por color, tenemos 2! reordenamientos de pelotas azules y 3! de verdes, tomandolas sin identificarlas por colores. Entonces, llegamos a la fórmula

  • D*2!*3!=5!

De donde D=10. Una extraña coincidencia con nuestro ejemplo de combinaciones ¿No crees? No tanto. En el problema anterior identificamos a los dos niños que seleccionamos y a los tres que dejamos fuera. Así, los dos niños que escogemos se vuelven "del mismo color" y los tres restantes "del otro color".

En general si tenemos k tipos diferentes de objetos, cada uno con n_i elementos, i=1,2,...,k, es fácil ver que el numero de reordenamientos D donde identificamos elementos del mismo tipo esta dado por:

  • D*(n_1)!*(n_2)!*...*(n_k)!=(n_1+n_2+...+n_3)!

Para darte un ejemplo, toma 5 monedas de 50 ctvs, tres de a peso y 4 de cinco. ¿Cuántas maneras tienes de reordenarlas? Aquí tenemos 3 tipos diferentes de objetos. El primero tipo tiene 5 elementos, así que n_1=5; el segundo tiene 3, así que n_2=3; y por ultimo, el tercer tipo tiene 4 objetos, así que n_3=4. El total de objetos esta dado por n_1+n_2+...+n_3=5+3+4=12. Así que el numero de reordenamientos D, donde identificamos monedas del mismo tipo esta dado por

  • D*5!*3!*4!=12!

De donde D=27, 720 ¡Son demasiados! Y los calculamos en pocos segundos, increíble, ¿no?.

Como ejercicio, toma dos monedas de peso y tres de dos, y trata de encontrar los 10 posibles reordenamientos, identificando monedas del mismo tipo.