Number of loops in permutations

Question

From the famous prisoners problem there are n labelled boxes and inside each the relative number. These are randomly mixed so that you don’t know which number is inside each box. How can I compute the distribution of the loops lengths given n? Where a loop is defined as the path that emerge following from a certain box the number inside it and so on until you reach again the first one.

This is a link about the puzzle and a solution using a simulation https://youtu.be/a1DUUnhk3uE

Answer 1

Let's consider the single question:

What is the probability the longest loop is length $k$, where $k \gt \frac n2$?

This condition means if there is any loop of length $k$ then any other loop cannot be longer than $n-k < k$.

In total there are $n!$ possible patterns.

It should not be difficult to see that of these, there are $(n-1)!$ patterns where the only loop is of length $n$, making the probability of this event $\frac1n$ as mentioned in the video.

It is not much harder to see that there are ${n \choose k} (k-1)! (n-k)! =\frac{n!}{k}$ patterns where the longest loop is of length $k$: you choose the $k$ involved, put them in a loop and then do anything possible with the rest. So the probability of this happening is $\frac1k$

This means that the probability that the longest loop exceeds $\frac n2$ is related to Harmonic numbers: $$\sum\limits_{k=\lfloor n/2\rfloor +1}^n \frac1k = H(n) - H(\lfloor n/2\rfloor)$$ and for large $n$ this is going to have a limit of $\log_e(2)\approx 0.6931472$; the probability the longest loop is not more than $\frac n2$ then has a limit of $1-\log_e(2)\approx 0.3068528$ close to the $0.31$ mentioned in the video

---

It is possible to find the probability that the longest loop is $k$ when $1 \le k\le \frac n2$, but I suspect perhaps not in a closed form. In that case you either want the first loop to be length $k$ and the other loops to be shorter than $k$ or the first loop to be of length less than or equal to $k$ and the longest other loop to be exactly $k$, which gives the recurrence $$P_n(k)=\frac{1}{n}\left(\sum\limits_{i=1}^{k-1} P_{n-k}(i) + \sum\limits_{j=1}^{k} P_{n-j}(k) \right)$$ while when $\frac n2 < k \le n$ we have $P_n(k) =\frac1k$, from earlier.

Clearly $P_n(1)=\frac1{n!}$ and calculating the probabilities up to $n=10$ gives the following table:

      k:   1         2         3          4      5    6   7   8   9   10
n:                                                                       
1         1                                                             
2         1/2       1/2                                                 
3         1/6       1/2       1/3                                       
4         1/24      3/8       1/3        1/4                            
5         1/120     5/24      1/3        1/4    1/5                     
6         1/720     5/48      5/18       1/4    1/5  1/6                
7         1/5040    11/240    7/36       1/4    1/5  1/6 1/7            
8         1/40320   109/5760  23/180     7/32   1/5  1/6 1/7 1/8        
9         1/362880  97/13440  127/1620   27/160 1/5  1/6 1/7 1/8 1/9     
10        1/3628800 211/80640 1013/22680 61/480 9/50 1/6 1/7 1/8 1/9 1/10

where, for example, $P_{10}(4)= \frac{1}{10}\left(\frac{1}{720}+ \frac{5}{48}+\frac{5}{18}+\frac14 + \frac14 +\frac{7}{32}+\frac{27}{160}\right)= \frac{61}{480}$