↩ Chapitre : Probabilités finies · Sommes et dénombrement (ECG1-ECG2)
Introduction
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
: elle vaut environ
, soit
.
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
,
et
l’ensemble des permutations (bijections) de
. On admet la formule du crible : pour des parties
d’un ensemble fini,
![Rendered by QuickLaTeX.com \[\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}).\]](https://prepasmaths360.com/wp-content/ql-cache/quicklatex.com-56cb46a7c289b2848f48e856a75f9301_l3.png)
Un point fixe de
est un
tel que
. On note
le nombre de permutations de
sans point fixe, avec
, et, pour
,
.
Partie I – Dénombrement des dérangements
1 ▷ Calculer
et
en listant les permutations.
Indication
Pour
, il y a
permutations ; seuls les deux « cycles » n’ont pas de point fixe.
Corrigé
(l’échange de
et
). Pour
, les permutations sans point fixe sont
et
:
.
2 ▷ Soit
. Montrer que
.
Indication
Une permutation qui fixe
est déterminée par sa restriction aux
autres éléments, qui est une permutation de ces éléments.
Corrigé
si et seulement si
fixe
; elle envoie alors
sur
bijectivement. L’application
est une bijection vers les permutations de
, au nombre de
.
3 ▷ En déduire que
. Vérifier pour
et
, puis calculer
et
.
Indication
Les permutations ayant au moins un point fixe forment
; il y a
façons de choisir
.
Corrigé
Par le crible et la question 2 :
.
Donc
. Vérification :
,
. Puis
et
.
Partie II – Une permutation au hasard
On choisit une permutation
au hasard dans
(loi uniforme). On note
son nombre de points fixes et
.
4 ▷ Exprimer
et montrer que
. Montrer que
et en déduire que
est l’entier le plus proche de
pour
.
Indication
(série exponentielle). Pour majorer le reste, regrouper ses termes deux par deux :
.
Corrigé
.
Le reste
s’écrit
, somme de termes positifs ; et
. Donc
. Alors
pour
:
étant entier, c’est l’entier le plus proche de
. Pour
,
est aussi l’entier le plus proche de
.
5 ▷ Pour
, montrer que
. Quelle est la limite quand
? Quelle loi reconnaît-on ?
Indication
Choisir l’ensemble des
points fixes, puis une permutation sans point fixe des
autres éléments.
Corrigé
Une permutation ayant exactement
points fixes est déterminée par l’ensemble de ses points fixes (
choix) et par une permutation sans point fixe des
éléments restants (
choix). D’où
.
À
fixé,
: c’est la loi de Poisson
. Le nombre de points fixes d’une grande permutation aléatoire suit approximativement une loi de Poisson de paramètre
.
6 ▷ Écrire
comme somme de variables de Bernoulli et calculer
. Les variables sont-elles indépendantes ?
Indication
et
. Pour l’indépendance, comparer
et
.
Corrigé
avec
. Par linéarité,
: en moyenne, une seule personne récupère son chapeau, quel que soit
.
: les
ne sont pas indépendantes, et
ne suit pas une loi binomiale. La linéarité de l’espérance ne demande aucune indépendance.
7 ▷ (Python) Simuler
permutations aléatoires de
à l’aide de rd.permutation, estimer
et
, et comparer avec
et
.
Indication
rd.permutation(n) renvoie une permutation aléatoire de
; compter les indices
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
et
, conformément aux résultats (
).
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…).
