Supongamos que comenzamos con una permutación aleatoria de la primera $n$ enteros. En cada paso, hacemos lo siguiente:
Dejar los enteros ya en la posición correcta donde están
Para el resto de los números enteros, decir $a_1, a_2, \ldots, a_{k},$ realizar una (al azar) alteración (en otras palabras, $\sigma$ no tiene puntos fijos) $\sigma: \{1, 2, \ldots, k\} \to \{1, 2, \ldots, k\}$ en el conjunto de índices, es decir que tomen $\{a_1, a_2, \ldots, a_{k}\}$ $\{a_{\sigma(1)}, a_{\sigma(2)},\ldots, a_{\sigma(k)}\}.$
Repita esto hasta que llegamos a la orden correcto, es decir, $\{1, 2, 3, \ldots, n\}.$ ¿Cuál es el número esperado de pasos para este proceso?
Ejemplo: Si usted comienza con la permutación $\{2, 1, 4, 3\},$ hay $9$ posibilidades para el siguiente paso (por la composición con un trastorno), es decir,:$\{1, 2, 3, 4\}, \{1, 3, 2, 4\}, \{1, 4, 3, 2\}, \{3, 2, 1, 4\},$ $\{3, 4, 2, 1\}, \{3, 4, 1, 2\}, \{4, 2, 3, 1\}, \{4, 3, 1, 2\},$ y $\{4, 3, 2, 1\}.$
Si, por el contrario, que había comenzado con $\{1, 3, 4, 2\},$, a continuación, las posibilidades serían $\{1, 2, 3, 4\}$ $\{1, 4, 2, 3\}.$
Ver AoPS para la discusión original de este problema. No es difícil escribir una recursividad para $E_n$ en términos de $E_{D_i},$ donde $E_{D_i}$ es el número esperado de pasos que comenzamos con precisión $(n-i)$ puntos fijos. Sin embargo, la estructura de cada trastorno juega un papel importante, por lo que el problema se vuelve extremadamente complicado, incluso para valores pequeños de a $n.$
