Biblioteca122.739 documentos en línea

Artículo

Factorización de PermutacionesFactorization of Permutations

Resumen

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 (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  ∈ 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.

  • Tipo de documento:Artículo
  • Formato:pdf
  • Idioma:Español
  • Tamaño:230 Kb

Cómo citar el documento

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.

Este contenido no est� disponible para su tipo de suscripci�n

Información del documento

  • Titulo:Factorización de Permutaciones
  • Autor:Novoa, Fernando
  • Tipo:Artículo
  • Año:2003
  • Idioma:Español
  • Editor:Pontificia Universidad Javeriana
  • Materias:Matemáticas
  • Descarga:2