jueves, 17 de junio de 2010

Permutaciones con repetición

Recordemos primero las Permutaciones ....

Pensemos que queremos permutar las letras en la palabra AMOR.

Existen 4! formas de hacerlo.

Podemos pensar que si tuviésemos que ubicar cada una de estas cuatro letras en un set de 4 casillas, en la primer casilla podemos poner 4 letras (están todas para elegir), en la segunda casilla, sólo 3 de las letras (porque una fue elegida) y así, en la que viene 2 letras y una última en la cuarta casilla. Es decir, tenemos: 4 x 3 x 2 x 1 = 24 posibilidades = 4 !

Veamos esas 24 posbilidades:

OMAR AMOR MAOR MOAR AOMR OAMR RAOM ROAM
MROA MRAO MORA MARO ORMA ARMO AROM ORAM
RMOA RMAO ROMA RAMO OMRA AMRO AORM OARM

Pero que pasa si tuviésemos que permutar las letras de la palabra AMAR .... Aquí es donde aparacen las:

PERMUTACIONES con REPETICIÓN:

Si sustituimos "O" por "A", en la matrzi anterior tendremos varias repeticiones, veamos:

AMAR AMAR MAAR MAAR AAMR AAMR RAAM RAAM
MRAA MRAA MARA MARA ARMA ARMA ARAM ARAM
RMAA RMAA RAMA RAMA AMRA AMRA AARM AARM


Destacamos en azul, las palabras que se repiten .... Y si las tachamos, tendremos solamente la mitad:

AMAR MAAR AAMR RAAM

MRAA MARA ARMA ARAM

RMAA RAMA AMRA AARM

Son 12, la mitad de las palabras que se tenían en la permutación de las letras en AMOR ....

Hay (4! / 2! = 12) permutaciones distinguibles que se pueden lograr con la palabra "AMAR".

Generalizando:

PERMUTACIONES CON REPETICION:

El número de permutaciones distintas de n objetos de los cuales n1 son de una clase, n2 de una segunda clase, ...., nk de una k-ésima clase y los demás objetos de calse 1, se calcula por:


2 comentarios: