Problème ECG1 maths approfondies : permutations sans point fixe et formule du crible

↩ Chapitre : Probabilités finies · Sommes et dénombrement (ECG1-ECG2)

Introduction

n invités déposent leur chapeau au vestiaire ; à la sortie, on leur rend les chapeaux au hasard. Quelle est la probabilité que personne ne récupère le sien ? Étonnamment, elle ne dépend presque pas de n : elle vaut environ 0{,}37, soit \frac1e.

On dénombre les permutations sans point fixe (les dérangements) grâce à la formule du crible, puis on étudie le nombre de points fixes d’une permutation aléatoire.

Le sujet

Problème d’après ESSEC 2004 (partie I), adapté au programme ECG 2021. Durée indicative : 2 heures. Programme : dénombrement, permutations, sommes et coefficients binomiaux, série exponentielle, variables aléatoires finies, Python.

Option : maths approfondies. Niveau : ★★. Faisable : au second semestre pour la limite (série exponentielle) ; le reste dès le chapitre de dénombrement.

Énoncé et corrigé

Soit n\geqslant2, E_n=[\![1,n]\!] et \mathfrak S_n l’ensemble des permutations (bijections) de E_n. On admet la formule du crible : pour des parties A_1,\dots,A_n d’un ensemble fini,

    \[\mathrm{card}\Big(\bigcup_{i=1}^nA_i\Big)=\sum_{k=1}^n(-1)^{k-1}\sum_{1\leqslant i_1<\cdots<i_k\leqslant n}\mathrm{card}(A_{i_1}\cap\cdots\cap A_{i_k}).\]

Un point fixe de \sigma\in\mathfrak S_n est un i tel que \sigma(i)=i. On note d_n le nombre de permutations de E_n sans point fixe, avec d_0=1, et, pour i\in E_n, A_i=\lbrace\sigma\in\mathfrak S_n:\sigma(i)=i\rbrace.

Partie I – Dénombrement des dérangements

1 ▷ Calculer d_2 et d_3 en listant les permutations.

Indication

Pour n=3, il y a 6 permutations ; seuls les deux « cycles » n’ont pas de point fixe.

Corrigé

d_2=1 (l’échange de 1 et 2). Pour n=3, les permutations sans point fixe sont 1\mapsto2\mapsto3\mapsto1 et 1\mapsto3\mapsto2\mapsto1 : d_3=2.

2 ▷ Soit 1\leqslant i_1<\cdots<i_k\leqslant n. Montrer que \mathrm{card}(A_{i_1}\cap\cdots\cap A_{i_k})=(n-k)!.

Indication

Une permutation qui fixe i_1,\dots,i_k est déterminée par sa restriction aux n-k autres éléments, qui est une permutation de ces éléments.

Corrigé

\sigma\in A_{i_1}\cap\cdots\cap A_{i_k} si et seulement si \sigma fixe i_1,\dots,i_k ; elle envoie alors F=E_n\setminus\lbrace i_1,\dots,i_k\rbrace sur F bijectivement. L’application \sigma\mapsto\sigma_{|F} est une bijection vers les permutations de F, au nombre de (n-k)!.

3 ▷ En déduire que d_n=n!\displaystyle\sum_{k=0}^n\frac{(-1)^k}{k!}. Vérifier pour n=2 et n=3, puis calculer d_4 et d_5.

Indication

Les permutations ayant au moins un point fixe forment \bigcup A_i ; il y a \binom nk façons de choisir i_1<\cdots<i_k.

Corrigé

Par le crible et la question 2 : \mathrm{card}\big(\bigcup A_i\big)=\displaystyle\sum_{k=1}^n(-1)^{k-1}\binom nk(n-k)!=\sum_{k=1}^n(-1)^{k-1}\frac{n!}{k!}.

Donc d_n=n!-\mathrm{card}\big(\bigcup A_i\big)=n!\displaystyle\sum_{k=0}^n\frac{(-1)^k}{k!}. Vérification : d_2=2\left(1-1+\frac12\right)=1, d_3=6\left(\frac12-\frac16\right)=2. Puis d_4=24-24+12-4+1=9 et d_5=120-120+60-20+5-1=44.

Partie II – Une permutation au hasard

On choisit une permutation \sigma au hasard dans \mathfrak S_n (loi uniforme). On note F_n son nombre de points fixes et p_n=P(F_n=0).

4 ▷ Exprimer p_n et montrer que p_n\to\dfrac1e. Montrer que \left|p_n-\dfrac1e\right|\leqslant\dfrac1{(n+1)!} et en déduire que d_n est l’entier le plus proche de \dfrac{n!}e pour n\geqslant1.

Indication

\frac1e=\sum_{k\geqslant0}\frac{(-1)^k}{k!} (série exponentielle). Pour majorer le reste, regrouper ses termes deux par deux : \frac1{k!}-\frac1{(k+1)!}\geqslant0.

Corrigé

