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.

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?

share|improve this question
    
More generally would be what the probability is of breaking open $k<n$ boxes and being able to open a maximum of exactly $r$ more boxes with the stolen keys. –  anon Oct 19 '11 at 4:40
3  
The keys are a permutation of the boxes. If you decompose the permutation into cycles, you are asking what is the chance that the k keys found have at least one in each cycle of the permutation. Not that I have an answer... –  Ross Millikan Oct 19 '11 at 4:47
    
As Ross noted, it's equivalent to randomly picking a permutation $\sigma\in S_n$ as well as choosing $k$ numbers out of $\{1,2,\dots,n\}$ and happening to have at least one representative from each cycle in $\sigma$'s cycle decomposition. And this is equivalent to picking a partition of $\{1,2,\dots,n\}$ nonuniformly (weighed by the number of permutations whose cycles correspond to the partition's cells) as well as $k$ of the $n$ numbers and getting at least one from each cell. This might be making it harder than it needs to be... –  anon Oct 19 '11 at 5:52
    
There are two ways to interpret this: (i) Select $k$ boxes randomly at the start, and break them all open. (ii) Select a random, unopened box, and open all the boxes that you can. Do this $k$ times. The answer to (ii) is just the probability that a permutation consists of $k$ or fewer cycles; the answer to (i) is more complicated. Which did you have in mind? –  TonyK Oct 19 '11 at 6:43

5 Answers 5

up vote 3 down vote accepted

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.