Exercice 76

1. Soit $i < j$. L'application $\sigma \mapsto \sigma \circ (i\ j)$ est une bijection de $\mathfrak{S}_{n}$ sur lui-même, qui préserve donc la loi uniforme, et elle échange les événements $\big(\Sigma(i) < \Sigma(j)\big)$ et $\big(\Sigma(i) > \Sigma(j)\big)$. Ces deux événements, incompatibles et de réunion $\Omega$ puisque $\Sigma(i) \neq \Sigma(j)$, ont donc la même probabilité $\frac{1}{2}$ ; c'est le calcul de l'exercice 66 (question 1 (a)), fait pour $i = 1$ et $j = 2$. Le nombre d'inversions est $I = \sum_{i<j} \mathbf{1}_{(\Sigma(i) > \Sigma(j))}$, somme de $\tbinom{n}{2}$ indicatrices, et $$\boxed{\mathrm{E}(I) = \frac{1}{2}\binom{n}{2} = \frac{n(n - 1)}{4}}$$ Une permutation aléatoire a en moyenne la moitié du nombre maximal $\tbinom{n}{2}$ d'inversions, atteint par la permutation $k \mapsto n + 1 - k$. Les inversions sont les « dérangements » de Cramer évoqués au chapitre 17, dont la parité donne la signature (chapitre 17, démonstration de la proposition 4).

2. Soit $k \in \llbracket 1\,,n \rrbracket$. La permutation $\Sigma$ est croissante sur $\llbracket 1\,,L \rrbracket$, donc sur $\llbracket 1\,,k \rrbracket$ si $L \geqslant k$ ; réciproquement, si elle est croissante sur $\llbracket 1\,,k \rrbracket$, le plus grand intervalle de cette forme sur lequel elle l'est a au moins $k$ éléments. Ainsi $(L \geqslant k) = \big(\Sigma(1) < \Sigma(2) < \cdots < \Sigma(k)\big)$. Une permutation de cet événement est déterminée par l'ensemble $\{\sigma(1), \dots, \sigma(k)\}$, que l'on choisit de $\tbinom{n}{k}$ façons, l'ordre étant alors imposé, et par la bijection de $\llbracket k + 1\,,n \rrbracket$ sur les $n - k$ valeurs restantes, choisie de $(n - k)!$ façons : $$\mathrm{P}(L \geqslant k) = \frac{1}{n!}\binom{n}{k}(n - k)!, \qquad \boxed{\mathrm{P}(L \geqslant k) = \frac{1}{k!}}$$ Comme $(L = k) = (L \geqslant k) \setminus (L \geqslant k + 1)$, avec $(L \geqslant k + 1) \subset (L \geqslant k)$, la proposition 7 (ii) donne $$\boxed{\mathrm{P}(L = k) = \frac{1}{k!} - \frac{1}{(k + 1)!} = \frac{k}{(k + 1)!} \ \text{ pour } k \in \llbracket 1\,,n - 1 \rrbracket, \qquad \mathrm{P}(L = n) = \frac{1}{n!}}$$

3. Comme $L$ est à valeurs dans $\llbracket 1\,,n \rrbracket$, on a, pour toute issue, $L = \sum_{k=1}^{n} \mathbf{1}_{(L \geqslant k)}$ : la somme compte les entiers $k \in \llbracket 1\,,n \rrbracket$ tels que $k \leqslant L$, qui sont au nombre de $L$. La linéarité donne $$\mathrm{E}(L) = \sum_{k=1}^{n} \mathrm{P}(L \geqslant k), \qquad \boxed{\mathrm{E}(L) = \sum_{k=1}^{n} \frac{1}{k!} \xrightarrow[n \to +\infty]{} \mathrm{e} - 1}$$ par la série exponentielle du chapitre 20. La convergence est très rapide : pour $n = 6$, $\mathrm{E}(L) \approx 1{,}71806$, contre $\mathrm{e} - 1 \approx 1{,}71828$. Les résultats ont été vérifiés par énumération pour $n \leqslant 6$ ✓.

À retenir. La formule $\mathrm{E}(L) = \sum_{k \geqslant 1} \mathrm{P}(L \geqslant k)$, pour une variable à valeurs entières positives, est souvent plus commode que la définition : ici, les probabilités $\mathrm{P}(L \geqslant k)$ sont plus simples que les $\mathrm{P}(L = k)$. Elle resservira dans les exercices 83 et 90.