PERMUTACIONES

3.2. Permutaciones

3.2.

153

Permutaciones

pr
eli
m
in
ar

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

(permutaci´n como lista)
o

o bien utilizar la siguiente notaci´n:
o

(permutaci´n como aplicaci´n biyectiva)
o
o

Ve
rs
i´n
o

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

que nos permite reconocer r´pidamente la imagen de cada elemento de {1, . . . , n} por la
a
permutaci´n. Es decir, identificamos la lista (2, 7, 5, 1, . . . , 6) con la aplicaci´n biyectiva
o
o
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 (els´
ımbolo j nunca va al j, para cada j = 1, . . . , n). En t´rminos de
e
listas, son las n-listas tales que, para cada j = 1, . . . , n, el s´
ımbolo j no ocupa la posici´n
o
j de la lista. Pronto calcularemos cu´ntos de estos desbarajustes hay. Otras permutaciones
a
que aparecer´n m´s adelante son las trasposiciones, cuyo efecto es el de intercambiar las
a
a
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 aplicao
o
ci´n biyectiva del conjunto en s´ mismo. Sean, por ejemplo, las dos siguientes permutaciones
o
ı
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´ndel conjunto {1, 2, 3, 4, 5} en s´ mismo que lleva, por
o
o
ı
ejemplo, el elemento 1 en el 2: g(1) = 2. Pero tambi´n f lo es, y observemos que lleva el 2
e
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´n preliminar 1 de noviembre de 2003)
o

154

´
Cap´
ıtulo 3. Las estructuras basicas de laCombinatoria

Composici´n de permutaciones
o

pr
eli
m
in
ar

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

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

es decir, la acci´nsucesiva de g primero y f despu´s.
o
e

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

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

como f es una aplicaci´n biyectiva esto supondr´ que g(a) = g(b). Y el que g sea tambi´n
o
ıa
e
una aplicaci´n biyectiva nos lleva a que a y b deben ser iguales.
o
Hemos comprobado que, dadas dos permutaciones...