permutacion

 PERMUTACIONES 
 *   Permutaciones:
Se llama permutación de n elementos a cada una de las diferentes ordenaciones  que se pueden hacer con esos elementos.  Ejemplo :
  {a, b, c}  Elementos
  Permutaciones:  (abc), (acb), (bac), (bca), (cab), (cba)    
 El número de permutaciones  de  n elementos es:  n !. En nuestro ejemplo tenemos 3 elementos, y por tanto, la cantidad de permutacionesposibles es 3!, o sea, 6.
  * Inversión:
Dada una permutación, diremos que dos elementos están en inversión cuando su orden difiere del de la permutación principal. 
   Ejemplo:  Consideremos los elementos  (1, 2, 3, 4, 5).
Llamamos  a (12345)  permutación principal,   entonces  en (21345) los elementos 1, 2 están en inversión.
  *  Permutación par e impar:
   Dada una permutación se dice que esde orden par cuando tiene un número par de inversiones.
   Dada una permutación se dice que es de orden impar cuando tiene un número impar de inversiones.
     Ejemplo: Partiendo de la permutación principal (12345)
   (21345) es de orden impar   (una inversión)
    (21354) es de orden par  (dos inversiones)
  A partir de esto es muy interesante si nos dan una cierta permutación, p.ej. (34215), poder decir de cuántas inversiones está formada. 
   El método de hacerlo es el siguiente:  
  Comenzando por la izquierda se van comparando cada elemento con los de su derecha, contando con los dedos de la mano  cada vez que nos encontramos con una inversión:
 ¿ Es inversión 34? No.    ¿32? Sí (1).    ¿31? Sí (2).   ¿35? No.  Y a continuación se continúa con el 4 y los elementos de suizquierda, aparecen otras dos inversiones más (4), después pasamos al 2 con el 1 que sí es inversión (5), el 25 que no lo es, y finalmente el 15 que tampoco lo es. Por tanto, la permutación (34215) está formada de 5 inversiones, y es llamada permutación impar.
  Finalmente, es reseñable el hecho de que si se cambian entre sí dos elementos de una permutación, ésta cambia de orden.
  Por ejempo, yasabemos que (34215) es de orden impar,  entonces  (34251) es de orden par. Observe que hemos cambiado sólo las posiciones de 1 y 5.

Combinaciones y permutaciones
¿Qué diferencia hay?
Normalmente usamos la palabra "combinación" descuidadamente, sin pensar en si el orden de las cosas es importante. En otras palabras:

"Mi ensalada de frutas es una combinación de manzanas, uvas y bananas": noimporta en qué orden pusimos las frutas, podría ser "bananas, uvas y manzanas" o "uvas, manzanas y bananas", es la misma ensalada.
 
 

"La combinación de la cerradura es 472": ahora sí importa el orden. "724" no funcionaría, ni "247". Tiene que ser exactamente 4-7-2.
Así que en matemáticas usamos un lenguaje más preciso:

Si el orden no importa, es una combinación.

Si el orden sí importaes una permutación.

 

¡Así que lo de arriba se podría llamar "cerradura de permutación"!
Con otras palabras:
Una permutación es una combinación ordenada.


Para ayudarte a recordar, piensa en "Permutación... Posición"
Permutaciones
Hay dos tipos de permutaciones:
Se permite repetir: como la cerradura de arriba, podría ser "333".
Sin repetición: por ejemplo los tres primeros en unacarrera. No puedes quedar primero y segundo a la vez.
1. Permutaciones con repetición
Son las más fáciles de calcular. Si tienes n cosas para elegir y eliges r de ellas, las permutaciones posibles son:
n × n × ... (r veces) = nr
(Porque hay n posibilidades para la primera elección, DESPUÉS hay n posibilidades para la segunda elección, y así.)
Por ejemplo en la cerradura de arriba, hay 10números para elegir (0,1,...,9) y eliges 3 de ellos:
10 × 10 × ... (3 veces) = 103 = 1000 permutaciones
Así que la fórmula es simplemente:
nr
donde n es el número de cosas que puedes elegir, y eliges r de ellas
(Se puede repetir, el orden importa)
 
2. Permutaciones sin repetición
En este caso, se reduce el número de opciones en cada paso.

Por ejemplo, ¿cómo podrías ordenar 16 bolas de...