Alla Te Espero

Descomposici´n de una permutaci´n o o en transposiciones simples
Objetivos. Demostrar que toda permutaci´n su puede descomponer en transposiciones o simples. Definir el n´mero de inversiones de una permutaci´n y estudiar la relaci´n de u o o este n´mero con la descomposici´n en transposiciones simples. u o Requisitos. Producto (composici´n) de permutaciones. o 1. Definici´n (inversi´n en unapermutaci´n). Sea ϕ ∈ Sn . Una inversi´n en ϕ es o o o o un par de ´ ındices (i, j) tal que 1 ≤ i < j ≤ n y ϕ(i) > ϕ(j). 2. Ejemplo. Las inversiones en la permutaci´n o (1, 4), (2, 4), 1 2 3 4 5 2 3 5 1 4 (3, 5). son:

(3, 4),

3. Ejercicio. Escriba todas las inversiones que tienen las siguientes permutaciones: 1 2 3 4 5 3 2 5 1 4 , 1 2 3 4 4 3 2 1 , 1 2 3 4 5 6 1 5 3 4 2 6 .

4. Notaci´n (n´mero de inversiones en una permutaci´n). Dada ϕ ∈ Sn , denoteo u o mos por inv(ϕ) el n´mero de las inversiones en ϕ. Es decir, u
n−1

inv(ϕ) =
i=1

|{j > i : ϕ(j) < ϕ(i)}| .

5. Ejemplo. Sea ϕ =

1 2 3 4 5 6 4 3 6 1 5 2

. Entonces

inv(ϕ) = 3 + 2 + 3 + 0 + 1 = 9. 6. Ejercicio. Calcule inv(ϕ), donde ϕ= 1 2 ... n − 1 n n n − 1 ... 2 1 .

7. Proposici´n (n´ mero de inversiones en unatransposici´n). o u o 1. Sean p, q ∈ {1, . . . , n} tales que p < q. Entonces inv(τp,q ) = 2d − 1, donde d = q − p. 2. En particular, inv(τi,i+1 ) = 1. 3. Por consecuencia, en toda transposici´n el n´mero de inversiones es impar. o u p´gina 1 de 4 a

8. Proposici´n (cambio del n´ mero de inversiones al multiplicar por una transo u posici´n simple). Sea ϕ ∈ Sn y sea k ∈ {1, . . . , n − 1}.Entonces o inv(ϕτk,k+1 ) = inv(ϕ) − 1, si ϕ(k) > ϕ(k + 1); inv(ϕ) + 1, si ϕ(k) < ϕ(k + 1).

9. Corolario. Sea ϕ ∈ Sn y sea k ∈ {1, . . . , n − 1}. Entonces inv(ϕτk,k+1 ) ≤ inv(ϕ) + 1. 10. Lema (en toda permutaci´n distinta de la identidad existe una inversi´n o o de vecinos). Sea ϕ ∈ Sn , ϕ = e. Entonces existe un ´ ındice i ∈ {1, . . . , n − 1} tal que ϕ(i) > ϕ(i + 1). Demostraci´n. Razonamiento porcontradicci´n. Suponemos que ϕ(i) ≤ ϕ(i + 1) para o o todo i ∈ {1, . . . , n − 1}. Como ϕ es inyectiva, debe ser ϕ(i) < ϕ(i + 1) para todo i ∈ {1, . . . , n − 1}. Esto implica que si ∀i, j ∈ {1, . . . , n} (i < j) =⇒ (ϕ(i) < ϕ(j).

En particular, ϕ(1) < ϕ(j) para todo j ∈ {2, . . . , n}. Por lo tanto, ϕ(1) = 1. Ahora tenemos que ϕ(2) < ϕ(j) para todo j ∈ {3, . . . , n}. De all´ ϕ(2) ∈ {1, 2},pero ı el valor 1 ya est´ ocupado, y ϕ es inyectiva. As´ que ϕ(2) = 2. a ı Continuando de la misma manera concluimos que ϕ = e. Contradicci´n. o 11. Teorema (descomposici´n de una permutaci´n en un producto de transo o posiciones simples). Sea ϕ ∈ Sn . Entonces existen inv(ϕ) transposiciones simples ψ1 , . . . , ψinv(ϕ) tales que ϕ = ψ1 · · · ψinv(ϕ) . Demostraci´n. Inducci´n sobre inv(ϕ). o o Siinv(ϕ) = 0, entonces ϕ = e. Por definici´n el producto de una lista vac´ es la o ıa identidad, as´ que en este caso degenerado la afirmaci´n es v´lida. ı o a Supongamos que la afirmaci´n es v´lida para inv(ϕ) = m y la demostremos para o a inv(ϕ) = m + 1. Sea ϕ ∈ Sn con inv(ϕ) = m + 1. Como inv(ϕ) > 0, ϕ = e. Por el lema, existe un ´ ındice k ∈ {1, . . . , n − 1} tal que ϕ(k) > ϕ(k + 1). Por laproposici´n sobre el cambio del n´mero de inversiones al multiplicar por una o u transposici´n simple, o inv(ϕτk,k+1 ) = inv(ϕ) − 1 = m. Aplicamos la hip´tesis de inducci´n a la permutaci´n ϕτk,k+1 : existen transposiciones o o o simples ψ1 , . . . , ψm tales que ϕτk,k+1 = ψ1 · · · ψm . Multiplicando esta igualdad por τk,k+1 por la derecha y usando el hecho que toda transposici´n es inversa a si misma,obtenemos que o ϕ = ψ1 · · · ψm τk,k+1 , donde todos los factores en el lado derecho son transposiciones simples. p´gina 2 de 4 a

12. Nota. En general, la descomposici´n de una permutaci´n ϕ en transposiciones simples o o no es unica, a´n bajo la condici´n que el n´mero de los factores es inv(ϕ). Por ejemplo, ´ u o u 1 2 3 3 2 1 = τ1,2 τ2,3 τ1,2 , 1 2 3 3 2 1 = τ2,3 τ1,2 τ2,3 .

13. Nota. Si...