Considérons le cas particulier de
la Proposition 2.3 où a un nombre fini
d'éléments et où tous les
sont égaux (et donc égaux à ) Dans ce cas, si
on a
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 leur produit cartésien, c'est-à-dire l'ensemble des couples
tels que et On note par l'ensemble des
fonctions définies sur et à valeurs dans Si est fini et est
de taille et si
est un entier avec
on note par
l'ensemble
des parties de de taille
Théorème 2.5
Si et sont des ensembles finis, alors
Plus généralement, si
sont des ensembles finis:
Ensuite
Enfin, si
le nombre de fonctions
injectives de vers est
En particulier, le nombre de fonctions bijectives de vers , appelées
permutations de , est égal à
Si est fini et est de taille et si est un
entier avec
alors
Démonstration
La première formule est évidente : si
et
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
il y a alors bijection entre et
( fois). D'où
Quant au nombre de
fonctions injectives, la formule donnée se justifie facilement: on identifie
à
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 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
on a
Démonstration
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 à
sans perte de généralité. Soit aussi l'ensemble des
premiers entiers. On partage alors les éléments de
en deux
catégories:
Catégorie 1: ceux qui ne contiennent pas
Catégorie 2: ceux qui contiennent
La catégorie 1 est égale à
et a donc éléments
par l'hypothèse
de récurrence. La catégorie 2 est en bijection avec
( enlever à un membre de la catégorie 2 pour
avoir
un élément de
et donc par l'hypothèse
de récurrence
a éléments. La formule de Pascal montre alors que
a é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
où est l'ensemble des personnes et où est l'ensemble des
jours de l'année: on observe donc la fonction
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
Si n'est pas grand, une évaluation approximative de cette somme se fait
en remplaçant par et en utilisant la somme d'une progression
arithmétique étudiée en Terminale
qui conduit à l'approximation
Pour voir
par exemple pour quel on a
on prend
Pour un calcul plus sérieux, on peut utiliser
l'encadrement pour
La majoration de droite se déduit du développement en série entière,
celle de gauche se montre en étudiant la fonction
On a aussi besoin de la somme des premiers carrés:
qui s'établit par récurrence. Si
,
alors
D'où l'encadrement :
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
satisfaisant
pour tout
Alors pour tout
Démonstration Si
notons
Si
puisque il y a parties
de
de taille on peut écrire
qui est à son tour
à cause de la formule du binôme
de Pascal Donc si , c'est-à-dire
si on a Si c'est-à-dire si on a
Calculons alors le second membre de l'égalité à démontrer:
La première égalité exploite le lien entre et la seconde inverse
les sommations par rapport aux indices de sommation et
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
, 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
ainsi:
si
,
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
Par conséquent
Proposition Problème des rencontres. Si a éléments, combien y a-t-il de
permutations de sans point fixe, c'est-à-dire telles que
pour tout on ait
.
On applique le théorème précédent aux fonctions et
définies sur
ainsi:
si
, est le nombre de permutations de
telles que pour tout on ait
, et est
le nombre de permutations de
telles que pour tout on ait
et pour tout
on ait
On veut donc calculer
Les hypothèses du théorème sont remplies, on a bien en effet
Par conséquent
Si 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
soit approximativement
si
Exercices sur 2.2.
Soit des entiers tels que
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
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?