Keys inside closed boxes, a question on probability The keys to $n$ boxes are placed randomly in the boxes, one per box, The boxes are closed, which locks them. I would like to know the probability that breaking open $k$ random boxes will allow all the remaining boxes to be unlocked. Could you help me please?
 A: Assume, without loss of generality, that the $k$ random boxes contain keys numbered $1, 2, \ldots, k$.  Accordingly, let $S(n,k)$ be the set of all permutations on $n$ elements such that each cycle has at least one of $1, 2, \ldots, k$.  None of the permutations in $S(n+1,k)$ can have $n+1$ as a singleton cycle; thus each permutation in $S(n+1,k)$ must be obtained by inserting $n+1$ into a cycle in a permutation in $S(n,k)$.  For each permutation in $S(n,k)$, there are $n$ ways to insert $n+1$ into one of its cycles; i.e., after each of the $n$ elements when the permutation is expressed as the product of disjoint cycles.  Thus $S(n+1,k) = n S(n,k)$.  Since $S(k,k) = k!$, we have $S(n,k) = k! k (k+1) \cdots (n-1) = k (n-1)!$, and so the probability that we can open all boxes is $$\frac{S(n,k)}{n!} = \frac{k}{n}.$$  
(The recurrence $S(n+1,k) = n S(n,k)$ is like the recurrence for the Stirling numbers of the first kind $s(n+1,k) = n s(n,k) + s(n,k-1)$ without the second term, as the second term comes from permutations in which $n+1$ forms its own cycle.)
A: This sounds quite difficult in general. It's related to the lengths of cycles that appear in elements of the symmetric group. Here's how...
Suppose we label all the boxes with numbers, and each key with the number of the corresponding box it opens. Then the mapping $f$ defined by mapping the number $x$ to the number on the key inside box $x$ is a permutation on the set $\{1, ..., n\}$. It's easy to see that this mapping is actually a bijection.
Let's take the case $k=1$. If you only break open one box, the probability that you will then be able to open all the others is the probability that a randomly selected element of $S_n$ is an n-cycle. There are $n!$ elements of $S_n$ and $(n-1)!$ possible n-cycles (this is because there are $(n-1)!$ ways to arrange n distinct objects in a circle), hence for the case $k=1$, the probability is $1/n$.
For other values of $k$, a similar approach might work, but you'll have to not only count the number of elements of $S_n$ with constraints on cycle length, but also consider the probability of breaking a box that is part of a particular cycle. This sounds like it has the potential to get very tricky very fast.
A: In effect this is starting with a random permutation $\pi$ of $[n] = \{1,\dots,n\}$, choosing $k$ elements at random, and asking for the probability $p(n,k)$ that we’ve chosen at least one element from each cycle of $\pi$.
Since there are $(n-1)!$ permutations of $[n]$ with just one cycle, $$p(n,1)=\dfrac{(n-1)!}{n!}=\frac1n.$$ If $k=2$, we’re certain to succeed if $\pi$ has only one cycle. If $\pi$ has a cycles of lengths $k$ and $n-k$, where $0<k\le\lfloor n/2\rfloor$, the number of possibilities for $\pi$ is $$\binom{n}{k}(k-1)!(n-k-1)! = \frac{n!}{k(n-k)},$$ and the probability of choosing one element from each cycle is $$\frac{k(n-k)}{\binom{n}2} = \frac{2k(n-k)}{n(n-1)},$$ so 
$$\begin{align*}
p(n,2) &= \frac1n+\frac1{n!}\sum_{k=1}^{\lfloor n/2\rfloor}\left(\frac{n!}{k(n-k)}\cdot\frac{2k(n-k)}{n(n-1)}\right)\\
&= \frac1n + \frac{2\lfloor n/2\rfloor}{n(n-1)}\\
&= \frac2n.
\end{align*}$$
Brute-force calculation yields $p(5,3) = 3/5$ and $p(4,3)=3/4$, so I suspect (perhaps a bit optimistically) that in general $p(n,k)=k/n$ for $k=0,\dots,n$, though I don’t yet see how to prove it.
A: I can do the case $k=1$. You succeed if and only if the (implied) permutation is an $n$-cycle, an event of probability $1/n$ (since there are $n!$ permutations and $(n-1)!$ $n$-cycles. 
A: Building on the prior work in  this discussion I present a proof using
combinatorial  species. The species  $\mathcal{Q}$ of  permutations by
cycles with some non-empty subset  of every cycle being marked has the
specification
$$\mathcal{Q} = \mathfrak{P}
\left(\sum_{q\ge 1}\mathfrak{C}_{=q}(\mathcal{Z})
\times \sum_{p=1}^q {q\choose p} \mathcal{U}^p
\right).$$
The index in the inner sum starts at one because we must  have at least one
mark on every cycle.

Translating the  specification to  generating functions we  obtain the
bivariate generating function
$$G(z, u) =
\exp\left(\sum_{q\ge 1} \frac{z^q}{q} 
\sum_{p=1}^q {q\choose p} u^p\right).$$
This simplifies to
$$\exp\left(\sum_{q\ge 1} \frac{z^q}{q} (u+1)^q
- \sum_{q\ge 1} \frac{z^q}{q} \right)
\\= \exp\left(\log\frac{1}{1-(u+1)z} - \log\frac{1}{1-z}\right)
= \frac{1-z}{1-(u+1)z}.$$
In order to extract coefficients from this re-write like so
$$(1-z)\sum_{q\ge 0} (u+1)^q z^q.$$
It now follows that
$$[z^n] G(z, u) = (u+1)^n - (u+1)^{n-1}$$
and hence
$$[u^k] [z^n] G(z, u) = {n\choose k} - {n-1\choose k}.$$
Divide by ${n\choose k}$ to obtain
$$1 - \frac{(n-1)!}{k! (n-1-k)!} \frac{k! (n-k)!}{n!}
= 1 - \frac{n-k}{n} = \frac{k}{n}.$$
This  confirms  the  results  and conjectures  that  were  established
previously.
This MSE link I contains a relevant computation, as does this MSE link II.
