Specific permutation

Question

Let $p : A → A$ be a permutation where $A = \{1,...., 2n\}$. Probability that all the cycles in $p$ are of length less than or equal to $n$?

Answer 1

You can have it by remarking that $P(A) = 1- P(\overline{A})$ whith $A$ the event "all the cycles in p are of length less than or equal to n".

And $\overline{A}$ is "at least one cycle in p is of length higher or equal to n+1".

To count all such cycles, we can divide them according to the lenght of the longest cycle, so if we note $C$ the set of all those permuations, and $C_k$ the set of all the permutations for which the longest cycle is of length k, then : $$ |C| = \sum\limits_{k=n+1}^{2n} |C_k|$$

And we notice that if $p$ a permutation has a cycle of length $k\geqslant n+1$, then all the other cycles are of lengths $k\leqslant n$.

So this gives that for $n+1 \leqslant k\leqslant 2n$, $|C_k| = \binom{2n}{k} (k-1)! (2n-k)!$.

($\binom{2n}{k}$ to choose the $k$ elements, $(k-1)!$ to permute the $k$ elements, and $(2n-k)!$ is the number of permutations with the other elements)

So we get that $|C|= \sum\limits_{k=n+1}^{2n} \binom{2n}{k} (k-1)! (2n-k)! = \sum\limits_{k=n+1}^{2n} \frac{(2n)!}{k}$.

Then $$P(A)= 1- P(\overline{A}) = 1 - \frac{|C|}{(2n)!} = 1 - \sum\limits_{k=n+1}^{2n} \frac{1}{k}$$