Deje $P_n$ denota el conjunto de pares $(x,y)$ de las permutaciones en $S_{2n}$, donde cada permutación es un producto de $n$ ciclos disjuntos de longitud dos. Deje que i y j dos elementos fijos del conjunto $\{1,2, \cdots,2n\}$. Seleccione un elemento $(x,y)$$P_n$. ¿Cuál es la probabilidad de que el producto $xy$ contiene $i$ $j$ en el mismo ciclo?
Respuesta
¿Demasiados anuncios?
JiminyCricket
Puntos
143
Ya que cada elemento distinto de $i$ $1$ $2n-1$ de probabilidad de ser $j$, la probabilidad deseada es $(a_n-1)/(2n-1)$ donde $a_n$ es la duración esperada del ciclo que contiene a $i$. Deje $k=y(i)$. Hay un $1$ $2n-1$ de probabilidad de que $x(k)=i$, en cuyo caso, la duración del ciclo es de $1$. De lo contrario, swap $i$ $x(k)$ en el ciclo de la representación de $y$. Ahora los dos permutaciones de dos ciclos, con $k$$x(k)$, el resto de los ciclos forman dos admisible permutaciones en $S_{2(n-1)}$, y la longitud del ciclo que contiene a $i$ en su producto es uno menos que la longitud del ciclo que contiene a $i$ en el producto original. Esto produce la recurrencia
$$ a_n=1+\frac{2n-2}{2n-1}a_{n-1} $$
con la condición inicial $a_1=1$, y es fácilmente comprobado que esto es resuelto por $a_n=\frac13(2n+1)$. Por lo tanto la probabilidad deseada es
$$ \frac{\frac13(2n+1)-1}{2n-1}=\frac23\frac{n-1}{2n-1}\;. $$
Es interesante que el producto sólo puede contener ciclos hasta la longitud de la $n$. Para un gran $n$, el promedio de duración del ciclo que contiene a $i$ es de aproximadamente $2/3$, por lo que la probabilidad de $j$ que es aproximadamente el $1/3$.
