Download ESTALMAT-Andalucía Actividades 07/08

Actividades 07/08
ESTALMAT-Andalucía
Sesión: 5 Fecha: no presencial
Título: La magia de las permutaciones.
Veteranos
_______________________________________________________________________________________
1.- Las permutaciones en la Corte del Rey Arturo.En la Corte del rey Arturo existía un Consejo formado por 12 nobles llamados “Los
Caballeros de la Mesa Redonda”. Estos nobles se sentaban alrededor de una gran
mesa circular donde tenían lugar los debates y la toma de decisiones sobre los
asuntos del Reino.
Pues bien, cuando nos gustan las Matemáticas y nos encontramos situaciones como
ésta, nos surgen siempre muchas preguntas como, por ejemplo, ¿de cuántas maneras
diferentes pueden sentarse los caballeros alrededor de la mesa?
Y siempre es bueno ver primero un caso más sencillo: supongamos que sólo hay 6
caballeros. Si estuvieran sentados en las butacas de una fila de teatro, estaríamos
hablando de las permutaciones de 6 números (Caballeros), es decir, S6, que son
6!=720 maneras distintas de sentarse.
EJERCICIO 1.1.-
Pero están sentados en una mesa circular y si le ponemos un número
a cada uno podrían estar, por ejemplo, así:
6
2
1
5
4
3
Esta misma posición la podemos escribir de varias maneras, según por dónde
empecemos:
6 1 4 3 5 2 = 1 4 3 5 2 6 = … ¿De cuántas maneras?
Si consideramos todas las posibles posiciones y todas las maneras de escribirlas ¿qué
obtenemos?
¿Podemos deducir de aquí el número de posiciones posibles?
¿Y en el caso de los 12 Caballeros de la Mesa redonda?
¿Y si hay n Caballeros?
________________________________________________________________________________________________________
Página 1 de 7
ESTALMAT-Andalucía
Actividades 07/08
Sesión: 5 Fecha: no presencial
Título: La magia de las permutaciones.
Veteranos
_______________________________________________________________________________________
EJERCICIO 1.2.-
En cada reunión el Rey Arturo dejaba
que sus 12 Caballeros se sentaran
aleatoriamente sin saber dónde se
sentaría él cada vez.
El Asiento Peligroso estaba reservado a
los caballeros de corazón puro.
En cierta ocasión el Rey ofreció a Sir
Galaad que ocupara “el asiento
peligroso”.
Una vez ocupado el asiento por Sir
Galaad, ¿de cuántas maneras posibles
pueden sentarse alrededor de la mesa
el resto de los Caballeros?
EJERCICIO 1.2.-
Si se colocan los 12 Caballeros aleatoriamente, ¿cuál es la probabilidad de que el Rey
Arturo y su amigo Sir Galaad se sienten juntos?
EJERCICIO 1.3.-
A veces, los 12 Caballeros se numeraban siguiendo los criterios del Mago Merlín. El
Rey Arturo era designado con el número 1, Sir Lancelot del Lago con el número 2, Sir
Perceval de Gales con el número 3 y así todos los demás.
¿Cuál es la probabilidad de que al sentarse queden alternativamente situados los
números pares y los impares?
________________________________________________________________________________________________________
Página 2 de 7
Actividades 07/08
ESTALMAT-Andalucía
Sesión: 5 Fecha: no presencial
Título: La magia de las permutaciones.
Veteranos
_______________________________________________________________________________________
2.- Algunas permutaciones interesantes.- En el conjunto S6 hay permutaciones
que merecen especial atención:
a) Hay una que deja todos los números en el mismo sitio:
1 2 3 4 5 6 


1 2 3 4 5 6 
Esta permutación se llama la identidad y se representa por (1) o por id.
Verifica la propiedad de que f id = id f = f, para cualquier f de S6.
b) Dada una permutación cualquiera f, siempre hay otra g, que deshace lo que
hace f, que es lo mismo que decir que cuando actúa una detrás de la otra, todo
se queda como estaba:
fg=gf=(1)
1 2 3 4 5 6
 , se tiene:
Por ejemplo, si f = 
4
3
1
6
5
2


