Dénombrement des $k$-cycles

• Le nombre de façons de choisir $k$ éléments parmi $n$ est $\binom{n}{k}$.
• Sur ces $k$ éléments, il y a $k!$ permutations linéaires possibles.
• Puisqu'un cycle de longueur $k$ est invariant par décalage circulaire, chaque cycle est compté $k$ fois parmi ces permutations linéaires.
• Le nombre exact de $k$-cycles distincts que l'on peut former avec ces $k$ éléments est donc :
  \[\frac{k!}{k} = (k - 1)!\]

Calcul de la probabilité $p_n$

• On considère l'événement contraire $\overline{A}$ : la permutation possède au moins un cycle de longueur $k > \frac{n}{2}$.
• Puisque $k > \frac{n}{2}$, la permutation ne peut avoir qu'un unique cycle d'une telle longueur.
• Les événements $E_k$ = "la permutation possède un $k$-cycle" pour $k \in \left\{\lfloor\frac{n}{2}\rfloor+1, \dots, n\right\}$ sont donc deux à deux disjoints.
• Le nombre de permutations réalisant $E_k$ s'obtient en choisissant les $k$ éléments, en formant le cycle, puis en permutant les $n - k$ éléments restants :
  \[|E_k| = \binom{n}{k} \times (k - 1)! \times (n - k)! = \frac{n!}{k}\]
• La probabilité de l'événement $E_k$ est donc :
  \[P(E_k) = \frac{|E_k|}{n!} = \frac{1}{k}\]
• Par disjonction, la probabilité de l'événement contraire est la somme des probabilités :
  \[P(\overline{A}) = \sum_{k=\lfloor\frac{n}{2}\rfloor+1}^n \frac{1}{k}\]
• On en déduit l'expression exacte de $p_n$ :
  \[p_n = 1 - \sum_{k=\lfloor\frac{n}{2}\rfloor+1}^n \frac{1}{k}\]

Étude de la limite de $p_n$

• En notant $H_n = \sum_{i=1}^n \frac{1}{i}$ la série harmonique, on réécrit la somme :
  \[p_n = 1 - \left(H_n - H_{\lfloor\frac{n}{2}\rfloor}\right)\]
• En utilisant le développement asymptotique $H_n = \ln(n) + \gamma + o(1)$ :
  \[H_n - H_{\lfloor\frac{n}{2}\rfloor} = \ln(n) - \ln\left(\lfloor\frac{n}{2}\rfloor\right) + o(1)\]
• Puisque $\lfloor\frac{n}{2}\rfloor \sim \frac{n}{2}$ quand $n \to +\infty$, on obtient :
  \[\lim_{n\to+\infty} \left(H_n - H_{\lfloor\frac{n}{2}\rfloor}\right) = \lim_{n\to+\infty} \left(\ln(n) - \ln\left(\frac{n}{2}\right)\right) = \ln(2)\]
• On conclut finalement :
  \[\lim_{n\to+\infty} p_n = 1 - \ln(2)\]