Presentamos la implementación de un programa que permite hallar una factorización de los elementos del grupo simétrico Sn, usando el número mínimo de transposiciones simples. Dicha implementación se realizó en el sistema computacional CoCoA.
INTRODUCCIÓN
El grupo simétrico Snpuede definirse como el conjunto de todas las biyecciones sobre el conjunto { 1 ,2, …,n} con la operación usual de composición de funciones. Los elementos de Sn pueden representarse por medio de ciclos. Por ejemplo, sobre el conjunto { 1,2, … ,5} la función que envía
1 → 5
2 → 1
3 → 2
4 → 3
5 → 4
se puede representar en un ciclo como (1,5,4,3,2). En general un k-ciclo (c1, … ,ck) representa la función
(c1 → c2)
(c2 → c3)
• •
• •
• •
(ck → c1)
Los elementos de Sn se llaman permutaciones y también se pueden escribir en notación de una línea. De esta forma, si w ∈ Sn escribimos w = [w1 ,w2 , ••• ,wn] para indicar que w (i) = wi para todo i =1, … ,n. En el ejemplo anterior, la notación en una línea de la permutación (1,5,4,3,2) es [5,1,2,3,4]. Una transposición es un 2-ciclo y una transposición simple es una transposición que intercambia dos elementos consecutivos. Las transposiciones simples se escriben como Sk= (k,k +1) para k= 1, … ,n - l. Es bien conocido que el número de elementos de Sn es n! y que toda permutación se puede factorizar como un producto de ciclos disyuntos. Además, todo ciclo se puede factorizar como producto de transposiciones simples y por lo tanto, las transposiciones simples generan a Sn. La descomposición anterior en ciclos y transposiciones simples no es única. Sin embargo, el número mínimo de transposiciones simples necesarias para factorizar una permutación w ∈ Sn se llama la longitud de w·y se denota por l(w).
Ejemplo 1. Para la permutación (1,5,4,3,2) tenemos que
(1,5,4,3,2) = (4,5)(3,4)(2,3)(1,2)
= S4S3S2S1
Note que el producto se hace de derecha a izquierda, en la forma usual como se componen funciones. Como se dijo antes, la descomposición en transposiciones no es única y se tiene que
SiSi+iSi = Si+lSiSi+l
SiSj = SjSi Si | i — j | > 1.
Esta es una versión de prueba de citación de documentos de la Biblioteca Virtual Pro. Puede contener errores. Lo invitamos a consultar los manuales de citación de las respectivas fuentes.
Artículo:
Análisis de estabilidad de sistemas no lineales de orden fraccionario con retardo
Artículo:
Evaluación de la susceptibilidad a los corrimientos de tierras en Vietnam mediante el uso de máquinas de vectores de apoyo, árboles de decisión y modelos Naive Bayes.
Artículo:
Efecto de la ubicación del contacto longitudinal en la simulación de la dinámica del vehículo
Artículo:
Método de Regula Falsi generalizado para hallar ceros y extremos de funciones reales
Artículo:
Determinación de la órbita de satélites artificiales a bordo y en tiempo real mediante GPS
Folleto:
Análisis de rentabilidad económica y financiera
Artículo:
¿Por qué debemos conservar la fauna silvestre?
Artículo:
Control y vigilancia de la calidad del agua de consumo humano
Manual:
Deshidratación y desecado de frutas, hortalizas y hongos. Procedimientos hogareños y comerciales de pequeña escala