Dénombrement
Définition :
Dénombrer un ensemble fini, c'est calculer son cardinal.
Méthode :
S'il existe une bijection entre deux ensembles finis, ils ont le même cardinal.
Donc, on établit une bijection entre l'ensemble étudié et certains modèles connus : listes, parties, applications, tirages.
Les raisonnements utilisés pour dénombrer des ensembles plus complexes reposent le plus souvent sur deux principes que l'on peut éventuellement combiner.
Fondamental :
Principe "additif" :
On réalise une partition de l'ensemble à dénombrer, on calcule les cardinaux de chaque partie et on additionne pour calculer le cardinal de l'ensemble.
En effet, si
est une partition de
:
.
Exemple :
En construisant un quadrillage
|  |
Fondamental :
Principe "multiplicatif" :
On décompose le problème en
étapes telles que, pour tout
, la
ème étape admette un nombre
d'issues indépendant des résultats des autres étapes.
Alors, on peut construire un arbre et le nombre total d'issues du problème est
.
Exemple :
Un anagramme de MAT est un mot de trois lettres formé avec M, A et T.
Combien peut-on former d'anagrammes de MAT ?
Bien sûr, lorsque le nombre d'issues devient trop grand, on imagine l'arbre sans le dessiner !
Attention :
Il faut que le nombre d'issues à chaque étape soit indépendant des résultats des autres étapes.
Par exemple, on ne pourrait pas appliquer ce principe aux anagrammes de ETE. En effet :
Pour la première place, on choisit une lettre parmi E et T : il y a 2 issues possibles.
Mais pour la deuxième place, si l'on a choisi T, il y a une seule issue E, alors que si l'on a choisi E, il reste deux issues T et E.
