Exercice 66

Comme dans le troisième exemple de la section 21.5.7, $\Sigma$ est une variable aléatoire de loi uniforme sur $\mathfrak{S}_{n}$ : chaque permutation a la probabilité $\frac{1}{n!}$, et calculer une probabilité revient à dénombrer des permutations.

1.(a) L'application $\sigma \mapsto \sigma \circ (1\ 2)$ est une bijection de $\mathfrak{S}_{n}$ sur lui-même, qui échange les valeurs $\sigma(1)$ et $\sigma(2)$ ; elle échange donc les ensembles $\{\sigma \mid \sigma(1) < \sigma(2)\}$ et $\{\sigma \mid \sigma(1) > \sigma(2)\}$, qui ont le même cardinal et forment une partition de $\mathfrak{S}_{n}$, puisque $\sigma(1) \neq \sigma(2)$. $$\boxed{\mathrm{P}\big(\Sigma(1) < \Sigma(2)\big) = \frac{1}{2}}$$

(b) L'exemple du cours donne $\mathrm{P}(\Sigma(1) = i) = \frac{1}{n}$ : $\Sigma(1)$ et $\Sigma(2)$ suivent la loi uniforme sur $\llbracket 1\,,n \rrbracket$. Pour $i \neq j$, les permutations telles que $\sigma(1) = i$ et $\sigma(2) = j$ sont en bijection avec les bijections de $\llbracket 3\,,n \rrbracket$ sur $\llbracket 1\,,n \rrbracket \setminus \{i, j\}$, qui sont au nombre de $(n - 2)!$ (théorème 1) ; pour $i = j$, il n'y en a aucune, par injectivité. Donc $$\boxed{\mathrm{P}\big(\Sigma(1) = i, \Sigma(2) = j\big) = \begin{cases} \frac{1}{n(n - 1)} & \text{si } i \neq j \\ 0 & \text{si } i = j \end{cases}}$$ Comme $\mathrm{P}(\Sigma(1) = 1, \Sigma(2) = 1) = 0 \neq \frac{1}{n^{2}} = \mathrm{P}(\Sigma(1) = 1)\mathrm{P}(\Sigma(2) = 1)$, les variables $\Sigma(1)$ et $\Sigma(2)$ ne sont pas indépendantes. C'est la loi conjointe de deux tirages sans remise dans une urne de $n$ boules numérotées, dont le cas $n = 3$ figure dans la section 21.5.4.

(c) Les couples $(i, j)$ d'entiers consécutifs de $\llbracket 1\,,n \rrbracket$, c'est-à-dire tels que $|i - j| = 1$, sont au nombre de $2(n - 1)$ : $(i, i + 1)$ et $(i + 1, i)$ pour $i \in \llbracket 1\,,n - 1 \rrbracket$. Par la question précédente, $$\boxed{\mathrm{P}\big(|\Sigma(1) - \Sigma(2)| = 1\big) = \frac{2(n - 1)}{n(n - 1)} = \frac{2}{n}}$$ Pour $n = 2$, on trouve $1$, ce qui est attendu, puisque $\{\Sigma(1), \Sigma(2)\} = \{1, 2\}$.

2.(a) Rappelons que les orbites de $\sigma$ sont les classes de la relation « $j = \sigma^{p}(i)$ pour un $p \in \mathbb{Z}$ » (chapitre 17, démonstration du théorème 1), et que $\sigma$ agit sur une orbite à $k \geqslant 2$ éléments comme un $k$-cycle. La partie $C$ est une orbite de $\sigma$ si et seulement si $\sigma(C) \subset C$, ce qui entraîne $\sigma(C) = C$ par injectivité et $\sigma(E \setminus C) = E \setminus C$, où $E = \llbracket 1\,,n \rrbracket$, et si la restriction $\sigma_{|C}$, qui est une permutation de $C$, a pour seule orbite $C$.

