Deje $P^0$ ser la identidad de la tupla $(1,2,...,N)$
Deje $P^{i+1}$ ser la tupla después de una permutación $P$ se aplica a $P^i$.
Por ejemplo, si $P$ $(2,1,3,6,4,5)$ que:
$$\begin{align} P^0 &= (1,2,3,4,5,6) \\ P^1 &= (2,1,3,6,4,5) \\ P^2 &= (1,2,3,5,6,4) \\ P^3 &= (2,1,3,4,5,6) \\ \dots \end{align}$$
Dado el valor de$P^4$, ¿cuántos valores posibles de $P$ hay?
Podemos reformular la pregunta: ¿cuántos "cuarto raíces" ¿ un determinado permutación? Es decir, dada una permutación $\sigma$, ¿cuántas permutaciones $\tau$ existe tal que $\tau^4 = \sigma$? La respuesta - vamos a llamar a $N(\sigma)$ - depende de la estructura de $\sigma$.
(La idea básica de qué mirar proviene de la sección 4.8 de generatingfunctionology (por ejemplo, aquí).)
Considere la posibilidad de una permutación $\tau$, descompuesto en ciclos. Para un ciclo particular en $\tau$ de la longitud de la $n$, echemos un vistazo a lo que sucede en $\tau^4$. Si $(a_0, a_1, \dots...)$ es un ciclo en $\tau$ (es decir, $\tau$ es de $a_0$$a_1$, lleva a $a_1$$a_2$, etc.), a continuación, $\tau^4$ es de $a_0$$a_4$, lleva a $a_1$$a_5$, etc. La resultante (sub)permutación puede ser de un solo ciclo o ciclos múltiples, dependiendo $n$:
Si $n$ es impar (relativamente primer a $4$), entonces tenemos un solo ciclo de longitud $n$, que se parece a $(a_0, a_4, a_8, \dots)$ con los índices de recorrer alrededor de modulo $n$.
Si $n$ es incluso pero no es un múltiplo de a $4$, entonces tenemos dos ciclos de longitud $n/2$, uno mirando como $(a_0, a_4, a_8, \dots)$ y que contiene todos los incluso los índices, y la otra mirando como $(a_1, a_5, a_9 \dots)$ y que contiene todos los impares.
Si $n$ es un múltiplo de a $4$, entonces tenemos cuatro ciclos de longitud $n/4$ cada uno, es decir,$(a_0, a_4, \dots)$, $(a_1, a_5, \dots)$, $(a_2, a_6, \dots)$, y $(a_3, a_7, \dots)$.
Girando alrededor de este, podemos mirar a un ciclo de longitud $m$ $\tau^4$ y dicen lo siguiente:
Si $m$ es par, entonces debe de haber llegado, junto con otras tres personas, como el resultado de un solo ciclo de longitud $4m$ que se divide en cuatro ciclos de longitud $m$ cada uno.
Si $m$ es impar, entonces:
Un ciclo de longitud $m$ dio lugar a un ciclo de longitud $m$,
Un ciclo de longitud $2m$ dio lugar a dos ciclos de longitud $m$ cada uno, o
Un ciclo de longitud $4m$ dio lugar a cuatro ciclos de longitud $m$ cada uno.
(Este inmediatamente se da una condición para $N(\sigma)$ a ser positivo, es decir, para la permutación $\sigma$ a tiene al menos una raíz cuarta: para cada número $m$, el número de ciclos de longitud $m$ debe ser un múltiplo de $4$.)
Ahora podemos calcular el $N(\sigma)$. Para cada número de $m$, dejar que el número de ciclos de longitud $m$$\sigma$$c_m$. Entonces:
Si $m$ es par, entonces ($c_m$ debe ser un múltiplo de $4$, y) se puede reconstruir una lista de $c_m/4$ original ciclos de longitud $4m$ cada uno, mediante la selección de $c_m/4$ ordenados en grupos de cuatro, con el pedido de entre ellos y cíclico de orden dentro de cada grupo de cuatro que son irrelevantes, el número de maneras de hacer que es $$\frac{c_m!}{(c_m/4)!4^{c_m/4}}$$ After picking a particular group of four cycles, we can make a big one out of them (find a fourth root of the product of these four cycles) by choosing where in the cyclic ordering we start in each of the four cycles. WLOG we can fix a point in the first cycle where we start so the choice is only among the other three, so we must multiply the above number by $m^3$.
Si $m$ es impar, entonces para cada entero partición de $c_m$ de la forma $$c_m = x + 2y + 4z$$ with $x$, $s$ and $z$ being nonnegative integers, we can pick $x$ cycles of length $m$ by themselves, form $s$ pairs of cycles, and $z$ groups of four. The number of ways of doing this is $$\frac{c_m!}{x! (y!2^y) (z!4^z)}.$$ Again in each of the $y$ pairs we have $m$ ways of putting them together, and in each of the $z$ quadruplets we have $m^3$ maneras de ponerlos juntos.
Con todos los que, la expresión final para $N(\sigma)$ es:
$$N(\sigma) = \left(\prod_{2|m}\frac{c_m!m^{3c_m/4}}{(c_m/4)!4^{c_m/4}}\right) \left(\prod_{2\not|m}\sum_{x,y,z:c_m=x+2y+4z}\frac{c_m! m^y m^{3z}}{x! (y!2^y) (z!4^z)}\right)$$
He comprobado esto con un programa de ordenador para todas las permutaciones de tamaño de hasta 12 años, así que por fin estoy convencido de que la expresión es correcta.
Ejemplos: Considere la posibilidad de su original permutación $\tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 1 & 3 & 6 & 4 & 5\end{pmatrix}$. We can write this in cycle notation as $\tau = (1 2) (3) (4 6 5)$. For this permutation, $\tau^4 = (1)(2)(3)(4 6 5)$. Notice how the cycle of length $2$ has split into two cycles of length $1$ each. If we want to start with this permutation $\sigma = (1)(2)(3)(4 6 5)$ and find fourth roots, we must look at the number of cycles $c_m$ for each $m$:
$m = 1$: $c_m = 3$. Estamos viendo solo el $(1)(2)(3)$ part.
$m = 3$: $c_m = 1$. Estamos buscando a los $(4 6 5)$ part.
De modo que los cuatro cuarto raíces de $\sigma = (1)(2)(3)(4 6 5)$
Deje que $\sigma = (1 2 3)(4 5 6) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 3 & 1 & 5 & 6 & 4\end{pmatrix}$. We can either choose to keep the two $3$-cycles separate ($x = 2$, $y = 0$), giving us the root $(1 2 3)(4 5 6)$ itself, or we can choose to put the pair together ($x = 0, y = 1$), where the choice of the pair is unique but we can interleave the two in three ways - basically the form $(1 ? 3 ? 2 ?)$ with the '?'s filled by $(4 6 5)$ - giving us the roots $(1 4 3 6 2 5)$, $(1 5 3 4 2 6)$ and $(1 6 3 5 2 4)$. Así que tenemos cuatro cuarto raíces.
Deje $\sigma = (1 2)(3 4)(5 6)(7 8 9)$. En este caso para $m = 2$, $c_m = 3$ no es un múltiplo de a $4$, lo $N(\sigma) = 0$.
Deje $\sigma = \begin{pmatrix}1 & 7\end{pmatrix} \begin{pmatrix}2\end{pmatrix} \begin{pmatrix}3 & 16 & 9\end{pmatrix} \begin{pmatrix}4 & 10\end{pmatrix} \begin{pmatrix}5\end{pmatrix} \begin{pmatrix}6 & 18\end{pmatrix} \begin{pmatrix}8\end{pmatrix} \begin{pmatrix}11 & 15 & 13\end{pmatrix} \begin{pmatrix}12 & 17\end{pmatrix} \begin{pmatrix}14\end{pmatrix}$. Contando el cuarto raíces de esta permutación por fuerza bruta enumeración es imposible, pero podemos hacerlo fácilmente mediante la recopilación de los ciclos de la longitud de la misma:
Para $m = 1$: las raíces de la $\begin{pmatrix}2\end{pmatrix} \begin{pmatrix}5\end{pmatrix} \begin{pmatrix}8\end{pmatrix} \begin{pmatrix}14\end{pmatrix}$
Para $m = 2$, las raíces de $\begin{pmatrix}1 & 7\end{pmatrix} \begin{pmatrix}4 & 10\end{pmatrix} \begin{pmatrix}6 & 18\end{pmatrix} \begin{pmatrix}12 & 17\end{pmatrix}$ $6 \times 8 = 48$ en número (elegir una de las $3!$ ordenamientos de los tres últimos, a continuación, uno de los $2^3$ ordenamientos de cada uno de los tres).
Para $m = 3$, las raíces de $\begin{pmatrix}3 & 16 & 9\end{pmatrix} \begin{pmatrix}11 & 15 & 13\end{pmatrix}$
De un modo tan total $N(\sigma) = 10 \times 48 \times 4 = 1920$.
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.
