I have some issues with a problem I found on this page: http://www.mast.queensu.ca/~peter/inprocess/prisoners.pdf
The problem goes as follows:
"A group of 100 condemned prisoners are offered the chance to play the
following game. They will be each be allowed to enter a room one at a
time in any order they wish until all 100 have gone in once. In the
room there is a long table with a row of 100 identical wooden boxes
numbered in order from 1 to 100. Each box can be opened and inside it
there is the name of one of the prisoners, such that each of the 100
names appears exactly once. However, the ordering of the names in the
boxes is random. Once inside the room, each prisoner is allowed to open and look inside
50 boxes—any 50 that he wants. After he has opened his 50 boxes he
must leave the room, making sure that the boxes are in exactly the same
state as he found them, and he is no longer able to communicate with
any other prisoner. The reprieve that they have been granted is that at
the end of the game they will all be spared on condition that every prisoner
manages to find the box that contains his own name. On the other
hand, if at least one of the prisoners fails to find his name, they will all
be executed at dawn. Let’s be clear about this—in order to escape execution,
it is necessary that every prisoner find his own name."
Now there is a strategy so that to probability of success is about 30%. Prisoner 1 goes in the room, opens box 1 and if he finds his number, he can leave, if not, then he opens the box whose number he has drawn in the previous box. He needs to find his number within 50 tries. Then prisoner 2 does the same with box 2 etc.
My problem basically is the calculation of the number of permutations having a cycle of length k. On page 3 it is said that there are $\binom {100}{k}$ ways to choose the elements of that cycle, $(k-1)!$ ways to arrange the elements and $(100-k)!$ for the remaining elements. I see why it is $(k-1)!$ arrangements (because it's a cycle and thus there are $(k-1)$ other arrangements that describe the same cycle), but why do we not do this to the remaining elements not being in the long cycle? Why don't we also take every possible permutation of the remaining numbers? Why is it not $(100-k-1)!$?
Best Answer
The formula that the author is trying to construct is :
By identifying that it doesn't matter which elements form the cycle, he reduces the problem to:
So the problem is broken into 2 parts. First, how many ways are there to arrange the first $k$ elements? The reason that it is $(k-1)!$ instead of $k!$, is because you cannot have a fixed point. If any $m^{\text{th}}$ element is $m$, then you have a cycle of length $1$ instead of length $k$. So the first element can't be $1$, the second element can't be $2$, etc.
So choose the first element, you have $k-1$ choices. Suppose you pick $a_1$. Then pick the $a_1^{\text{th}}$ element...it can't be $1$ and it can't be $a_1$, so you have $k-2$ choices. So pick $a_2$. Then pick the $a_2^{\text{th}}$ element. You can't choose $a_2$ or anything that has been chosen so far or $1$, so there are $k-3$ choices. The final $a_k$ choice must be $1$ to complete the cycle, so there are $(k-1)!$ cycles of the first $k$ elements.
Second, how many ways are there to arrange the remaining elements. This is where the author cheats a bit. He silently only considers the cases where $k > n/2$, meaning that you don't have to consider the possibility that there are multiple cycles of length $k$. Consequently , any arrangement of the remaining values is a valid count, even if it has fixed points or no fixed points or other cycles, since there aren't enough remaining elements to form cycle of length $k$. So there are $(n - k)!$ ways to arrange the remaining elements.