Exercice 22

1. Les orbites d'une permutation sont deux à deux disjointes (chapitre 17, théorème 1). Deux orbites distinctes à $k$ éléments contiendraient ensemble $2k \geqslant 2n + 2$ éléments de $\llbracket 1\,,2n \rrbracket$, ce qui est impossible : une permutation a au plus une orbite à $k$ éléments.

Une permutation $\sigma$ qui a une orbite $O$ à $k$ éléments est déterminée par le triplet formé de $O$, de la restriction de $\sigma$ à $O$, qui est un $k$-cycle de support $O$, et de la restriction de $\sigma$ à $\overline{O}$, qui est une permutation de $\overline{O}$ ; réciproquement, tout tel triplet définit une permutation qui a $O$ pour orbite. Il y a $\binom{2n}{k}$ choix de $O$, $(k - 1)!$ cycles de support $O$ (exercice 19) et $(2n - k)!$ permutations de $\overline{O}$. $$\boxed{\binom{2n}{k}(k - 1)!\,(2n - k)! = \frac{(2n)!}{k} \text{ permutations ont une orbite à } k \text{ éléments}}$$

2. Les ensembles de permutations ayant une orbite à $k$ éléments, pour $k \in \llbracket n + 1\,,2n \rrbracket$, sont deux à deux disjoints : deux orbites à $k$ et $k'$ éléments, avec $k, k' > n$, contiendraient plus de $2n$ éléments. Une permutation a toutes ses orbites à au plus $n$ éléments si et seulement si elle n'appartient à aucun de ces ensembles, et la proposition 2 (i) et (ii) donne $$a_{n} = (2n)! - \sum_{k=n+1}^{2n} \frac{(2n)!}{k}, \qquad\text{d'où}\qquad \boxed{\frac{a_{n}}{(2n)!} = 1 - \sum_{k=n+1}^{2n} \frac{1}{k} = 1 - \big(H_{2n} - H_{n}\big)}$$ où $H_{m} = \sum_{k=1}^{m} \frac{1}{k}$. Par la proposition 7 du chapitre 20, on a $H_{m} = \ln m + \gamma + o(1)$, donc $$H_{2n} - H_{n} = \ln(2n) - \ln n + o(1) = \ln 2 + o(1),$$ comme le note la remarque qui suit cette proposition. $$\boxed{\lim_{n \to +\infty} \frac{a_{n}}{(2n)!} = 1 - \ln 2 \approx 0{,}3069}$$ Pour $n = 1$, $2$, $3$, $4$, la formule donne $\frac{1}{2}$, $\frac{5}{12}$, $\frac{23}{60}$ et $\frac{307}{840} \approx 0{,}365$, valeurs confirmées par énumération de $\mathfrak{S}_{2}$, $\mathfrak{S}_{4}$, $\mathfrak{S}_{6}$ et $\mathfrak{S}_{8}$. Pour $n = 1$, seule l'identité convient parmi les deux permutations de $\llbracket 1\,,2 \rrbracket$ ✓.

3. On choisit une permutation $\sigma$ au hasard : $\Omega = \mathfrak{S}_{2n}$, muni de la probabilité uniforme. La probabilité que toutes les orbites de $\sigma$ aient au plus $n$ éléments vaut $\frac{a_{n}}{(2n)!}$, et la question 2 montre que la probabilité que $\sigma$ ait une orbite à $k$ éléments vaut $\frac{1}{k}$, pour chaque $k > n$. $$\boxed{\mathrm{P}\big(\text{toutes les orbites de } \sigma \text{ ont au plus } n \text{ éléments}\big) \xrightarrow[n \to +\infty]{} 1 - \ln 2 \approx 0{,}31}$$ Quel que soit $n$, une permutation de $2n$ éléments choisie au hasard a donc, avec probabilité voisine de $\ln 2 \approx 0{,}69$, une orbite qui contient plus de la moitié des éléments : une « grande » orbite est la règle, et non l'exception. Pour $2n = 100$, la probabilité de n'en avoir aucune vaut $1 - (H_{100} - H_{50}) \approx 0{,}312$. C'est le ressort de l'énigme dite des cent prisonniers, où une stratégie qui suit les orbites d'une permutation aléatoire réussit avec cette probabilité, alors que des choix indépendants n'auraient quasiment aucune chance. L'exercice 66 précisera la loi de la longueur de l'orbite d'un élément donné.

Piège. L'erreur la plus répandue est d'appliquer le même raisonnement aux orbites de taille $k \leqslant n$ : une permutation peut en avoir plusieurs, les ensembles correspondants ne sont plus disjoints, et la somme des $\frac{(2n)!}{k}$ ne compte plus rien de simple. C'est l'hypothèse $k > n$ qui rend les événements incompatibles et le calcul exact.