Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
204 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 
Le cas équiprobable. next up previous
suivant: Le schéma Succès-Echec. monter: epb précédent: L'espace est fini ou

Le cas équiprobable.

Considérons le cas particulier de la Proposition 2.3 où $ \Omega$ a un nombre fini $ N=\vert\Omega\vert$ d'éléments et où tous les $ p_x$ sont égaux (et donc égaux à $ 1/N.$) Dans ce cas, si $ A\subset \Omega$ on a

$\displaystyle P(A) =\frac{\vert A\vert}{\vert\Omega\vert}=\
\frac{\mathrm{nombre de  cas favorables}}{\mathrm{nombre de cas possibles}}.$

Pour exploiter cette égalité, il est nécessaire de posséder quelques principes généraux de dénombrement d'ensembles et de fonctions contenus dans les deux prochains théorèmes. Si $ E$ et $ F$ sont des ensembles, on note par $ E\times F$ leur produit cartésien, c'est-à-dire l'ensemble des couples $ (x,y)$ tels que $ x\in E$ et $ y\in F.$ On note par $ F^E$ l'ensemble des fonctions $ f$ définies sur $ E$ et à valeurs dans $ F.$ Si $ E$ est fini et est de taille $ n=\vert E\vert$ et si $ k$ est un entier avec $ 0\leq k\leq n$ on note par $ \mathcal{P}_k(E)$ l'ensemble des parties de $ E$ de taille $ k.$

Théorème 2.5

  1. Si $ E$ et $ F$ sont des ensembles finis, alors $ \vert E\times F\vert=\vert E\vert\times\vert F\vert.$ Plus généralement, si $ F_1,\ldots, F_n$ sont des ensembles finis: $ \vert F_1\times\cdots\times F_n\vert=\vert F_1\vert\times\cdots\times\vert F_n\vert.$ Ensuite $ \vert F^E\vert=\vert F\vert^{\vert E\vert}.$ Enfin, si $ p=\vert F\vert\geq n=\vert E\vert,$ le nombre de fonctions injectives de $ E$ vers $ F$ est $ p(p-1)(p-2)\cdots(p-n+1).$ En particulier, le nombre de fonctions bijectives de $ E$ vers $ E$, appelées permutations de $ E$, est égal à $ n!$

  2. Si $ E$ est fini et est de taille $ n=\vert E\vert$ et si $ k$ est un entier avec $ 0\leq k\leq n$ alors

    $\displaystyle \vert\mathcal{P}_k(E)\vert=C^k_n=\frac{n!}{k!(n-k)!}=\frac{n(n-1)\cdots(n-k+1)}{k!}.$

$  $

Démonstration

  1. La première formule est évidente : si $ e_1,\ldots,e_n$ et $ f_1, \ldots,f_p$ sont les éléments de $ E$ et $ F$, le nombre de couples $ (e_i,f_j)$ est $ np.$ L'extension à $ n$ facteurs est immédiate également. Cette extension est ensuite appliquée au cas particulier où tous les ensembles $ F_j$ sont égaux au même ensemble $ F.$ Si $ \vert E\vert=n,$ il y a alors bijection entre $ F^E$ et $ F\times \cdots\times F$ ($ n$ fois). D'où $ \vert F^E\vert=\vert F\vert\times \cdots\times \vert F\vert=\vert F\vert^n=\vert F\vert^{\vert E\vert}.$ Quant au nombre de fonctions injectives, la formule donnée se justifie facilement: on identifie $ E$ à $ (1,2,\ldots,n),$ et l'image de 1 peut occuper $ p$ positions, l'image de 2 peut occuper une des $ p-1$ positions restantes, l'image de 3 une des $ p-2$ positions restantes, etc. Faire $ E=F$ pour le nombre de permutations de $ E$ (on rappelle que si $ \vert E\vert=\vert F\vert$ avec $ E$ fini, alors une fonction $ f$ de $ E$ vers $ F$ est injective si et seulement si elle est surjective).

  2. Rappelons pour cette partie la formule de Pascal:
$  $

Proposition 2.6 Si $ k$ est un entier avec $ 1\leq k\leq n$ on a

$\displaystyle C^{k-1}_n+C^k_n=C^k_{n+1}.$

$  $

Démonstration

$\displaystyle C^{k-1}_n+C^k_n=
\frac{n!}{(k-1)!(n-k)!}\left[\frac{1}{n-k+1}+\frac{1}{k}\right]=
\frac{(n+1)!}{k)!(n+1-k)!}=C^k_{n+1}.$

$  $

Pour prouver 2) on observe que c'est trivial pour $ k=0$, puis on fixe $ k>0$ et on montre 2) par récurrence sur $ n.$ C'est trivial pour $ n=k.$ Supposons enfin 2) vrai pour $ n$ et supposons que $ E$ ait $ n+1$ éléments, qu'on prend égaux à $ 1,2,\ldots,n+1$ sans perte de généralité. Soit aussi $ E'$ l'ensemble des $ n$ premiers entiers. On partage alors les éléments de $ \mathcal{P}_k(E)$ en deux catégories:

