Nombre Alumna: Laura Betzabe Reyes Ibarra Matricula : 10931
Materia : Matematicas
Tetra: 1ero.
Ensayo # 3 Matematicas - Permutacion
Permutación
En matemáticas,
llamamos permutación de un conjunto a cada una de las posibles ordenaciones de
todos los elementos de dicho conjunto.Por ejemplo, en el conjunto {1,2,3}, cada
ordenación posible de sus elementos, sin repetirlos, es una permutación. Existe
un total de 6 permutaciones para estos elementos: "1,2,3",
"1,3,2", "2,1,3", "2,3,1", "3,1,2" y
"3,2,1".
Definición
formal-.La definición intuitiva de p
Ejemplo de permutación considerada como función
biyectiva.
Para ilustrar la definición,
retomemos el ejemplo descrito en la introducción. En el ejemplo, X={1, 2, 3}.
Entonces, cada correspondencia uno a
uno entre el conjunto {1, 2, 3} a sí mismo equivale a una forma de ordenar los
elementos.
Por ejemplo, la asignación biyectiva
dada por
- 1 → 1
- 2 → 2
- 3 → 3
puede hacerse corresponder al
ordenamiento "1, 2, 3".
Por otro lado, la asignación
biyectiva dada por
- 1 → 3
- 2 → 2
- 3 → 1
- puede
hacerse corresponder al ordenamiento "3, 2, 1".
En la definición de permutación, no
se establece condición alguna sobre X, el cual puede incluso ser infinito. Sin
embargo, es común considerar únicamente el caso en que X es un conjunto finito
al estudiar permutaciones.
En
combinatoria-.La combinatoria
trata del número de diferentes maneras que existen de considerar conjuntos
formados a partir de elementos de un conjunto dado, respetando ciertas reglas,
como el tamaño, el orden, la repetición, la partición. Así un problema
combinatorio consiste usualmente en establecer una regla sobre cómo deben ser
las agrupaciones y
determinar cuántas existen que cumplan dicha regla.Básicamente, dos asuntos:
permutaciones y combinaciones (ambas sin repetición o con ella).Un tipo
importante de esas agrupaciones son las llamadas permutaciones. Dada una n-tupla
ordenada de elementos de un conjunto, el número de permutaciones es el número
de n-tuplas ordenadas .
Fórmula
del número de permutaciones
Demostración: Dado que hay formas
de escoger el primer elemento y, una vez escogido éste, sólo tenemos formas
de escoger el segundo elemento, y así sucesivamente, vemos que cuando llegamos
al elemento k-ésimo sólo tenemos posibles
elementos para escoger, lo que nos lleva a que tenemos formas
de ordenar el conjunto, justamente lo que enunciamos anteriormente. .
Ejemplo: sea el conjunto A={1,2,3}
en este caso hay 6 permutaciones, en forma compacta: 123, 132, 213, 231, 312,
321. En álgebra, para estudiar los grupos simétricos se presentan entre
paréntesis y en dos filas, en la primera siempre aparece 1 2 3.
Una variante de lo mismo, si se va a
formar un comité que involucra presidente, tesorero y secretario, habiendo tres
candidatos a, b, c ; cuando se elige por sorteo los cargos sucesivamente,
hay seis posibilidades u ordenaciones: abc, acb, bca, bac, cab, cba.
En
teoría de grupos
Notaciones
Representación gráfica de la permutación σ que
revela su estructura compuesta por 2 ciclos de longitud 4.
La primera forma de escribir una
permutación σ, aunque no es la más compacta, consiste en
escribirla en forma de matriz de dos filas, situando en la primera fila los
elementos del dominio 1, 2, 3,...,n, y en la segunda las imágenes
correspondientes a los elementos reordenados σ(1), σ(2), σ(3),...,σ(n).
Por ejemplo, dado el conjunto ordenado podemos expresar una permutación sobre éste mediante una matriz de correspondencias:
Por ejemplo, dado el conjunto ordenado podemos expresar una permutación sobre éste mediante una matriz de correspondencias:
Claramente es biyectiva, ya que
podemos encontrar una aplicación inversa de
forma que su composición genera la aplicación identidad. Para ello, en primer
lugar intercambiamos las filas y finalmente reordenamos las columnas de modo
que los elementos del dominio queden ordenados de forma natural:
Notación
de ciclos-.Existe otra notación más compacta, llamada notación de ciclos. Un ciclo de
longitud s es una permutación que intercambia cíclicamente s elementos y fija
los restantes.Esta notación revela mejor la estructura interna de la
permutación. Para ello:
- Empezamos
con cualquier elemento. Lo escribimos, a su derecha escribimos su imagen,
a la derecha de esta, la imagen de su imagen, y seguimos así hasta que se
complete un ciclo.
- Luego
cogemos cualquier elemento no contenido en el primer ciclo, volvemos a
escribir su imagen a su derecha, y continuamos hasta completar el segundo
ciclo.
- El
proceso continúa hasta que la permutación entera ha quedado descrita como
producto de ciclos disjuntos.
Siguiendo con el mismo ejemplo de
antes, en notación de ciclos, quedaría
expresada como composición de dos ciclos:
= (1
3 5 6 )(2 4 7 8)
Descomposición
de una permutación en ciclos disjuntos-.La descomposición realizada por el
procedimiento anterior no es única en principio, pues podrían haberse obtenido
cualquiera de estos resultados equivalentes:
= (1
3 5 6)(2 4 7 8)=(2 4 7 8) (1 3 5 6)= (8 2 4 7)(6 1 3 5)
La descomposición canónica de una permutación
como producto de ciclos se obtiene colocando en primer lugar de cada ciclo el
número más pequeño del mismo. Posteriormente se procede a la colocación de los
ciclos, colocando primero el ciclo cuyo primer elemento sea menor.
Frecuentemente, suelen omitirse los ciclos de longitud 1. Así la permutación (1
3)(2)(4 5) se escribe simplemente como (1 3)(4 5).
Descomposición
de una permutación en trasposiciones-.Una trasposición es una permutación que
intercambia dos elementos y fija los restantes. Dicho de otro modo, es un ciclo de
longitud 2. Una propiedad interesante es que cualquier permutación se puede
construir como una composición de transposiciones, aunque no de manera única.
Dadas dos descomposiciones en transposiciones de una permutación se cumple que
ambas usaran un número par o ambas usarán un número impar, eso permite definir
de manera unívoca la signatura de una permutación.
Las trasposiciones permiten
descomponer una permutación cualquiera de una forma diferente a la
descomposición en ciclos. En particular, las trasposiciones que aparezcan no
tendrán que ser disjuntas: Por ejemplo, el ciclo (1 2 3 4) = (1 2) (2 3) (3 4).
Aquí el orden de aplicación es importante: en primer lugar (3 4) deja el 4 en
su sitio definitivo y el 3 descolocado. Después (2 3) deja en su sitio
definitivo el 3 y el 2 descolocado, que quedará recolocado definitivamente por
(1 2).
Para ver que cualquier permutación
descompone como producto de trasposiciones bastará ver que todo ciclo lo hace.
De hecho, la descomposición del ciclo de nuestro ejemplo se generaliza a la
fórmula:
No habrá unicidad en la
descomposición, ni siquiera en el número de trasposiciones necesarias. Pero se
demuestra que si admite
dos descomposiciones distintas con n y con m trasposiciones, entonces n y m
tendrán la misma paridad (serán simultáneamente pares o impares). Dada una
permutación cualquiera, se define el siguiente morfismo de grupos:
Donde es el
grupo
simétrico de n elementos y m es un número entero, tal
que exiten transposiciones tales
que:
Permutación
par y permutación impar
Llamaremos permutación par (resp. impar)
a la que se escribe como composición de un número par (resp. impar) de
trasposiciones.
Como ejemplo, de las 6=3!
permutaciones del conjunto {1, 2, 3}, escritas en notación de ciclos:
- (1
2), (2 3) y (1 3) son, de forma trivial, impares.
- (1
2 3) y (1 3 2) son pares, como es fácil de comprobar al aplicar la fórmula
anterior de descomposición de un ciclo en trasposiciones.
- e
(la identidad) también es par.
En general, se demuestra que la
mitad de las n! permutaciones de un conjunto de n elementos son pares y la otra
mitad impares.
Estructura
de grupo
Dado un número natural ,
consideramos el conjunto .
Definimos el grupo de permutaciones de elementos,
que denotaremos por , o
lo que es lo mismo, el conjunto de aplicaciones biyectivas de a .
Las permutaciones pares forman un subgrupo normal de
índice 2 del grupo Sn, al que llamaremos grupo alternado, y
notaremos por .
Dato
histórico
El estudio de las permutaciones de
las raíces de ecuaciones algebraicas le permitió a Galois, elaborar los inicios
de la teoría de grupos y usar este vocablo, por primera vez, en Matemática. Y
empezó por los grupos no abelianos.