p_n=\dfrac{d_n}{n!}=\displaystyle\sum_{k=0}^n\frac{(-1)^k}{k!}\to\sum_{k=0}^{+\infty}\frac{(-1)^k}{k!}=e^{-1}.

Le reste R_n=\displaystyle\sum_{k>n}\frac{(-1)^k}{k!} s’écrit (-1)^{n+1}\displaystyle\sum_{j\geqslant0}\left(\frac1{(n+1+2j)!}-\frac1{(n+2+2j)!}\right), somme de termes positifs ; et \displaystyle\sum_{j\geqslant0}\left(\frac1{(n+1+2j)!}-\frac1{(n+2+2j)!}\right)=\frac1{(n+1)!}-\sum_{j\geqslant0}\left(\frac1{(n+2+2j)!}-\frac1{(n+3+2j)!}\right)\leqslant\frac1{(n+1)!}. Donc |R_n|\leqslant\dfrac1{(n+1)!}. Alors \left|d_n-\frac{n!}e\right|=n!\,|R_n|\leqslant\dfrac1{n+1}<\dfrac12 pour n\geqslant2 : d_n étant entier, c’est l’entier le plus proche de \frac{n!}e. Pour n=1, d_1=0 est aussi l’entier le plus proche de \frac1e\approx0{,}37.

5 ▷ Pour 0\leqslant k\leqslant n, montrer que P(F_n=k)=\dfrac{\binom nk\,d_{n-k}}{n!}=\dfrac1{k!}\displaystyle\sum_{j=0}^{n-k}\frac{(-1)^j}{j!}. Quelle est la limite quand n\to+\infty ? Quelle loi reconnaît-on ?

Indication

Choisir l’ensemble des k points fixes, puis une permutation sans point fixe des n-k autres éléments.

Corrigé

Une permutation ayant exactement k points fixes est déterminée par l’ensemble de ses points fixes (\binom nk choix) et par une permutation sans point fixe des n-k éléments restants (d_{n-k} choix). D’où P(F_n=k)=\dfrac{\binom nk d_{n-k}}{n!}=\dfrac{d_{n-k}}{k!\,(n-k)!}=\dfrac1{k!}\displaystyle\sum_{j=0}^{n-k}\frac{(-1)^j}{j!}.

À k fixé, P(F_n=k)\to\dfrac{e^{-1}}{k!} : c’est la loi de Poisson \mathcal P(1). Le nombre de points fixes d’une grande permutation aléatoire suit approximativement une loi de Poisson de paramètre 1.

6 ▷ Écrire F_n comme somme de variables de Bernoulli et calculer E(F_n). Les variables sont-elles indépendantes ?

Indication

F_n=\sum\mathbf 1_{A_i} et P(A_i)=\frac{(n-1)!}{n!}. Pour l’indépendance, comparer P(A_1\cap A_2) et P(A_1)P(A_2).

Corrigé

F_n=\displaystyle\sum_{i=1}^n\mathbf 1_{A_i} avec P(A_i)=\frac{(n-1)!}{n!}=\frac1n. Par linéarité, E(F_n)=n\cdot\frac1n=1 : en moyenne, une seule personne récupère son chapeau, quel que soit n.

P(A_1\cap A_2)=\frac{(n-2)!}{n!}=\frac1{n(n-1)}\neq\frac1{n^2}=P(A_1)P(A_2) : les \mathbf 1_{A_i} ne sont pas indépendantes, et F_n ne suit pas une loi binomiale. La linéarité de l’espérance ne demande aucune indépendance.

7 ▷ (Python) Simuler 10\,000 permutations aléatoires de E_{10} à l’aide de rd.permutation, estimer p_{10} et E(F_{10}), et comparer avec \frac1e et 1.

Indication

rd.permutation(n) renvoie une permutation aléatoire de 0,\dots,n-1 ; compter les indices i tels que s[i] == i.

Corrigé
import numpy as np
import numpy.random as rd

n, M = 10, 10000
F = np.zeros(M)
for m in range(M):
    s = rd.permutation(n)
    F[m] = np.sum(s == np.arange(n))
print(np.mean(F == 0), np.exp(-1))
print(np.mean(F))

On obtient environ 0{,}37 et 1, conformément aux résultats (p_{10}=\frac{1334961}{3628800}\approx0{,}367879).


Pour aller plus loin

Besoin d’aide sur ce chapitre, ou un concours à viser ?

Un blocage sur une notion, une méthode de rédaction à acquérir, un devoir surveillé — ou l’ambition d’intégrer une grande école : Pr. Elakili, agrégé de mathématiques depuis 1991, plus de 25 ans d’enseignement en classes préparatoires, propose des cours particuliers, en présentiel à Casablanca, ou à distance, partout au Maroc et en France.

🎯 Prépas commerciales : réussir les écrits BCE et Ecricome et intégrer les meilleures écoles de commerce (HEC, ESSEC, ESCP…).

Publications similaires