Catégorie 1: ceux qui ne contiennent pas $ n+1.$

Catégorie 2: ceux qui contiennent $ n+1.$

La catégorie 1 est égale à $ \mathcal{P}_k(E')$ et a donc $ C^k_n$ éléments par l'hypothèse de récurrence. La catégorie 2 est en bijection avec $ \mathcal{P}_{k-1}(E')$ ( enlever $ n+1$ à un membre de la catégorie 2 pour avoir un élément de $ \mathcal{P}_{k-1}(E'))$ et donc par l'hypothèse de récurrence a $ C^{k-1}_n$ éléments. La formule de Pascal montre alors que $ \mathcal{P}_k(E)$ a $ C^k_{n+1}$ éléments et la récurrence est étendue.

Voici un exemple d'application du théorème précédent.

Proposition Anniversaires. $ n$ personnes sont réunies. Quelle est la probabilité que au moins deux d'entre elles aient le même anniversaire?

On formalise le problème en le simplifiant un peu: on ignore d'abord le problème du 29 février, et on postule donc que l'espace des observablesest $ \Omega=F^E$$ E$ est l'ensemble des personnes et où $ F$ est l'ensemble des $ p=365$ jours de l'année: on observe donc la fonction $ f\in\Omega$ qui à chaque personne associe son anniversaire. On postule ensuite qu'on est dans le cas équiprobable, ce qui n'est qu'une approximation: il y a plus d'enfants conçus au printemps et en été qu'en novembre sous nos climats. Finalement, il est plus facile de calculer la probabilité du complémentaire $ A^c$ de l'évènement $ A$ "deux personnes au moins ont le même anniversaire", car c'est la probabilité que la fonction $ f$ soit injective. D'après le théorème 2.5 1), c'est

$\displaystyle P(A^c)=\frac{1}{365^n}365(365-1)\cdots(365-n+1)=
\prod_{k=1}^{n-1}(1-\frac{k}{365})=\exp\sum_{k=1}^{n-1}\log(1-\frac{k}{365}).$

Si $ n$ n'est pas grand, une évaluation approximative de cette somme se fait en remplaçant $ \log(1-x)$ par $ -x$ et en utilisant la somme d'une progression arithmétique étudiée en Terminale

$\displaystyle \sum_{k=1}^{n-1}k=\frac{1}{2}n(n-1)\sim ný/2,$

qui conduit à l'approximation $ P(A^c)\sim \exp(-ný/730).$ Pour voir par exemple pour quel $ n$ on a $ P(A^c)\sim 1/2$ on prend $ n\sim \sqrt{730\log 2}\sim 23.$ Pour un calcul plus sérieux, on peut utiliser l'encadrement pour $ 0<x<1:$

$\displaystyle -x-\frac{xý}{2(1-x)}<\log(1-x)<-x-\frac{xý}{2};$

La majoration de droite se déduit du développement en série entière, celle de gauche se montre en étudiant la fonction $ x+\frac{xý}{2(1-x)}+\log(1-x).$ On a aussi besoin de la somme des premiers carrés:

$\displaystyle \sum_{k=1}^{n-1}k^2=\frac{1}{6}n(2n-1)(n-1)\sim n^3/3,$

qui s'établit par récurrence. Si $ x\leq (n-1)/365$, alors $ -1/(1-x)\geq-365/(365-n+1).$ D'où l'encadrement :

$\displaystyle -\frac{n(n-1)}{2}\frac{1}{365}
-\frac{n(n-1)(2n+1)}{6}\frac{1}{2\times 365^2}\frac{365}{365-n+1}<$

$\displaystyle \log P(A^c)
<-\frac{n(n-1)}{2}\frac{1}{365}-\frac{n(n-1)(2n+1)}{6}\frac{1}{2\times 365^2}.$

Par exemple, si $ n=35$ on trouve $ P(A^c)=0,186...$ Si 35 personnes sont réunies, la probabilité que deux d'entre elles au moins aient le même anniversaire est donc $ 0,813...$

Le prochain théorème sert en particulier à résoudre le problème plus difficile du calcul du nombre de fonctions surjectives.

