Dénombrement

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 , combien dessine-t-on de carrés ?

Solution

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 ?

Solution

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.

PrécédentPrécédentSuivantSuivant
AccueilAccueilImprimerImprimer Paternité - Pas d'Utilisation Commerciale - Partage des Conditions Initiales à l'IdentiqueRéalisé avec Scenari (nouvelle fenêtre)