Principes de dénombrement
L'essentiel du cours (3 notions)
Représentations pour le dénombrement
Méthode : 1. Modéliser la situation : arbre pour choix successifs, tableau pour deux critères, diagramme pour intersections. 2. Compter toutes les issues sans oubli ni doublon.
Exemple : Un arbre à 3 niveaux ayant 2 branches par nœud donne $2^3 = 8$ issues au total.
Principes fondamentaux du dénombrement
Propriété : - Principe additif : Si $A$ et $B$ sont disjoints, $\text{Card}(A \cup B) = \text{Card}(A) + \text{Card}(B)$. - Principe multiplicatif : Pour des choix successifs, on multiplie le nombre de possibilités à chaque étape.
Exemple : Un code à 2 lettres suivi de 3 chiffres offre $26^2 \times 10^3 = 676\ 000$ combinaisons.
$k$-uplets, permutations et parties
Propriété : Pour un ensemble $E$ à $n$ éléments : • Nombre de $k$-uplets de $E$ : $n^k$ • Nombre de permutations de $E$ : $n! = n \times (n-1) \times \dots \times 1$ • Nombre de parties de $E$ : $2^n$
Exemple : Ranger 4 livres distincts sur une étagère : $4! = 24$ ordonnancements.
Lors d'un concours, $n$ candidats doivent passer une épreuve orale les uns après les autres. L'ordre de passage de l'ensemble des candidats est déterminé par un tirage au sort, de sorte que chaque candidat passe exactement une fois.
Les organisateurs constatent qu'il existe exactement $720$ ordres de passage distincts possibles.
Saisir la valeur du nombre de candidats $n$.
En bio-informatique, on modélise des séquences biologiques constituées :
- d'un premier élément choisi parmi $5$ types d'acides aminés distincts ;
- suivi d'une chaîne de $n$ bases azotées choisies parmi $4$ bases possibles (A, C, G, T), la répétition des bases étant autorisée.
Un chercheur constate qu'il existe au total $1280$ séquences distinctes répondant à cette structure.
En calculant d'abord le nombre de chaînes de bases azotées possibles, déterminer la valeur de $n$.
Saisir la valeur de $n$.
Une association souhaite former un bureau composé de trois personnes occupant trois fonctions distinctes : un président, un secrétaire et un trésorier.
- Le président est obligatoirement choisi parmi 4 membres fondateurs de l'association.
- Le secrétaire et le trésorier sont choisis parmi un groupe de $n$ adhérents de l'association, sachant qu'aucun membre fondateur n'est adhérent et qu'une même personne ne peut pas cumuler deux fonctions.
On sait qu'il existe exactement $840$ possibilités différentes pour constituer ce bureau.
Saisir la valeur de $n$.
Un serveur informatique sécurisé génère des clés d'accès constituées de deux parties successives :
- La première partie est formée de $3$ chiffres distincts choisis parmi les $10$ chiffres de $0$ à $9$.
- La deuxième partie est formée de $2$ lettres distinctes choisies parmi une liste de $n$ lettres majuscules autorisées (avec $n \ge 2$).
On sait que ce système permet de former exactement $64\,800$ clés d'accès différentes.
Saisir la valeur du nombre $n$ de lettres autorisées.
Soit $n$ un entier naturel non nul et $E$ un ensemble fini à $n$ éléments.
On s'intéresse d'une part au nombre de $4$-uplets d'éléments de $E$, et d'autre part au nombre de permutations de $E$.
Un élève émet la conjecture suivante : « Pour tout entier naturel $n \ge 1$, le nombre de $4$-uplets d'éléments d'un ensemble à $n$ éléments est supérieur ou égal au nombre de permutations de cet ensemble. »
Cette conjecture est fausse. On cherche à déterminer le plus petit entier naturel $n \ge 1$ qui la met en défaut.
Saisir le plus petit entier naturel $n \ge 1$ constituant un contre-exemple.