Probabilidad de un ciclo-m de largo

Question

Usted tiene una baraja de cartas numeradas de$1$$n$. Después de barajar las cartas al azar, se ponen en cajas numeradas, de$1$$n$, es decir, $1$ tarjeta por caja. Así que el cuadro de $1$ puede contener cualquier tarjeta de$1$$n$, etc.

Ahora vaya a la caja de $1$ y mire la tarjeta en el interior. Si la tarjeta es, por ejemplo,$4$, de ir a la casilla de número de $4$ y mire la tarjeta en el interior. Que tarjeta te dice a dónde ir. De continuar, hasta llegar a la tarjeta de $1$ (que sería decirle que vaya a la caja de $1$, que está vacía). El número de tarjetas (o pasos) es el número de un ciclo que acaba de descubrir. Usted, a continuación, vaya a la primera casilla con una tarjeta en el interior, y repita el proceso. Usted termina con $1$ $n$ciclos de $1$ $n$tarjetas.

Por ejemplo, usted podría tener una muy gran ciclo con todas las tarjetas, o un gran ciclo con la mitad de las cartas y un montón de ciclos menores. Si se mira en el cuadro de número de $7$ y encontrar la tarjeta con un $7$, que es un $1$-ciclo.

¿Cuál es la probabilidad de que ningún ciclo es más de ${n \over 2}$?

Gracias!

Answer 1

Si$n=2m$, hay$$\binom{2m}{m+1}m!(m-1)!=\frac{(2m)!}{m+1} $ $ permutaciones con un ciclo de longitud$m+1$,$$\binom{2m}{m+2}(m+1)!(m-2)!=\frac{(2m)!}{m+2} $ $ permutaciones con un ciclo de longitud$m+2$ y así sucesivamente, por lo que la la probabilidad es:$$ 1-\sum_{k=m+1}^{2m}\frac{1}{k} = 1-(H_{2m}-H_m).$ $ Si$n=2m+1$ la probabilidad es:$$ 1-\sum_{k=m+1}^{2m+1}\frac{1}{k}=1-(H_{2m+1}-H_m).$ $ En ambos casos tenemos que la probabilidad es:$$ (1-\log 2)+\frac{1}{2n}+O\left(\frac{1}{n^2}\right)\geq\color{red}{30,68\%}. $ $