Probability of opening all piggy banks

The answer is indeed $k/n$ as conjectured by MJD in the comments above. It's essentially a one-line argument, but we'll arrive at this gradually through successive reductions of the problem.

Reduction 1:

Original question: you have $n$ piggy banks, each with a key. The keys are dropped into the piggy banks in some uniformly random order (so that now no key is outside, so no piggy bank can be unlocked), except that you then shatter $k$ piggy banks. Now with the $k$ available keys, what is the probability that it is possible to unlock all the remaining $n-k$ piggy banks?

We can state the answer in terms of permutations as follows. Number the piggy banks $1$ to $n$. (Without loss of generality, we can do the numbering such that the $k$ shattered piggy banks are numbered $1$ to $k$.) For each locked piggy bank $i$, let $\pi(i)$ be the piggy bank in which its key is present. Note that $\pi$ is a uniformly random permutation of $\{1, \dots, n\}$. If in the cycle $(i, \pi(i), \pi(\pi(i)), \dots)$ at least one of the elements is among $1$ to $k$ (the shattered piggy banks), then using that key we can unlock the previous piggy bank and so on, so that eventually $i$ can be unlocked as well.

So the answer we want is the probability that in a random permutation of $\{1, \dots, n\}$, every cycle contains at least one of the numbers $1, \dots, k$.

Reduction 2:

There is a canonical representation of a permutation in terms of its cycle decomposition: given a permutation, decompose it into cycles, write each cycle with its smallest element first, and write these cycles in decreasing order of their smallest element. Then remove the parentheses. For example, the permutation $$\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} $$ can be represented by $$3642517_c$$ (where I added the $_c$ subscript to make it clear that this is the canonical cycle representation).

It can be verified that this process is invertible (no information has been lost); thus this is a well-defined canonical representation.

Given a permutation $\pi$, write $\pi$ as a product of cycles according to the canonical representation described in the previous paragraph. Then we claim that $\pi$ has the desired property (that each cycle in $\pi$ contains at least one of the numbers $1$ to $k$) if and only if the first number in the canonical representation is one of the numbers $1$ to $k$:

• If the first number is greater than $k$, then as it is the smallest element in the first cycle, it means that the first cycle does not contain any of the numbers $1$ to $k$.
• If the first number is not greater than $k$, then the first cycle does contain some number $1$ to $k$ (namely that first number). What's more, as the cycles are written in decreasing order of smallest element, every later cycle has its smallest element smaller than this one, and thus also in $1$ to $k$.

So the answer we want is the probability that the canonical cycle representation of a random permutation begins with a number from $1$ to $k$.

Reduction 3:

To calculate this answer, we use a classical bijection between permutations, involving a "pun" between cycle representations (as above) and one-line notation. Namely, given a canonical cycle representation as above, this string can also be differently interpreted as the one-line representation of a (some other) permutation of $1$ to $n$; thus this gives a bijection between permutations. (This bijection is called "Foata's transformation" here.)

Because of the bijection, canonical representations correspond to one-line permutations, so the answer is the same as the probability that the one-line notation of a permutation begins with a number from $1$ to $k$. As the first element of a random permutation of $1$ to $n$ can be any of the $n$ elements with equal probability, this is $$\frac{k}{n}.$$

Example: Here is an example with $n=7$ and $k=3$. (I'll use the subscript $_c$ to denote that a string of symbols is to be interpreted as the canonical cycle representation of a permutation, and $_o$ to denote that it's a permutation in one-line notation.)

Among the "good" permutations for $n=7$ and $k=3$ are: $$\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. If you similarly write down the canonical representations for all $7! = 5040$ permutations, some will be good, the rest will be bad, but each of the $7!$ permtuations occurs just once. We want to count the number of permutations for which the $_c$ representations above start with $1$, $2$, or $3$. But suppose we read the $_c$ subscript as a $_o$ subscript, to count the permutations that start with $1$, $2$, or $3$. It is clear that the count does not change, because it is still exactly the same set of $7!$ strings that we look at. Of course, because of the changed interpretation, we'll be counting a different set of permutations, not our "good" ones: corresponding to the above, we'll be counting ones like $$\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}, $$ many of which will happen to be bad, but the count of permutations will be the same.

This lets us calculate that
the number of good permutations
= the number of $_c$ representations starting with $1$, $2$, or $3$
= the number of $_o$ representations starting with $1$, $2$, or $3$
= $\displaystyle \frac{3}{7} 7!$

and hence the answer (probability) for $n=7$ and $k=3$ is $\displaystyle \frac37$.