Composición de la permutación para generar todas las permutaciones

Question

Mirando las permutaciones se me ocurrió la siguiente pregunta:

¿Puedes encontrar una permutación $S$ de un conjunto de $n$ elementos tales que al componer esta permutación $n!$ veces describirá todas las permutaciones posibles de este conjunto.

es decir, toda permutación de un conjunto dado puede expresarse como una composición de esta permutación.

Pero no es posible:

Prueba: (no estoy seguro de que sea la prueba más directa)

dejar $S$ sea una permutación, se puede descomponer en ciclos disjuntos. ¡Encontrar una permutación S que verifique la restricción anterior significaría que el mínimo común múltiplo de estos ciclos es n!

Así que al menos descomponer $S$ en un ciclo de $n$ elementos, un ciclo de $n-1$ etc.

Pero es imposible ya que el ciclo es disyuntivo.

---

Ahora bien, puede que en lugar de buscar una única permutación que genere todas las permutaciones, pueda buscar una composición de permutaciones que describa todas las permutaciones de un conjunto.

Por ejemplo, me gustaría encontrar $S_1$ y $S_2$ tal que $S_1$ , $S_1\circ S_2$ , $S_1\circ S_2\circ S_1$ etc. describen todas las permutaciones.

Con un conjunto de $3$ elementos es bastante fácil encontrar tales $S_1$ y $S_2$ :

S1 = 1 2 3  //permute first and second element
     2 1 3

S2 = 1 2 3  //permute first and third element
     3 2 1

Componiendo S1, S1°S2 etc... obtengo

1 2 3 
2 1 3
3 1 2
1 3 2
2 3 1 
3 2 1

Mi pregunta es, cuál es el número mínimo de permutaciones para un conjunto de n elementos que describa todo el conjunto. ¿Hay alguna manera fácil de obtener estas permutaciones?

Gracias de antemano.

---

EDITAR:

gracias por vuestras respuestas he reformulado la pregunta en otra pregunta : Pregunta sobre la permutación

Answer 1

El grupo simétrico en $n$ no es cíclico cuando $n>2$ (ni siquiera es abeliana). Por lo tanto, no puede ser generado por una sola permutación. Sin embargo, siempre se puede generar mediante dos permutaciones, una transposición $(12)$ y un ciclo $(123\ldots n)$ .

Answer 2

(Descargo de responsabilidad: estoy escribiendo una respuesta algo detallada, ya que me di cuenta de que esto venía de SO (y del vocabulario en el que se formuló la pregunta). Pido disculpas si es demasiado prolijo para algunos).

Si he entendido bien, se tiene un conjunto S de tamaño n, y se quieres mirar el conjunto de todas las permutaciones posibles P(S) de ese conjunto.¹

Que P(S) es el grupo simétrico de pedir n, normalmente anotado $S_n$ . Usted quiere encontrar un (mínimo) grupo electrógeno de $S_n$ .

Un grupo generador de $S_n$ es el conjunto de todos los transposiciones $σ_{i,j}$ , para 1 ≤ i,j ≤ n, donde $σ_{i,j}$ es la permutación que intercambia i y j y deja todos los demás elementos sin cambios ².

Para demostrarlo, hay que demostrar que cualquier permutación puede escribirse como "producto" (composición) de transposiciones. Encontrarás numerosas pruebas de ello por ahí, permítanme decir que lo esencial es proceder por inducción sobre n. Entonces, dada una permutación p de (n+1) elementos, se encuentra un producto de transposiciones q tal que (q ∘ p) (n+1) = (n+1) : entonces (q∘p) es una permutación de n elementos, que por hipótesis de inducción se puede escribir como un producto de transposiciones, y a partir de ahí, se puede escribir la propia p como un producto de transposiciones.

Ese conjunto generador no es mínimo: por ejemplo, se puede reducir fácilmente a transposiciones adyacentes (aquellas transposiciones de la forma (i,i+1), para 1 ≤ i < n), y seguir teniendo un conjunto generador.

