Permutaciones

3.2. Permutaciones

3.2.

153

Permutaciones

pr
eli
m
in
ar

Aunque ya las hemos definido en la subsecci´on 2.2.1 (como un tipo particular de listas),
las permutaciones son un objeto combinatorio lo suficientemente rico como para merecer
atenci´on especial.
Una permutaci´
on del conjunto {1, . . . , n} es una lista de longitud n sin repetici´on formada por sus elementos; el conjunto de todasellas lo llamaremos
P erm({1, . . . , n}) = { n-listas sin repetici´on formadas con los s´ımbolos {1, . . . , n}} .
Sabemos, por supuesto, que hay n! de ellas. En los t´erminos en que las estamos definiendo,
cada permutaci´on es una (re)ordenaci´
on de los elementos de {1, . . . , n}.
Ya vimos, en el ejemplo 2.2.5, que podemos entender tambi´en una permutaci´on de un
conjunto finito X como unaaplicaci´on biyectiva de X en X . Como siempre, para simplificar
la notaci´on, supondremos que X = {1, . . . , n}.
Para exhibir una permutaci´on podemos escribir la lista correspondiente,
(2, 7, 5, 1, . . . , 6)

(permutaci´on como lista)

o bien utilizar la siguiente notaci´on:

(permutaci´on como aplicaci´on biyectiva)

Ve
rs
i´on

1 2 3 4 ... n
2 7 5 1 ... 6

que nos permite reconocer r´apidamente laimagen de cada elemento de {1, . . . , n} por la
permutaci´on. Es decir, identificamos la lista (2, 7, 5, 1, . . . , 6) con la aplicaci´on 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´erminos de
listas, sonlas n-listas tales que, para cada j = 1, . . . , n, el s´ımbolo j no ocupa la posici´
on
j de la lista. Pronto calcularemos cu´
antos de estos desbarajustes hay. Otras permutaciones
que aparecer´an m´as 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´on depermutaci´on como aplicaci´on biyectiva del conjunto en s´ı 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´on g es una aplicaci´on del conjunto {1, 2, 3, 4, 5} en s´ı mismo que lleva, por
ejemplo, el elemento 1 en el 2: g(1) = 2. Pero tambi´en f loes, 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.
(versi´
on preliminar 1 de noviembre de 2003)

154

´sicas de la Combinatoria
Cap´ıtulo 3. Las estructuras ba

Composici´
on de permutaciones

pr
eli
m
in
ar

Perfilemos adecuadamente esta idea de acci´
on sucesiva de dos permutaciones. Sean fy g
dos permutaciones del conjunto {1, . . . , n}. La composici´
on de f con g, que escribiremos
como f ◦ g (obs´ervese el orden en que se escriben) se define como
(f ◦ g)(x) = f (g(x)),

para cada x ∈ {1, . . . , n},

es decir, la acci´on sucesiva de g primero y f despu´es.

La aplicaci´on g sabe actuar sobre los elementos {1, . . . , n}, y devuelve los mismos elementos, quiz´as reordenados.As´ı que la acci´on posterior de f est´a igualmente bien definida. Pero
adem´as, y esto es lo importante, estas dos acciones sucesivas producen, en total, una nueva
aplicaci´on biyectiva del conjunto en s´ı mismo (esto es, una permutaci´on). Basta comprobar
que (f ◦ g) es una aplicaci´on inyectiva: si a y b son tales que
(f ◦ g)(a) = (f ◦ g)(b) ,

es decir, si f (g(a)) = f (g(b)) ,

como f es unaaplicaci´on biyectiva esto supondr´ıa que g(a) = g(b). Y el que g sea tambi´en
una aplicaci´on biyectiva nos lleva a que a y b deben ser iguales.
Hemos comprobado que, dadas dos permutaciones cualesquiera f y g, la acci´on sucesiva
de g y f , lo que llamamos su composici´on f ◦ g (insistimos en el orden en que se escriben) es
tambi´en una permutaci´on. Y es que

Ve
rs
i´on

el conjunto de las...