AnnalesÉcoles d'ingénieurs

X-ENS MP 2024 — Maths A

Nombre de cycles d'une permutation et nombre de facteurs premiers d'un entier · 8 pages

La première partie calcule $\sum \varepsilon(\sigma) x^{\nu(\sigma)} = (x - 1)^{n-1}(x + n - 1)$ grâce à la diagonalisation d'une matrice, en déduit la répartition des dérangements selon leur signature, la formule $D_n = n! \sum (-1)^k/k!$ par inversion de Pascal et la loi du nombre de points fixes ; elle montre ensuite, à l'aide des nombres de Stirling de première espèce, que le nombre de cycles $X_n$ d'une permutation aléatoire a pour espérance $\ln n + \gamma + O(1/n)$ et se concentre autour de $\ln n$. La seconde partie établit des estimations de Tchebychev et de Mertens ($\prod_{p \leqslant n} p \leqslant 4^n$, $\sum_{p \leqslant n} \ln p/p = \ln n + O(1)$, $\sum_{p \leqslant n} 1/p = \ln \ln n + c_1 + O(1/\ln n)$), puis montre qu'en dehors d'un ensemble de densité nulle le nombre $\omega(n)$ de facteurs premiers distincts de $n$ vaut $\ln \ln n \, (1 + o(1))$, comme le nombre de cycles d'une permutation vaut $\ln n$.

Le sujet, partie par partie