1 → 4 → 1
2 → 3 → 2
3 → 1 → 3
;
4 → 6 → 4
5 → 5 → 5
6 → 2 → 6
 4 3 1 6 5 2 1 2 3 4 5 6
 =
 . Comprobar que fg=gf=(1).
2 3 4 5 6   3 6 2 1 5 4 
de donde, g= 
1
Se podría hablar de una inversa por la derecha, fg=(1), y otra por la izquierda, g’f=(1),
porque el producto no es conmutativo, pero en este caso coinciden, g=g’. ¿Por qué coinciden?
Dada una permutación f, la permutación que multiplicada por f (en los dos sentidos)
da la identidad se llama inversa de f y se representa por f −1 .
Una manera de obtener la inversa de una permutación es subir la fila de abajo a
arriba y la de arriba abajo ¡y ya está! Ahora, si se quiere poner ‘bonita’, se cambian
las columnas para que la fila de arriba quede ordenada.
Si la permutación es un ciclo, la cosa es aún más fácil: basta invertir el orden de los
números dentro del ciclo. Si la permutación contiene ciclos disjuntos, la inversa se
obtiene invirtiendo cada uno de los ciclos.
3.- Ejercicio.- Calcular las inversas de las permutaciones f, g, h del ejercicio 13.
(Usar el dorso de la hoja)
________________________________________________________________________________________________________
Página 3 de 7
Actividades 07/08
ESTALMAT-Andalucía
Sesión: 5 Fecha: no presencial
Título: La magia de las permutaciones.
Veteranos
_______________________________________________________________________________________
4.- El grupo de las permutaciones.- En el conjunto S6, y, en general, en Sn, hemos
visto cómo se pueden multiplicar (componer) las permutaciones dando siempre como
resultado una nueva permutación.
Si resumimos las propiedades que hemos visto en las actividades anteriores,
tenemos:
1. Existe una permutación que se llama identidad, que verifica: id f = f id = f. Esta
permutación es el elemento unidad de Sn. Es lo análogo al 0 en la adición de
números o al 1 en la multiplicación de números.
, tal que ff −1 = f −1 f = id. Es como el a
1
y el –a en la adición de números o el a y el
en la multiplicación.
a
2. Toda permutación f tiene una inversa f
−1
3. El producto de permutaciones no es conmutativo. En esto se diferencia de la
adición y multiplicación de números, que sí son conmutativas.
Enunciamos la siguiente propiedad que implícitamente hemos utilizado antes sin
mencionarla:
4.
El producto de permutaciones tiene la propiedad asociativa, que es también una
propiedad de la adición y multiplicación de números:
(a+b)+c=a+(b+c) y (a—b)—c=a—(b—c),
f (g h)=(f g) h
Estas propiedades que tiene el producto de permutaciones en Sn:
-
Propiedad asociativa
Elemento neutro
Cada elemento tiene un inverso
se resumen en Álgebra diciendo que
Sn es un grupo, en este caso, no conmutativo.
5.- Ejercicio.- La propiedad 4 del apartado anterior se comprueba fácilmente con un
sencillo razonamiento. ¿Podéis intentarlo?
________________________________________________________________________________________________________
Página 4 de 7
ESTALMAT-Andalucía
Actividades 07/08
Sesión: 5 Fecha: no presencial
Título: La magia de las permutaciones.
Veteranos
_______________________________________________________________________________________
6.- Trasposiciones.- Se llama trasposición a un ciclo de longitud 2, esto es, con dos
elementos. Es decir, una trasposición es una permutación que cambia dos elementos
entre sí y al resto los deja invariantes. La permutación g del ejercicio 11,
1 2 3 4
 ,
g = 
4
2
3
1


es un ejemplo de trasposición. En cierto modo, las trasposiciones son las
permutaciones más elementales posibles.
TEOREMA.- Toda permutación se puede escribir como producto de trasposiciones,
pero no de manera única. Además, en general, las trasposiciones no serían disjuntas.
Veamos un ejemplo:
La permutación h del ejercicio 13 resultó ser:
1 2 3 4 5 6
 = (1 4 5)(2 6 3) = (1 4)(1 5)(2 6)(2 3) , pero también puede ser:
h= 
ciclos disjuntos
trasposiciones
 4 6 2 5 1 3
