A lire

Deug/Prépa

Licence

Agrégation
A télécharger

Télécharger

79 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.

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 sont égaux (et donc égaux à ) 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 et sont des ensembles, on note par $E\times F$ leur produit cartésien, c'est-à-dire l'ensemble des couples tels que $x\in E$ et $y\in F.$ On note par l'ensemble des fonctions définies sur et à valeurs dans Si est fini et est de taille $n=\vert E\vert$ et si est un entier avec $0\leq k\leq n$ on note par $\mathcal{P}_k(E)$ l'ensemble des parties de de taille

Théorème 2.5

Si et 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 vers est $p(p-1)(p-2)\cdots(p-n+1).$ En particulier, le nombre de fonctions bijectives de vers , appelées permutations de , est égal à
Si est fini et est de taille $n=\vert E\vert$ et si 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

La première formule est évidente : si $e_1,\ldots,e_n$ et $f_1, \ldots,f_p$ sont les éléments de et , le nombre de couples est L'extension à facteurs est immédiate également. Cette extension est ensuite appliquée au cas particulier où tous les ensembles sont égaux au même ensemble Si $\vert E\vert=n,$ il y a alors bijection entre et $F\times \cdots\times F$ ( 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 à $(1,2,\ldots,n),$ et l'image de 1 peut occuper positions, l'image de 2 peut occuper une des positions restantes, l'image de 3 une des positions restantes, etc. Faire pour le nombre de permutations de (on rappelle que si $\vert E\vert=\vert F\vert$ avec fini, alors une fonction de vers est injective si et seulement si elle est surjective).
Rappelons pour cette partie la formule de Pascal:

Proposition 2.6 Si 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 , puis on fixe et on montre 2) par récurrence sur C'est trivial pour Supposons enfin 2) vrai pour et supposons que ait éléments, qu'on prend égaux à $1,2,\ldots,n+1$ sans perte de généralité. Soit aussi l'ensemble des 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

Catégorie 2: ceux qui contiennent

La catégorie 1 est égale à $\mathcal{P}_k(E')$ et a donc éléments par l'hypothèse de récurrence. La catégorie 2 est en bijection avec $\mathcal{P}_{k-1}(E')$ ( enlever à 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. 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$ où est l'ensemble des personnes et où est l'ensemble des 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 de l'évènement "deux personnes au moins ont le même anniversaire", car c'est la probabilité que la fonction 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}).$

n'est pas grand, une évaluation approximative de cette somme se fait en remplaçant $\log(1-x)$ par

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

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

$\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 on trouve Si 35 personnes sont réunies, la probabilité que deux d'entre elles au moins aient le même anniversaire est donc

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 un ensemble fini et soit et 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

parties de $A\setminus C$ de taille

on peut écrire $F(A,C)=\sum_{k=0}^n(-1)^kC_n^k,$ qui est à son tour

à cause de la formule du binôme de Pascal

$(a+b)^n=\sum_{k=0}^na^{n-k}b^kC_n^k.$ Donc si

, c'est-à-dire si $C\neq A,$ on a

c'est-à-dire si

on a

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

la seconde inverse les sommations par rapport aux indices de sommation

la troisième résulte de la définition de

la quatrième du calcul de

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 vers ?

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

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 a éléments, combien y a-t-il de permutations $\sigma$ de 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 et définies sur $\mathcal{P}(E)$ ainsi: si $A\subset E$ , $f(A)=\vert A\vert!$ est le nombre de permutations de telles que pour tout $j\in A^c$ on ait $\sigma(j)=j$ , et est le nombre de permutations de 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

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 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

Exercices sur 2.2.

Soit des entiers tels que $2\leq a\leq b\leq c.$ On tire de façon équiprobable une partie de taille de l'ensemble des entiers . Calculer la probabilité pour que 0 d'entre eux soient pour que 2 d'entre eux exactement soient .
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 l'évènement "la somme des points du premier dé et des points du second est Calculer pour $k=2,3,\ldots, 12$ le nombre
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?