Théorème 2.7 (Principe d'inclusion-exclusion) Soit $ E$ un ensemble fini et soit $ f$ et $ g$ des fonctions réelles définies sur $ \mathcal{P}(E)$ satisfaisant pour tout $ A\subset E:$

$\displaystyle f(A)=\sum_{B\subset A}g(B).$

Alors pour tout $ A\subset E:$

$\displaystyle g(A)=\sum_{B\subset A}(-1)^{\vert A\setminus B\vert}f(B).$

$  $

Démonstration Si $ C\subset A \subset E$ notons

$\displaystyle F(A,C)=\sum_{C\subset B\subset A}(-1)^{\vert A\setminus B\vert}.$

Si $ \vert A\setminus C\vert=n,$ puisque il y a $ C_n^k$ parties de $ A\setminus C$ de taille $ k$ on peut écrire $ F(A,C)=\sum_{k=0}^n(-1)^kC_n^k,$ qui est à son tour $ (1+(-1))^n$ à cause de la formule du binôme de Pascal $ (a+b)^n=\sum_{k=0}^na^{n-k}b^kC_n^k.$ Donc si $ n>0$, c'est-à-dire si $ C\neq A,$ on a $ F(A,C)=0.$ Si $ n=0,$ c'est-à-dire si $ C=A$ on a $ F(A,C)=1.$ Calculons alors le second membre de l'égalité à démontrer:

$\displaystyle \sum_{B\subset A}(-1)^{\vert A\setminus B\vert}f(B)=
\sum_{B\subset A}(-1)^{\vert A\setminus B\vert}\sum_{C\subset B}g(C)=$

$\displaystyle \sum_{C\subset B}g(C)\sum_{C\subset B\subset A}(-1)^{\vert A\setminus B\vert}=
\sum_{C\subset B}g(C)F(A,C)=g(A).$

La première égalité exploite le lien entre $ f$ et $ g,$ la seconde inverse les sommations par rapport aux indices de sommation $ B$ et $ C,$ la troisième résulte de la définition de $ F(A,C),$ la quatrième du calcul de $ F$ précédent et fournit le résultat voulu.

Voici deux applications.

Proposition Nombre de fonctions surjectives. Si $ \vert E\vert=n\geq\vert F\vert=p$, quel est le nombre de fonctions surjectives de $ E$ vers $ F$?

Pour répondre on applique le théorème précédent aux fonctions $ f$ et $ g$ définies sur $ \mathcal{P}(F)$ ainsi: si $ A\subset F$, $ f(A)=\vert A\vert^n$ est le nombre de fonctions de $ E$ vers $ F$ dont l'image est contenue dans $ A$ (on pourrait donc dire tout aussi bien les fonctions de $ E$ vers $ A$); et $ g(A)$ est le nombre de fonctions de $ E$ vers $ F$ dont l'image est exactement égale à $ A$ (on pourrait dire les fonctions de $ E$ vers $ A$ qui sont surjectives). On veut donc calculer $ g(F).$

Les hypothèses du théorème sont remplies, on a bien en effet $ f(A)=\sum_{B\subset A}g(B).$ Par conséquent

$\displaystyle g(F)=\sum_{B\subset F}(-1)^{\vert F\setminus B\vert}\vert B\vert^n=
\sum_{k=0}^pC^k_p(-1)^{p-k}k^n.$


Proposition Problème des rencontres. Si $ E$ a $ n$ éléments, combien y a-t-il de permutations $ \sigma$ de $ E$ sans point fixe, c'est-à-dire telles que pour tout $ j\in E$ on ait $ \sigma(j)\neq j?$.

On applique le théorème précédent aux fonctions $ f$ et $ g$ définies sur $ \mathcal{P}(E)$ ainsi: si $ A\subset E$ , $ f(A)=\vert A\vert!$ est le nombre de permutations de $ E$ telles que pour tout $ j\in A^c$ on ait $ \sigma(j)=j$, et $ g(A)$ est le nombre de permutations de $ E$ telles que pour tout $ j\in A^c$ on ait $ \sigma(j)=j$ et pour tout $ j\in A$ on ait $ \sigma(j)\neq j.$ On veut donc calculer $ g(E).$

Les hypothèses du théorème sont remplies, on a bien en effet $ f(A)=\sum_{B\subset A}g(B).$ Par conséquent

$\displaystyle g(E)=\sum_{B\subset E}(-1)^{\vert F\setminus B\vert}\vert B\vert!...
...=
n!\sum_{k=0}^n(-1)^{n-k}\frac{1}{(n-k)!}
=n!\sum_{k=0}^n(-1)^k\frac{1}{k!}.$

Si $ \Omega$ est l'ensemble des permutations de $ E$ et si il est muni de la probabilité équiprobable, la probabilité pour qu'une permutation aléatoire soit sans point fixe est donc

$\displaystyle \sum_{k=0}^n(-1)^k\frac{1}{k!},$

soit approximativement $ e^{-1}=0,367...$ si $ n>6.$

Exercices sur 2.2.

  1. Soit des entiers tels que $ 2\leq a\leq b\leq c.$ On tire de façon équiprobable une partie de taille $ a$ de l'ensemble des $ b+c$ entiers $ >0$. Calculer la probabilité pour que 0 d'entre eux soient $ >a;$ pour que 2 d'entre eux exactement soient $ >a$.
  2. Deux dés non pipés sont marqués sur leurs six faces 1,2,2,3,3,4 et 1,3,4,5,6,8 respectivement. On jette une fois ces deux dés et on note par $ A_k$ l'évènement "la somme des points $ i$ du premier dé et des points $ j$ du second est $ k''.$ Calculer pour $ k=2,3,\ldots, 12$ le nombre $ P(A_k).$
  3. 12 méchantes fées se penchent sur le berceau des quintuplés et attribuent chacune au hasard à un enfant un défaut. Quel est la probabilité qu'il y ait au moins un enfant parfait?
$  $


next up previous
suivant: Le schéma Succès-Echec. monter: epb précédent: L'espace est fini ou
Gérard_Letac_Les-Mathematiques.net
 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page