h=(4 5)(4 1)(6 3)(6 2) ó h=(5 1)(5 4)(3 2)(3 6) o incluso h=(2 6)(2 3)(2 1)(1 2)(1 4)(1 5)
Para escribir una permutación como producto de trasposiciones se parte de los ciclos
disjuntos que hay en la permutación. Cada ciclo se descompone en producto de
trasposiciones como hemos visto en el ejemplo.
¿Podéis pensar una demostración del Teorema a partir de la descomposición de toda
permutación en producto de ciclos disjuntos?
EJERCICIO.-
Como ejemplo de que esto se puede hacer de muchas maneras,
comprobar que los siguientes productos de trasposiciones dan la misma permutación:
(1 3)(1 5)(1 2)(1 4)(1 5)(1 4)(4 6)
(1 3)(1 6)(1 4)(1 5)(1 2)
(2 3)(1 2)(2 3)(1 5)(1 2)(4 5)(1 4)(1 6)(1 4)
NOTA.- El número de trasposiciones en que se descompone una permutación puede
ser distinto, según cómo se haga, pero, curiosamente, hay una cosa que no cambia en
ese número: el ser par o impar. Eso se llama la paridad de la permutación.
________________________________________________________________________________________________________
Página 5 de 7
ESTALMAT-Andalucía
Actividades 07/08
Sesión: 5 Fecha: no presencial
Título: La magia de las permutaciones.
Veteranos
_______________________________________________________________________________________
7.- Las trasposiciones generan el grupo de las permutaciones.En “La magia de las permutaciones” se ha visto que toda permutación es producto
de trasposiciones. Este resultado tiene un formato habitual en otros ámbitos
científicos: “Todo objeto complejo se compone de objetos elementales”. Pensemos en
el código genético escrito en las moléculas de ADN en un lenguaje que sólo tiene 4
letras A C G T (iniciales de los nombres de las cuatro bases nitrogenadas). Cuantos
menos objetos elementales necesitemos para componer uno complejo, más elegante
es la construcción.
n(n − 1)
En nuestro caso, ¿cuántas trasposiciones tiene Sn? (Solución:
). Esto quiere
2
decir que, por ejemplo, en S4 hay 6 trasposiciones,
{(1 2) , (1 3) , (1 4) , (2 3) , (2 4) , (3 4)},
y toda permutación se puede obtener componiendo elementos de ese conjunto.
Pero ¿hacen falta estas 6 trasposiciones para “generar” S4, o lo podemos hacer con
menos?
Nos proponemos en este apartado ver cómo se puede generar Sn con menos de
n(n − 1)
trasposiciones.
2
EJERCICIO 7.1.-
Consideramos Sn y suponemos n ≥ 3 .
a) Calcular el producto: (1 3)(1 5)(1 3)
b) Calcular el producto: (1 i)(1 j)(1 i), siendo i, j distintos y 2 ≤ i ≤ n ; 2 ≤ j ≤ n .
________________________________________________________________________________________________________
Página 6 de 7
ESTALMAT-Andalucía
Actividades 07/08
Sesión: 5 Fecha: no presencial
Título: La magia de las permutaciones.
Veteranos
_______________________________________________________________________________________
De lo anterior se deduce que toda trasposición (i,j) es producto de trasposiciones de
la forma (1, _).
c) Deducir que toda permutación se puede escribir como producto de trasposiciones
del conjunto:
{(1 2) , (1 3) , ... , (1 n)}.
Este conjunto tiene n-1 elementos. En el caso de S4 sólo se necesitan 3
trasposiciones, {(1 2) , (1 3) , (1 4)}, para generar todas las permutaciones.
d) Practicar lo anterior en el caso concreto de la permutación (125)(346) de S6.
EJERCICIO 7.2.-
a) Calcular los siguientes productos:
(5 6) (1 5) (5 6) , (4 5) (1 4) (4 5) , (3 4) (1 3) (3 4) , (2 3) (1 2) (2 3)
b) Calcular el producto: (i-1 i) (1 i-1) (i-1 i) para i entre 3 y n.
c) Deducir de lo anterior que toda permutación es producto de las n-1 trasposiciones
del conjunto:
{(1 2) , (2 3) , ... , (n-1 n)}.
d) Practicar lo anterior en el caso concreto de la permutación (125)(346) de S6.
________________________________________________________________________________________________________
Página 7 de 7