[ Editar. Ampliado significativamente para añadir ejemplos y (espero) aclaraciones. Siéntase libre de hojear leyendo los cuadros grises].
Un colega me ha pedido información sobre una colección de permutaciones especiales, pero me temo que el tema queda un poco fuera de mi ámbito de experiencia. Las permutaciones en cuestión pueden describirse así:
Permutaciones (en $n$ símbolos) que son un producto de $n$ transposiciones con el notación de ciclo formulario $$(1,s_1)(2,s_2)(3,s_3)\cdots(n,s_n) \qquad\qquad (\star)$$ Es decir, el $i$ El "factor" de la permutación intercambia el elemento en la posición $i$ con el elemento en la posición $s_i$ donde asumimos que $i\neq s_i$ .
Tenga en cuenta que $(\star)$ es una "receta" para una permutación, no la descomposición de la permutación en órbitas. Obsérvese también que hay $(n-1)^n$ recetas, pero sólo $n!$ permutaciones de $n$ símbolos. Varias recetas dan lugar a la misma permutación.
Por ejemplo, para $n=3$ tenemos $2^3=8$ recetas $(1a)(2b)(3c)$ , lo que resulta en sólo $3$ permutaciones: $$\begin{align} (12)(23)(31)&: 123 \to 213 \to 231 \to 132 \\ (12)(21)(32)&: 123 \to 213 \to 123 \to 132 \\ (13)(21)(31)&: 123 \to 321 \to 231 \to 132 \\ \\ (13)(23)(31)&: 123 \to 321 \to 312 \to 213 \\ (12)(23)(32)&: 123 \to 213 \to 231 \to 213 \\ (13)(21)(32)&: 123 \to 321 \to 231 \to 213 \\ \\ (12)(21)(31)&: 123 \to 213 \to 123 \to 321 \\ (13)(23)(32)&: 123 \to 321 \to 312 \to 321 \end{align}$$
Más brevemente: $$132\;(\times 3) \qquad 213\;(\times 3) \qquad 321\;(\times 2)$$ donde el " $(\times m)$ "da la "multiplicidad" de la permutación (es decir, el número de recetas $(\star)$ que lo provocan).
Para $n=4$ tenemos $3^4=81$ recetas, con lo que se obtiene $12$ permutaciones:
$$\begin{align} &1234\;(\times 3)\qquad 1342\;(\times 9)\qquad 1423\;(\times 7)\\ &2143\;(\times 11)\quad\;\; 2314\;(\times 9)\qquad 2431\;(\times 6)\\ &3124\;(\times 7)\qquad 3241\;(\times 6)\qquad 3412\;(\times 7)\\ &4132\;(\times 5)\qquad 4213\;(\times 5) \qquad 4321\;(\times 6) \end{align}$$
Para $n=5$ tenemos $4^5 = 1024$ recetas, con lo que se obtiene $60$ permutaciones:
$$\begin{align} &12354\;(\times 9) \quad \phantom{0}12435\;(\times 9) \quad \phantom{0}12543\;(\times 8) \quad \phantom{0}13245\;(\times 9) \quad \phantom{0}13452\;(\times 28) \quad 13524\;(\times 21) \\ &14253\;(\times 21) \quad 14325\;(\times 8) \quad \phantom{0}14532\;(\times 20) \quad 15234\;(\times 15) \quad 15342\;(\times 7) \quad \phantom{0}15423\;(\times 20) \\ &21345\;(\times 9) \quad \phantom{0}21453\;(\times 37) \quad 21534\;(\times 29) \quad 23154\;(\times 37) \quad 23415\;(\times 28) \quad 23541\;(\times 19) \\ &24135\;(\times 21) \quad 24351\;(\times 18) \quad 24513\;(\times 25) \quad 25143\;(\times 16) \quad 25314\;(\times 14) \quad 25431\;(\times 20) \\ &31254\;(\times 29) \quad 31425\;(\times 21) \quad 31542\;(\times 15) \quad 32145\;(\times 8) \quad \phantom{0}32451\;(\times 19) \quad 32514\;(\times 15) \\ &34152\;(\times 25) \quad 34215\;(\times 20) \quad 34521\;(\times 18) \quad 35124\;(\times 21) \quad 35241\;(\times 14) \quad 35412\;(\times 20) \\ &41235\;(\times 15) \quad 41352\;(\times 14) \quad 41523\;(\times 21) \quad 42153\;(\times 16) \quad 42315\;(\times 7) \quad \phantom{0}42531\;(\times 14) \\ &43125\;(\times 20) \quad 43251\;(\times 20) \quad 43512\;(\times 20) \quad 45132\;(\times 15) \quad 45213\;(\times 15) \quad 45321\;(\times 12) \\ &51243\;(\times 12) \quad 51324\;(\times 10) \quad 51432\;(\times 17) \quad 52134\;(\times 12) \quad 52341\;(\times 6) \quad \phantom{0}52413\;(\times 15) \\ &53142\;(\times 15) \quad 53214\;(\times 17) \quad 53421\;(\times 18) \quad 54123\;(\times 14) \quad 54231\;(\times 14) \quad 54312\;(\times 12) \end{align}$$
Y así sucesivamente.
En lo anterior, obtenemos $n!/2$ permutaciones (lo que significaría necesariamente: todos los miembros de $S_n$ que coinciden con $n$ ), pero no me parece evidente que esto sea siempre así. (Ciertamente, siempre obtenemos $n$ 's-parity permutaciones, pero ¿siempre obtenemos todo de ellos). Señalaré que a mi colega y a mí nos interesa principalmente incluso $n$ ---para que trabajemos dentro (si no con la totalidad) del grupo de alternancia, $A_n$ --- pero teniendo en cuenta todo $n$ puede ayudar a revelar patrones.
Ahora, mi colega y yo estamos interesados en contar el número de estas permutaciones especiales "con multiplicidad" que mueven elementos $i$ , $j$ , $k$ en posiciones $1$ , $2$ , $3$ (donde $n \gg 3$ ). Por ejemplo,
Entre las permutaciones de la forma $(\star)$ en el alfabeto (inglés), ¿cuántas resultan en $26$ -cadenas de letras que empiezan por a $3$ -una palabra de mi elección, por ejemplo, "gato". $\cdots$ " o "perro $\cdots$ "?
(En términos más generales, ¿cuántas permutaciones dan lugar a cadenas que empiezan por un $4$ -, $5$ -, o $m$ -(¿palabra de letras de mi elección?)
En cuanto a las permutaciones dadas anteriormente, podría hacer preguntas como
¿Cuántas permutaciones especiales (con multiplicidad) ...
- ... de $\phantom{45}123$ comenzar con $\phantom{495}2$ ? Respuesta: $\phantom{00}3$
- ... de $\phantom{45}123$ comenzar con $\phantom{49}31$ ? Respuesta: $\phantom{00}0$ *
- ... de $\phantom{5}1234$ comenzar con $\phantom{459}3$ ? Respuesta: $\phantom{0}20$
- ... de $\phantom{5}1234$ comenzar con $\phantom{59}42$ ? Respuesta: $\phantom{00}5$
- ... de $\phantom{5}1234$ comenzar con $\phantom{9}123$ ? Respuesta: $\phantom{00}3$
- ... de $12345$ comenzar con $\phantom{999}3$ ? Respuesta: $217$
- ... de $12345$ comenzar con $\phantom{99}15$ ? Respuesta: $\phantom{4}42$
- ... de $12345$ comenzar con $\phantom{9}321$ ? Respuesta: $\phantom{42}8$
- ... de $12345$ comenzar con $2431$ ? Respuesta: $\phantom{42}0$ *
*La primera $(n-2)$ Las entradas de la permutación determinan el último $2$ (esto se desprende de la paridad), por lo que es posible especificar la longitud $(n-1)$ cadenas de inicio que nunca se producen. (No es que eso nos importe realmente. En nuestra investigación, queremos especificar cadenas iniciales de longitud lejos menos de $n$ .)
Si todo lo que queríamos era saber el número de formas de artículo $i$ puede moverse a su posición $j$ entonces bastaría con un análisis bastante sencillo de los productos de las matrices de permutación. Aquí están las tabulaciones resultantes para $n=3,4,5,6$ , donde el $(i,j)$ cuenta el número de permutaciones (con multiplicidad) que mueven el elemento $i$ en posición $j$ . $$\left( \begin{array}{ccc} 3 & 3 & 2 \\ 3 & 2 & 3 \\ 2 & 3 & 3 \\ \end{array} \right)\qquad \left( \begin{array}{cccc} 19 & 26 & 20 & 16 \\ 23 & 14 & 24 & 20 \\ 21 & 20 & 14 & 26 \\ 18 & 21 & 23 & 19 \\ \end{array} \right)\qquad \left( \begin{array}{ccccc} 175 & 273 & 225 & 189 & 162 \\ 229 & 138 & 252 & 216 & 189 \\ 220 & 201 & 126 & 252 & 225 \\ 208 & 204 & 201 & 138 & 273 \\ 192 & 208 & 220 & 229 & 175 \\ \end{array} \right)$$ $$\left( \begin{array}{cccccc} 2101 & 3524 & 3024 & 2624 & 2304 & 2048 \\ 2869 & 1732 & 3280 & 2880 & 2560 & 2304 \\ 2805 & 2564 & 1552 & 3200 & 2880 & 2624 \\ 2725 & 2580 & 2464 & 1552 & 3280 & 3024 \\ 2000 & 2100 & 2180 & 2244 & 1476 & 2500 \\ 2500 & 2625 & 2725 & 2805 & 2869 & 2101 \\ \end{array} \right)$$
Se observa que las matrices son simétricas en la diagonal secundaria. De forma menos evidente, indican que hay $(n-1)^{n-1}-(n-2)^{n-1}$ formas para el artículo $1$ que se quede en el sitio, y $2(n-2)^{n-1}$ formas para el artículo $1$ para pasar a la posición $n$ . Las fórmulas generales para otras entradas son algo más complicadas de expresar.
Estos recuentos independientes son una cosa, pero no sé cómo contar las circunstancias "compuestas", como (en el caso más simple)
$$\text{"# of ways ( item $ i $ moves to position $ 1 $ ) AND ( item $ j $ moves to position $ 2 $ )"}$$
Por supuesto, la enumeración por "fuerza bruta" -generando todas las permutaciones y contando las que queremos- ya se vuelve computacionalmente intratable una vez que $n$ se acerca a $10$ . Nuestra sospecha es que efectivamente no hay una buena solución en este caso. Dicho esto, parece que posible que la naturaleza específica de la receta $(\star)$ proporciona suficiente estructura para facilitar dicha enumeración, quizás mediante una recursión inteligente o la explotación de algún aspecto del grupo simétrico, $S_n$ (o, tal vez, el grupo alternativo, $A_n$ ). Así que, antes de que mi colega dé carpetazo a este rompecabezas en particular, he pensado en pedir indicaciones aquí. Incluso sería útil saber
¿Se han estudiado estas "permutaciones especiales" en la literatura?
Si es cierto que las recetas $(\star)$ siempre nos dan la mitad de las permutaciones en $S_n$ Entonces este problema se puede dividir en dos partes
- Encuentre el $n$ 's-parity members of $S_n$ que comienzan con una secuencia especificada.
- Cuente el número de maneras en que un miembro de $S_n$ puede descomponerse en la forma $(\star)$ .
