Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Interesting problem I found, and can't solve it since the morning:

We have $n$ keys and $n$ piggy banks. Each key fits only one piggy bank. We randomly put exactly one key in each piggy bank. Then we randomly shatter $1\le k\le n$ piggy banks. What is the probability that we are able to open all other piggy banks?

Really interested me. I thought about approach with cycles in permutation. When we number all piggy banks and their keys with numbers $1...n$ and then denote $f(i)$ - the number of key that is in $i$-th piggy bank then we have permutation $f$. So to open all piggy banks we need at least one key from each cycle in permutation $f$. But I completely don't know how to count it. Can anybody help?

share|improve this question
    
I'm not sure I fully understand the second part of your question about shattering piggy banks, but I believe that this would be useful for the first part: en.wikipedia.org/wiki/Derangement –  Vincent Tjeng Mar 4 '13 at 15:16
1  
@VincentTjeng, There is no first and second part. Whole problem is one part. We shatter randomly selected $k$ piggy banks so we have access to keys that we firstly put in them. And the problem is to find probability that we have enough keys (after shattering) to open all piggy banks left. Once we open (with a key) piggy bank, we have key in it. –  xan Mar 4 '13 at 15:44
1  
oh, I see. that explanation makes it clearer! –  Vincent Tjeng Mar 4 '13 at 16:22
1  
Very nice question! I'll just note that the variant of this question, asking for the probability that we can't open any of the piggy banks, is much easier: the answer to that is $1/\binom{n}{k}$. –  ShreevatsaR Mar 4 '13 at 17:02
2  
Hand calculation of cases up to $n=4$ reveals that the answer is very likely $\frac kn$, so there ought to be a simple and brilliant argument. –  MJD Mar 4 '13 at 20:28

2 Answers 2

up vote 8 down vote accepted
+150

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$.

share|improve this answer
    
Why is there a $k/n$ probability that the first number in the first cycle is between 1 and $k$? This first number is certainly not uniformly distributed on $[1,n]$. Your claim that "the first element of a random permutation of 1 to n can be any of the n elements with equal probability" is true for permutations written in one-line notation but not in cycle notation. –  MJD Mar 5 '13 at 1:52
    
@MJD: Yes, that's where I'm using the bijection. –  ShreevatsaR Mar 5 '13 at 1:54
    
But your argument in the bullet points is based on the first element of the cycle representation, not the first element of the one-line representation. The first element of the permutation $p$ in one-line notation is just $p(1)$, which is equally likely to be any number in $[1,n]$, but which doesn't seem to support any of the arguments you make in your bulleted section. –  MJD Mar 5 '13 at 1:56
1  
@ShreevatsaR, finally understood. This is just brilliant! Thank you very, very much :-) –  xan Mar 5 '13 at 10:29
1  
@MJD: Glad you liked the bijection. Apparently it's also known as "Foata's fundamental correspondence". Also, coincidentally just today while reading Analytic Combinatorics (which is available online), around p. 142 I found another application: this bijection maps the number of "records" in a permutation (in _o above, the number of elements that have nothing bigger to the left) to the number of cycles. So for instance the answer to "how many permutations on $n$ elements have $k$ 'records'?" is the Stirling cycle numbers. –  ShreevatsaR Jan 6 at 5:08

You might as well number the piggybanks in the order in which you break them. If $k = 1$, the permutation must be a $n$-cycle, for $k = 2$ the possibilities are one $n$-cycle, one $1$-cycle $(1)$ or $(2)$ and an $n - 1$ cycle including the other, or a $r$ cycle including 1 and an $s$ cycle including 2 where $r + s = n$. It gets more complicated as $k$ grows, there are several possibilities with cycles that stay in $[1 .. k]$ as long as the other cycles cover $[k .. n]$ and have elements in $[1 .. k]$. I don't see any easy way to make this observation into a recurrence :(

share|improve this answer
3  
These are nice thoughts on the question, but they are probably better suited to a comment than an answer. –  robjohn Mar 5 '13 at 11:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.