Combien de codes à quatre chiffres existe-t-il ?
Le dénombrement est l’art de compter les cas possibles sans les écrire un par un. Il sert à mesurer la solidité d’un mot de passe et à savoir combien de cas un programme devrait tester.
Un code de carte bancaire a quatre chiffres. Un voleur qui le devine au hasard a une chance sur 10 000. D’où vient ce nombre ? Le même raisonnement compte aussi les équipes et les classements.
À la fin de cette leçon
Remarque
Je peux compter des choix et des regroupements avec la règle du produit, les arrangements et les combinaisons.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Règle du produit | on multiplie le nombre de choix de chaque étape | |
| Factorielle | le produit des entiers de 1 jusqu’à n | 4 ! = 24 |
| Permutation | une façon de ranger tous les éléments dans un ordre | |
| Arrangement | k éléments choisis parmi n, dans un ordre qui compte | |
| Combinaison | k éléments choisis parmi n, sans tenir compte de l’ordre |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
La règle du produit multiplie les choix
Un code de quatre chiffres se fait en quatre étapes. À chaque étape, on a 10 choix, et les étapes sont indépendantes.
La règle du produit dit : on multiplie le nombre de choix de chaque étape. Ici 10 fois 10 fois 10 fois 10 donne 10 000 codes.
Exemple travaillé : trois codes à compter
| Code | Étapes et choix | Produit |
|---|---|---|
| Code de carte, 4 chiffres | 10, 10, 10, 10 | 10 000 |
| Mot de passe, 3 lettres minuscules | 26, 26, 26 | 17 576 |
| Plaque simplifiée, 2 lettres, 3 chiffres, 2 lettres | 26, 26, 10, 10, 10, 26, 26 | 456 976 000 |
| Mot de passe, 8 caractères parmi 36 | 36 répété 8 fois | 2 821 109 907 456 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Code de carte et mot de passe
python3 -c "print(10 ** 4, 26 ** 3)"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
La plaque simplifiée
python3 -c "print(26 ** 4 * 10 ** 3)"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Une factorielle compte les façons de ranger
Quatre étudiants se rangent en file. Pour la première place, 4 choix. Pour la deuxième, il en reste 3, puis 2, puis 1.
Le produit 4 fois 3 fois 2 fois 1 vaut 24. On l’écrit 4 ! et on le lit « factorielle de 4 ». Ces rangements sont des permutations. Par convention, 0 ! vaut 1.
Exemple travaillé : président, secrétaire, trésorier
| Poste | Choix restants parmi 5 candidats | Total jusque-là |
|---|---|---|
| Président | 5 | 5 |
| Secrétaire | 4 | 20 |
| Trésorier | 3 | 60 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Un arrangement garde l’ordre des choix
Le tableau compte 60 façons de nommer trois postes différents parmi cinq candidats. L’ordre compte : Lina présidente et Hugo secrétaire n’est pas Hugo président et Lina secrétaire.
C’est un arrangement de 3 éléments parmi 5. On arrête la factorielle après trois facteurs.
Factorielle et arrangements
python3 -c "import math; print(math.factorial(5), math.perm(5, 3))"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Une combinaison oublie l’ordre
Choisir trois personnes pour une équipe, sans poste, ne tient pas compte de l’ordre. L’équipe Lina, Hugo, Jade est la même que Jade, Lina, Hugo.
Chaque équipe apparaît 3 ! = 6 fois parmi les 60 arrangements. On divise donc 60 par 6 et on obtient 10 équipes. C’est une combinaison.
Arrangements et combinaisons au calcul
# Factorielle, arrangements et combinaisons de 5 éléments pris 3 par 3.
def factorielle(n):
resultat = 1
for facteur in range(2, n + 1):
resultat = resultat * facteur
return resultat
n = 5
k = 3
arrangements = factorielle(n) // factorielle(n - k)
combinaisons = arrangements // factorielle(k)
print("Arrangements :", arrangements)
print("Combinaisons :", combinaisons)
# Changez n en 6 puis relancez : prévoyez d’abord les deux nombres.
Les trois nombres de la leçon
python3 -c "import math; print(math.factorial(5), math.perm(5, 3), math.comb(5, 3))"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Erreur fréquente
Attention
Beaucoup choisissent une formule sans se demander si l’ordre compte. Un loto tire 5 numéros parmi 49 sans ordre : c’est une combinaison. Un podium de trois places a un ordre : c’est un arrangement. Posez toujours la question de l’ordre d’abord.
Pour aller plus loin
Le loto français tire 5 numéros parmi 49, puis un numéro chance parmi 10. Écrivez le nombre de grilles possibles.
Indice : combinaison pour les 5 numéros, puis règle du produit avec le numéro chance. Vérifiez ensuite avec math.comb(49, 5) * 10 dans le terminal.