Sin embargo, esto nos permite notar que para probar un conjunto de permutaciones Π es un conjunto generador de $S_n$ basta con demostrar que cualquier adyacente transposición puede escribirse como un producto de permutaciones en Π.

Tomemos ahora un ciclo de longitud máxima, digamos (1,2,3,...,n), y una única transposición adyacente, digamos (1,2). Observaremos que para cualquier 0 ≤ i < (n-1)³:

$(1,2,3,...,n)^i(1,2)(1,2,3,...,n)^{-i}$ = (i+1,i+2)

Este es el mismo razonamiento que hemos aplicado en el enlace anterior para demostrar que que las transposiciones pueden expresarse como un producto de transposiciones adyacentes: se "desplazan" todos los elementos utilizando el ciclo, se aplica la transposición y luego se "desplaza" todo.

Así, todas las transposiciones adyacentes, y por tanto todas las permutaciones, pueden ser expresarse como producto de un ciclo de longitud máxima y una única transposición adyacente. Dejaré la demostración de que el conjunto generador es mínimo como una ejercicio.

¹: Notarás que el contenido de S es irrelevante, por lo que podemos denotar los elementos de S como {1,...,n}, representando los elementos reales por su indexación.

²: En notación de ciclo También se observa (i,j). Seguiremos utilizando la notación de ciclo en lo sucesivo.

³: Aquí, la exponenciación denota la composición iterada: $p^i$ significa aplicar i veces la permutación p.

Answer 3

Si lo he entendido bien, está buscando elementos $\sigma_1, \dots, \sigma_m$ del grupo simétrico $S_n$ en $n$ elementos tales que la secuencia $\sigma_1$ , $\sigma_1\circ\sigma_2$ , $\sigma_1\circ\sigma_2\circ\sigma_3, \dots, \sigma_1\circ\dots\circ\sigma_m$ , $\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1$ , $\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\sigma_2, \dots, \sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\dots\circ\sigma_m$ , $\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1$ , $\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\sigma_2, \dots$ enumera cada elemento de $S_n$ exactamente una vez.

Definición de $\tau := \sigma_1\circ\dots\circ\sigma_m$ esta lista puede escribirse como $\tau^0\circ\sigma_1, \dots, \tau^0\circ\sigma_1\circ\dots\circ\sigma_{m-1}$ , $\tau^1\circ\sigma_1, \dots, \tau^1\circ\sigma_1\circ\dots\circ\sigma_{m-1}$ , $\tau^2\circ\sigma_1, \dots, \tau^2\circ\sigma_1\circ\dots\circ\sigma_{m-1}, \dots$ .

Escrito así, se ve que si $\tau$ tiene el pedir $k$ (también llamado período ), la secuencia se repite después de $\dots, \tau^{k-1}\circ\sigma_1\circ\dots\circ\sigma_{m-1}, \tau^k$ . Así que si eliges un elemento $\tau$ cuyo orden es máximo en $S_n$ , obtendrá $m$ mínimo, como siempre tienes

$$m = \frac{|S_n|}{k} = \frac{n!}{k}.$$

Ahora elija los elementos $\tau_1, \dots, \tau_m$ de los diferentes cosetas de la derecha del grupo (cíclico) $\langle \tau \rangle$ generado por $\tau$ donde sin pérdida de generalidad se puede tomar $\tau_m = \tau$ . Entonces defina $\sigma_1 := \tau_1$ y $\sigma_i := \tau_{i-1}^{-1}\circ\tau_i$ para $i = 2,\dots, m$ .

Entonces no es difícil demostrar que esta secuencia $\sigma_1, \dots, \sigma_m$ cumple con sus condiciones y es lo más corto posible si la orden de $\tau$ se elige el máximo entre los elementos de $S_n$ . (Si quieres saber este orden, haz otra pregunta ;-)).