6 votos

¿Hay un truco rápido para escribir permutaciones de$S_n$ como productos de transposiciones?

Si quiero escribir$(123)$ como producto de las transposiciones, obtengo$(13)(12)$. Para$(132)$ obtengo$(12)(13)$. Para$(1234)$, obtengo$(14)(13)(12)$. Parece que puedo escribir$(abcd)$ como$(ad)(ac)(ab)$.

¿Es este un truco general que también funciona para$n$% más grande?

Edit: como usernull sugirió, ¿sería esto una prueba correcta por inducción?

Suponer que $(a_1 ... a_n)=(a_1 a_n)...(a_1 a_2)$. Entonces \begin{align} (a_1 ... a_n a_{n+1})=&(a_1 a_{n+1})(a_1 ... a_n) \\ \overset{\text{IH}}{=}& (a_1 a_{n+1})(a_1 a_n)...(a_1 a_2) \end {align}

8voto

Drew Jolesch Puntos 11

$(1)$ Sí, como mixedmath señala, uno "probado y verdadero" método para la escritura de un producto de distinto ciclo como un producto de transposiciones es la estrategia que emplean:

Para un ciclo:
$$(a_1\,a_2\,a_3\,\cdots\,a_{n-1}\,a_n) = (a_1\,a_n)(a_1\,a_{n-1})\cdots\,(a_1\,a_3)(a_1\,a_2)$$

Para más ciclos, digamos por ejemplo, una de tres ciclos, que acaba de concatenar cada ciclo del producto de transposiciones: $$(abcd)(efgh)(ijkl) = \underbrace{(ad)(ac)(ab)}_{\large (abcd)}\,\underbrace{(eh)(eg)(ef)}_{\large (efgh)}\,\underbrace{(il)(ik)(ij)}_{\large(ijkl)}$$


Pero otro tonto método a prueba a los ciclos de escritura como de los productos de transposiciones es como sigue:

$$(a_1\,a_2\,a_3\,\cdots\,a_{n-1}\,a_n) = (a_1\,a_2)(a_2\,a_3)\,(a_3\,a_4)\cdots(a_{n-2}\,a_{n-1})(a_{n-1}\,a_n)$$

Y de nuevo, para ciclos más, digamos por ejemplo, una de tres ciclos, que acaba de concatenar cada ciclo del producto de transposiciones: $$(abcd)(efgh)(ijkl) = \underbrace{(ab)(bc)(cd)}_{\large (abcd)}\,\underbrace{(ef)(fg)(gh)}_{\large (efgh)}\,\underbrace{(ij)(jk)(kl)}_{\large(ijkl)}$$


  • Lo que esto demuestra es que hay no hay una única manera de escribir una permutación como producto de transposiciones. Lo que es cierto es que no importa el método que utilice, si se trata de un método correcto, devolverán los originales de ciclo(s), cuando los relatos se "multiplican".

  • Y para cada permutación, cualquiera que sea la forma elegida para expresarlo como el producto de transposiciones, el número de transposiciones en el producto SIEMPRE va a ser , incluso, o sea SIEMPRE impar, para cualquier permutación.

4voto

Gudmundur Orn Puntos 853

Sí, siempre funciona.

$(abcdefg) = (ag)(af)(ae)(ad)(ac)(ab)$, y así sucesivamente, siempre funcionará. Una forma de 'verlo' es justificar que cada letra vaya a la siguiente letra. Digamos que queremos ver qué pasa con$d$. Luego, en nuestro producto de transposiciones,$d$ se enviará a$a$, y en la siguiente transposición,$a$ se enviará a$e$. Cada letra, además de$a$, aparece exactamente una vez, por lo que vemos que$d \to e$. Esto sucede para el símbolo$n$ th de la misma manera.

1voto

muzzlator Puntos 5769

Para cualquier ciclo de separación$(a_1 a_2 ... a_n)$, puede escribirlo como$(a_1 a_2)(a_1 a_3) \dots (a_1 a_n)$.

Para una permutación general, represéntela en notación de ciclo desunido y luego aplique el truco anterior.

Editar: Parece que estás evaluando tus permutaciones con argumentos a la derecha, en cuyo caso$(a_1 a_2 \dots a_n) = (a_1 a_n) \dots (a_1 a_3) (a_1 a_2)$ como dices.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X