La respuesta es, efectivamente $k/n$ como conjetura MJD en los comentarios anteriores. Es esencialmente un argumento de una línea, pero llegaremos a esto gradualmente a través de sucesivas reducciones del problema.
Reducción 1:
Pregunta original: tiene $n$ huchas, cada una con una llave. Las llaves se introducen en las huchas en un orden uniformemente aleatorio (de modo que ahora no hay ninguna llave fuera, por lo que no se puede abrir ninguna hucha), salvo que luego se rompa $k$ huchas. Ahora, con la $k$ llaves disponibles, ¿cuál es la probabilidad de que sea posible desbloquear todas las $n-k$ ¿hay huchas?
Podemos plantear la respuesta en términos de permutaciones de la siguiente manera. Enumerar las huchas $1$ a $n$ . (Sin pérdida de generalidad, podemos hacer la numeración de forma que el $k$ las huchas destrozadas están contadas $1$ a $k$ .) Por cada hucha cerrada $i$ , dejemos que $\pi(i)$ sea la hucha en la que está presente su llave. Tenga en cuenta que $\pi$ es una permutación uniformemente aleatoria de $\{1, \dots, n\}$ . Si en el ciclo $(i, \pi(i), \pi(\pi(i)), \dots)$ al menos uno de los elementos está entre $1$ a $k$ (las huchas destrozadas), entonces usando esa llave podemos abrir la hucha anterior y así sucesivamente, de manera que finalmente $i$ también se puede desbloquear.
Así que la respuesta que queremos es la probabilidad de que en una permutación aleatoria de $\{1, \dots, n\}$ cada ciclo contiene al menos uno de los números $1, \dots, k$ .
Reducción 2:
Hay una canónica representación de una permutación en términos de su descomposición en ciclos: dada una permutación, descomponerla en ciclos, escribir cada ciclo con su elemento más pequeño primero, y escribir estos ciclos en orden decreciente de su elemento más pequeño. A continuación, elimine los paréntesis. Por ejemplo, la permutación $$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 7 & 5 & 6 & 3 & 2 & 4 & 1\end{pmatrix} = \begin{pmatrix}1 & 7 \end{pmatrix} \begin{pmatrix}2 & 5 \end{pmatrix} \begin{pmatrix}3 & 6 & 4 \end{pmatrix} = \begin{pmatrix}3 & 6 & 4 \end{pmatrix} \begin{pmatrix}2 & 5\end{pmatrix} \begin{pmatrix}1 & 7\end{pmatrix} $$ puede ser representado por $$3642517_c$$ (donde he añadido el $_c$ subíndice para dejar claro que se trata del c anónimo c ycle representation).
Se puede comprobar que este proceso es invertible (no se ha perdido ninguna información), por lo que se trata de una representación canónica bien definida.
Dada una permutación $\pi$ , escriba $\pi$ como un producto de ciclos según la representación canónica descrita en el párrafo anterior. Entonces afirmamos que $\pi$ tiene la propiedad deseada (que cada ciclo en $\pi$ contiene al menos uno de los números $1$ a $k$ ) si y sólo si el primer número de la representación canónica es uno de los números $1$ a $k$ :
- Si el primer número es mayor que $k$ entonces como es el elemento más pequeño del primer ciclo, significa que el primer ciclo no contiene ninguno de los números $1$ a $k$ .
- Si el primer número no es mayor que $k$ , entonces el primer ciclo sí contiene algún número $1$ a $k$ (es decir, ese primer número). Es más, como los ciclos se escriben en orden decreciente de elemento más pequeño, cada ciclo posterior tiene su elemento más pequeño que éste, y por tanto también en $1$ a $k$ .
Así que la respuesta que queremos es la probabilidad de que la representación del ciclo canónico de una permutación aleatoria comience con un número de $1$ a $k$ .
Reducción 3:
Para calcular esta respuesta, utilizamos una biyección clásica entre permutaciones, que implica un "juego de palabras" entre las representaciones de los ciclos (como arriba) y la notación de una línea. Es decir, dada una representación canónica del ciclo como la anterior, esta cadena también puede ser interpretado de forma diferente como la representación de una línea de una (otra) permutación de $1$ a $n$ por lo que se obtiene una biyección entre permutaciones. (Esta biyección se llama "transformación de Foata" aquí .)
Debido a la biyección, las representaciones canónicas corresponden a permutaciones de una línea, por lo que la respuesta es la misma que la probabilidad de que el notación de una línea de una permutación comienza con un número de $1$ a $k$ . Como primer elemento de una permutación aleatoria de $1$ a $n$ puede ser cualquiera de los $n$ elementos con igual probabilidad, esto es $$\frac{k}{n}.$$
Ejemplo : Este es un ejemplo con $n=7$ y $k=3$ . (Utilizaré el subíndice $_c$ para indicar que una cadena de símbolos debe interpretarse como el c anónimo c ycle representación de una permutación, y $_o$ para denotar que es una permutación en o notación de líneas).
Entre las permutaciones "buenas" para $n=7$ y $k=3$ son: $$\begin{align} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 4 & 1 & 7 & 6 & 2 & 3 & 5\end{pmatrix} &= \begin{pmatrix}2 & 7 & 5 \end{pmatrix} \begin{pmatrix}1 & 4 & 6 & 3\end{pmatrix} &= 2751463_c \\ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 7 & 5 & 6 & 3 & 2 & 4 & 1\end{pmatrix} &= \begin{pmatrix}3 & 6 & 4 \end{pmatrix} \begin{pmatrix}2 & 5\end{pmatrix} \begin{pmatrix}1 & 7\end{pmatrix} &= 3642517_c \\ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 4 & 6 & 7 & 5 & 2 & 3 & 1\end{pmatrix} &= \begin{pmatrix}1 & 4 & 5 & 2 & 6 & 3 & 7\end{pmatrix} &= 1452637_c \end{align} $$ etc. Si se escriben de forma similar las representaciones canónicas de todos los $7! = 5040$ permutaciones, algunas serán buenas, el resto serán malas, pero cada una de las $7!$ permtuaciones se produce sólo una vez. Queremos contar el número de permutaciones para las que el $_c$ Las representaciones anteriores comienzan con $1$ , $2$ o $3$ . Pero Supongamos que leemos el $_c$ subíndice como $_o$ para contar las permutaciones que empiezan por $1$ , $2$ o $3$ . Está claro que el el recuento no cambia porque sigue siendo exactamente el mismo conjunto de $7!$ cuerdas que miramos. Por supuesto, debido al cambio de interpretación, contaremos con un set de permutaciones, no las "buenas": correspondiendo a lo anterior, contaremos con las de $$\begin{align} 2751463_o &= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 2 & 7 & 5 & 1 & 4 & 6 & 3\end{pmatrix} & \text{bad, because of $ (6) $}\\ 3642517_o &= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 3 & 6 & 4 & 2 & 5 & 1 & 7\end{pmatrix} & \text{bad, because of $ (5) $ and $ (7) $}\\ 1452637_o &= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 1 & 4 & 5 & 2 & 6 & 3 & 7\end{pmatrix} & \text{bad, because of $ (7) $} \end{align}, $$ muchos de los cuales serán malos, pero el contar de permutaciones será la misma.
Esto nos permite calcular que
el número de permutaciones buenas
\= el número de $_c$ representaciones que empiezan por $1$ , $2$ o $3$
\= el número de $_o$ representaciones que empiezan por $1$ , $2$ o $3$
\= $\displaystyle \frac{3}{7} 7!$
y por lo tanto la respuesta (probabilidad) para $n=7$ y $k=3$ es $\displaystyle \frac37$ .
