PERMUTACIONES

1. INTRODUCCION
Antiguamente, se definía una permutación así:
Sea un número n de objetos, (n>1), alineados en
una mesa con el fin de poder atribuir a cada cual
su rango: el objeto más a la izquierda es el
primero, el que sigue el segundo y así
sucesivamente. Ahora se mezclan los objetos y se
les vuelven a colocar en una fila, en cualquier
orden. Se dice que se han permutado los objetos,
o, lo que viene a ser lo mismo, los números de 1 a
n.
Si el objeto que se encuentra actualmente a la
izquierda era antes el quinto de la fila, si el que se
encuentra a su derecha era el séptimo ... y el que
está al final era el segundo ... entonces la actual
permutación está caracterizada por los serie de
números ( 5, 7, ..., 2).
La definición moderna de una permutación ya no
hace referencia al mundo real, y prescinde de los
objetos.
Para conocer la permutación, sólo se necesita
conocer la serie de números (5, 7, ..., 2) en el
ejemplo. Se dice que 5 es la imagen de 1 por la
permutación, 7 es la imagen de 2, ...y 2 es la
imagen de n. De este punto de vista, una
permutación es una aplicación biyectiva de
{1,...,n} hacia {1,...,n}. Es biyectiva porque a cada
posición anterior de un objeto corresponde una
única posición actual.
Las Técnicas de conteo son importantes en matemáticas y las
ciencias de la computación, particularmente en el análisis de
algoritmos.
Una permutación del conjunto {1, . . . , n} es una lista de
longitud n sin repetición formada por sus elementos; el conjunto
de todas ellas lo llamaremos
Perm({1, . . . , n}) = { n-listas sin repetición formadas con los
símbolos {1, . . . , n}} .
Sabemos, por supuesto, que hay n! de ellas. En los términos en
que las estamos definiendo, cada permutación es una
(re)ordenación de los elementos de
{1, . . . , n}.
Ya vimos, en el ejemplo 2.2.5, que podemos entender también
una permutación de un conjunto finito X como una aplicación
biyectiva de X en X. Como siempre, para simplificar la notación,
supondremos que X = {1, . . . , n}.
Para exhibir una permutación podemos escribir la lista
correspondiente,
(2, 7, 5, 1, . . . , 6) (permutación como lista) o bien utilizar la
siguiente notación:
)
1 2 3 4 . . . n
2 7 5 1 . . . 6


(permutación como aplicación biyectiva) que nos permite
reconocer rápidamente la imagen de cada elemento de {1, . . . ,
n} por la permutación. Es decir, identificamos la lista (2, 7, 5, 1,
. . . , 6) con la aplicación biyectiva que lleva el 1 en el 2, el 2 en
el 7, el 3 en el 5, etc.
Unas permutaciones especiales son los desbarajustes, las
aplicaciones biyectivas que no fijan elemento alguno (el símbolo
j nunca va al j, para cada j = 1, . . . , n). En términos de listas,
son las n-listas tales que, para cada j = 1, . . . , n, el símbolo j no
ocupa la posición j de la lista. Pronto calcularemos cuantos de
estos desbarajustes hay. Otras permutaciones que aparecerán mas
adelante son las trasposiciones, cuyo efecto es el de
intercambiar las posiciones de dos elementos (y fijar los n − 2
restantes).
Para lo que sigue, es conveniente tener presente la definición de
permutación como aplicación biyectiva del conjunto en si mismo.
Sean, por ejemplo, las dos siguientes permutaciones del conjunto
X = {1, 2, 3, 4, 5}:
f : (1, 3, 2, 5, 4) =
)
1 2 3 4 5
1 3 2 5 4
g : (2, 1, 3, 5, 4) =
)
1 2 3 4 5
2 1 3 5 4
.
La permutación g es una aplicación del conjunto {1, 2, 3, 4, 5} en
si mismo que lleva, por ejemplo, el elemento 1 en el 2: g(1) = 2.
Pero también f lo es, y observemos que lleva el 2 en el 3, f(2) =
3. Así que si primero hacemos actuar g y luego f, entonces, por
ejemplo, el elemento 1 acaba yendo al 3.
2. PERMUTACIONES SIN REPETICIÓN
Las permutaciones sin repetición de n elementos se definen
como las distintas formas de ordenar todos esos elementos
distintos, por lo que la única diferencia entre ellas es el orden de
colocación de sus elementos.
El número de estas permutaciones
será:
Ponemos como ejemplo las siguientes letras: aei
2.1.1 El número de permutaciones sin
repetición de esos 3 elementos es 6 y esas
permutaciones son:
aei
aie
eai
eia
iae
iea
3. PERMUTACIONES CON REPETICIÓN
Llamamos a las permutaciones con repetición de n elementos
tomados de a en a, de b en b, de c en c, etc, cuando en los n
elementos existen elementos repetidos (un elemento aparece a
veces, otro b veces, otro c veces, etc) verificándose que
a+b+c+...=n.
El número de estas permutaciones será:
Ahora ponemos como ejemplo las siguientes letras: aea
3.1.1 El número de permutaciones con
repetición de esos 3 elementos tomados de
2 en 2 y de 1 en 1 es 3 y esas permutaciones
son:
aea
aae
eaa


4. REFERENCIAS
[1] Estructuras de las Matematicas Discretas para la
Computacion. Kolman, Busby, Ross.. Pag. 75
[2] http://club.telepolis.com/ildearanda/combina/per_marco.htm
[3] http://www.uam.es/personal_pdi/ciencias/gallardo/capitulo3
b_2004_2005.pdf