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 la ecuación de Reynolds para la lubricación en caso de viscosidad dependiente de la presión
Artículo:
Análisis y optimización de la precisión de medición dinámica del giroscopio de fibra óptica
Artículo:
Detección comprimida y descomposición matricial de bajo rango en la fusión de imágenes multifuente
Artículo:
Un enfoque híbrido para la dinámica aleatoria de sistemas inciertos bajo carga estocástica
Artículo:
Modelado eficaz de características volumétricas y correspondencia gruesa mediante 3DSIFT y correspondencia espectral mejoradas
Libro:
Metodología del marco lógico para la planificación, el seguimiento y la evaluación de proyectos y programas
Presentación:
Estudio de movimientos y tiempos
Artículo:
Estudio sobre la evaluación de la sostenibilidad de los productos innovadores
Tesis:
Materiales y prácticas de construcción sostenible