L'application $\sigma \mapsto (\sigma_{|C}, \sigma_{|E \setminus C})$ est une bijection de l'ensemble des permutations qui stabilisent $C$ sur $\mathfrak{S}_{C} \times \mathfrak{S}_{E \setminus C}$. Il reste à dénombrer les permutations de $C$ ayant une seule orbite. Soit $c$ le plus petit élément de $C$ ; une telle permutation $\tau$ est déterminée par la suite $\big(\tau(c), \tau^{2}(c), \dots, \tau^{k-1}(c)\big)$, qui est une liste ordonnée des $k - 1$ éléments de $C \setminus \{c\}$, et toute liste de ce type provient d'une unique telle permutation, le cycle $\big(c\ \tau(c)\ \cdots\ \tau^{k-1}(c)\big)$. Il y en a donc $(k - 1)!$, y compris pour $k = 1$, où seule l'identité de $C$ convient. Ainsi $C$ est une orbite de $(k - 1)!\,(n - k)!$ permutations : $$\boxed{\mathrm{P}(C \text{ est une orbite de } \Sigma) = \frac{(k - 1)!\,(n - k)!}{n!} = \frac{1}{k\binom{n}{k}}}$$ Pour $k = n$, on obtient la probabilité $\frac{1}{n}$ que $\Sigma$ soit un $n$-cycle ; pour $k = 1$, la probabilité $\frac{1}{n}$ que l'élément de $C$ soit un point fixe.

(b) Les entiers $1$ et $2$ sont dans la même orbite si et seulement si celle-ci est l'une des parties $C$ contenant $1$ et $2$ ; pour une permutation donnée, une seule partie convient, donc les événements « $C$ est une orbite », pour ces parties $C$, sont deux à deux incompatibles. Il y a $\binom{n - 2}{k - 2}$ parties à $k$ éléments contenant $1$ et $2$, pour $k \in \llbracket 2\,,n \rrbracket$, et $$\binom{n - 2}{k - 2}\,\frac{(k - 1)!\,(n - k)!}{n!} = \frac{(n - 2)!}{(k - 2)!\,(n - k)!} \cdot \frac{(k - 1)!\,(n - k)!}{n!} = \frac{k - 1}{n(n - 1)}.$$ En sommant sur $k$, avec $\sum_{k=2}^{n} (k - 1) = \frac{n(n - 1)}{2}$, $$\boxed{\mathrm{P}(1 \text{ et } 2 \text{ appartiennent à la même orbite de } \Sigma) = \frac{1}{2}}$$

(c) Soit $L$ le nombre d'éléments de l'orbite de $\Sigma$ qui contient $1$, et $k \in \llbracket 1\,,n \rrbracket$. L'événement $(L = k)$ est la réunion disjointe, sur les $\binom{n - 1}{k - 1}$ parties $C$ à $k$ éléments contenant $1$, des événements « $C$ est une orbite de $\Sigma$ » : $$\mathrm{P}(L = k) = \binom{n - 1}{k - 1}\frac{(k - 1)!\,(n - k)!}{n!} = \frac{(n - 1)!}{n!}, \qquad \boxed{L \sim \mathcal{U}(\llbracket 1\,,n \rrbracket)}$$ Le calcul a été contrôlé par énumération de $\mathfrak{S}_{n}$ pour $n \leqslant 6$ ✓.

À retenir. Ces résultats surprennent : on s'attendrait à ce que les petites orbites soient plus probables, alors que l'orbite de $1$ a une longueur uniforme, et qu'il y a une chance sur deux que $1$ et $2$ soient dans la même orbite, quel que soit $n$. Le cas $k = n$, où $\Sigma$ est un $n$-cycle avec la probabilité $\frac{1}{n}$, sera retrouvé dans l'exercice 69, qui utilise aussi les parties stables, et la question 2(a) prolonge l'exercice 17, où les parties stables par une permutation étaient les réunions d'orbites.