v1 · padrão canônico

Leçon 36 — Principe Fondamental du Dénombrement

PFD : si une tâche a k étapes indépendantes avec n₁, n₂, …, nₖ options chacune, le nombre total de séquences possibles est le produit. Principe additif, factorielle et applications.

Used in: 1ère année du Lycée (15 ans) · Équivalent Math A japonais · Équivalent Klasse 10 allemande

N = n_1 \times n_2 \times \cdots \times n_k

Choose your door

Rigorous notation, full derivation, hypotheses

Énoncé rigoureux et principe additif

Principe Multiplicatif (PFD)

"Si vous avez $m$ façons de faire une chose et $n$ façons de faire une autre, alors il y a $m \cdot n$ façons de faire les deux choses." — OpenStax College Algebra 2e, §11.5

La justification formelle : l'ensemble de toutes les séquences est le produit cartésien $E_1 \times E_2 \times \cdots \times E_k$ , et $|A \times B| = |A| \cdot |B|$ (prouvé par induction). Le PFD est exactement ce théorème.

Principe Additif

Connecteur entre étapes	Opération
"ET" — étapes séquentielles indépendantes	multiplication
"OU" — alternatives mutuellement exclusives	addition

"Le Principe de l'Addition affirme que s'il y a $m$ résultats dans l'événement $A$ et $n$ résultats dans l'événement $B$ , et $A$ et $B$ sont mutuellement exclusifs, alors il y a $m + n$ résultats dans l'événement $A$ ou $B$ ." — OpenStax College Algebra 2e, §11.5

Factorielle

Arbre de possibilités

Un arbre de décision avec $k$ niveaux représente graphiquement le PFD : chaque nœud au niveau $i$ génère $n_i$ fils. Le nombre total de feuilles est $n_1 \times n_2 \times \cdots \times n_k$ .

Arbre avec 3 étapes au 1er niveau et 2 au 2e niveau : 6 feuilles = 3 × 2. Le PFD en action.

Fonctions et sous-ensembles via PFD

Nombre total de fonctions $f: A \to B$ avec $|A| = m,\, |B| = n$ : $n^m$ (chaque élément de $A$ a $n$ images indépendantes).
Nombre total de sous-ensembles de $S$ avec $|S| = n$ : $2^n$ (chaque élément est inclus ou exclu).
Fonctions injectives $f: A \to B$ ( $m \leq n$ ) : $n \cdot (n-1) \cdots (n-m+1) = \frac{n!}{(n-m)!}$ — base de l'arrangement (Leçon 37).

Exemples résolus

Example— 1· PFD avec deux étapes indépendantes

Problème : Un restaurant offre 4 entrées et 6 plats principaux. Un client choisit exactement une entrée et un plat principal. De combien de façons distinctes peut-il monter sa commande ?

Stratégie : Le choix de l'entrée et le choix du plat sont indépendants — n'importe quelle entrée se combine avec n'importe quel plat. Deux étapes séquentielles : appliquez le PFD.

Résolution :

Étape 1 — Entrée : 4 options.
Étape 2 — Plat principal : 6 options.
PFD : $4 \times 6 = 24$ commandes distinctes.

Vérification : Un arbre de décision : 4 racines (entrées), chacune avec 6 feuilles (plats). Nombre total de feuilles = $4 \times 6 = 24$ . Cohérent.

Source. OpenStax College Algebra 2e, §11.5 — licence CC-BY 4.0.

Example— 2· PFD avec trois étapes — plaque de véhicule

Problème : Une plaque de véhicule selon l'ancien modèle (avant le Mercosul) était composée de 3 lettres suivies de 4 chiffres numériques. En admettant 26 lettres et chiffres 0-9 avec répétition autorisée, combien de plaques distinctes étaient possibles ?

Stratégie : 7 étapes indépendantes — 3 de choix de lettre et 4 de choix de chiffre. Appliquez le PFD.

Résolution :

Lettres : chacune des 3 positions a 26 options. Sous-total : $26^3 = 17\,576$ .
Chiffres : chacune des 4 positions a 10 options. Sous-total : $10^4 = 10\,000$ .
PFD : $26^3 \times 10^4 = 17\,576 \times 10\,000 = 175\,760\,000$ .

Vérification : Ordre de grandeur : $\approx 1{,}8 \times 10^8$ . Le Brésil avait en 2019 environ 100 millions de véhicules — l'espace de $1{,}8 \times 10^8$ plaques était suffisant. Cohérent avec le fait historique que le système a fonctionné pendant des décennies.

Source. OpenStax College Algebra 2e, §11.5 — licence CC-BY 4.0.

Example— 3· Principe additif — alternatives mutuellement exclusives

Problème : Un étudiant veut aller de l'école à la maison en utilisant les transports en commun. Il peut prendre l'un des 3 bus disponibles OU l'une des 2 lignes de métro qui font le trajet. De combien de façons peut-il faire le trajet ?

Stratégie : Bus et métro sont des moyens alternatifs (exclusifs l'un l'autre — il prend l'un OU l'autre, pas les deux). Appliquez le principe additif.

Résolution :

Les deux alternatives sont mutuellement exclusives (l'étudiant utilise exactement un moyen de transport) :

$N = 3 + 2 = 5 \text{ façons}$

Attention : si le problème était "prendre un bus ET ensuite un métro" (deux étapes en séquence), le total serait $3 \times 2 = 6$ . Le connecteur "OU" (alternative) génère une somme ; le connecteur "ET" (séquence) génère un produit.

Source. Book of Proof, 3rd ed., §3.1 — Richard Hammack, licence CC-BY-ND.

Example— 5· Mot de passe avec restrictions mixtes — sans et avec restriction à la 1ère position

Problème : Un système exige des mots de passe de 6 caractères composés de lettres minuscules (a-z, 26 options) et chiffres (0-9, 10 options), avec répétition autorisée. Combien de mots de passe sont possibles si : (a) pas de restriction supplémentaire ; (b) le mot de passe doit commencer par une lettre ?

Stratégie : Appliquez le PFD directement en (a). Pour (b), fixez la restriction au premier caractère avant de multiplier.

Résolution :

(a) Sans restriction : chacune des 6 positions accepte l'un des $26 + 10 = 36$ caractères alphanuméricos.

$N_a = 36^6 = 2\,176\,782\,336 \approx 2{,}2 \times 10^9$

(b) Première position doit être lettre : la 1ère position a 26 options (uniquement les lettres) ; les autres 5 positions conservent 36 options chacune.

$N_b = 26 \times 36^5 = 26 \times 60\,466\,176 = 1\,572\,120\,576 \approx 1{,}6 \times 10^9$

Vérification : $N_b / N_a = 26/36 \approx 0{,}72$ — les mots de passe commençant par une lettre représentent 72% du total, cohérent avec $26/36$ des 36 options étant des lettres.

Source. OpenStax College Algebra 2e, §11.5 — licence CC-BY 4.0.

Exercise list

40 exercises · 10 with worked solution (25%)

Application 27Understanding 6Modeling 6Challenge 1

Ex. 36.1Application
Une personne a 3 chemises et 4 pantalons. De combien de façons distinctes peut-elle choisir une chemise et un pantalon pour s'habiller ?
Solve online
Ex. 36.2ApplicationAnswer key
Un menu a 5 plats principaux, 3 accompagnements et 4 desserts. Combien de repas distincts (1 plat + 1 accompagnement + 1 dessert) sont possibles ?
Solve online
Ex. 36.3Application
Combien de mots de passe de 3 chiffres numériques sont possibles, avec répétition autorisée ?
Solve online
Ex. 36.4Application
Combien de mots de passe de 3 chiffres numériques sont possibles si les chiffres ne peuvent pas se répéter ?
Solve online
Ex. 36.5Application
Combien de nombres entiers à 4 chiffres ont le premier chiffre différent de zéro ?
Solve online
Ex. 36.6ApplicationAnswer key
Une plaque de véhicule selon l'ancien modèle a 3 lettres (A-Z) suivies de 4 chiffres (0-9), avec répétition autorisée dans les deux. Combien de plaques distinctes sont possibles ?
Solve online
Ex. 36.7Application
Une association a 8 membres. Combien d'équipes distinctes de président, secrétaire et trésorier peuvent être formées (une personne ne peut pas occuper deux postes) ?
Solve online
Ex. 36.8Application
Trois pièces sont lancées simultanément. Combien de résultats distincts sont possibles ?
Solve online
Ex. 36.9Application
Deux dés ordinaires (faces 1 à 6) sont lancés. Combien de paires ordonnées $(d_1, d_2)$ de résultats sont possibles ?
Solve online
Ex. 36.10Application
De combien de façons 5 livres distincts peuvent-ils être disposés sur une étagère ?
Solve online
Ex. 36.11ApplicationAnswer key
Combien d'anagrammes (réarrangements de lettres) le mot AMOR a-t-il, en utilisant les 4 lettres ?
Solve online
Ex. 36.12Application
Combien de sous-ensembles l'ensemble $\{1, 2, 3, 4, 5\}$ a-t-il (y compris l'ensemble vide et l'ensemble lui-même) ?
Solve online
Ex. 36.13Application
Trois prix distincts (1ère, 2e et 3e place) seront distribués entre 5 candidats. Chaque candidat peut recevoir au maximum un prix. Combien de distributions distinctes sont possibles ?
Solve online
Ex. 36.14Application
Combien de chaînes binaires (séquences de 0s et 1s) de longueur 10 existent ?
Solve online
Ex. 36.15ApplicationAnswer key
Combien de fonctions $f: \{1, 2, 3\} \to \{a, b\}$ existent ?
Solve online
Ex. 36.16Application
Un nombre à 5 chiffres est palindrome quand lu dans les deux sens il est égal (ex. : 12 321). Combien de nombres palindromes à 5 chiffres existent ?
Solve online
Ex. 36.17Application
Combien de séquences d'ADN de longueur 10 sont possibles ? (Utilisez les bases A, T, C, G — 4 bases.)
Solve online
Ex. 36.18Application
Combien de nombres à 4 chiffres distincts (sans répétition) ont le premier chiffre différent de zéro ?
Solve online
Ex. 36.19ApplicationAnswer key
De combien de façons peuvent être choisis un représentant et un vice-représentant distincts dans une classe de 6 élèves (l'ordre importe : représentant $\neq$ vice) ?
Solve online
Ex. 36.20Application
Un test vrai ou faux a 4 questions. Combien de modèles de réponse distincts sont possibles ?
Solve online
Ex. 36.21ApplicationAnswer key
Combien de nombres entiers à 3 chiffres ont le chiffre central pair (0, 2, 4, 6 ou 8) ?
Solve online
Ex. 36.22Application
Combien de mots de passe de 4 chiffres commencent par le chiffre 1 et se terminent par le chiffre 9 ?
Solve online
Ex. 36.23Application
Combien de codes PIN de 4 chiffres ont tous les chiffres distincts (sans répétition) ?
Solve online
Ex. 36.24ApplicationAnswer key
Un étudiant peut aller de l'école à la maison en bus (3 lignes disponibles) ou en métro (2 lignes). De combien de façons distinctes peut-il faire le trajet ?
Solve online
Ex. 36.25Understanding
Si $A$ et $B$ sont des ensembles avec intersection non-vide, quelle est la formule correcte pour $|A \cup B|$ ?
Solve online
Ex. 36.26Application
En compétition, 6 athlètes disputent les médailles d'or, d'argent et de bronze (3 positions distinctes). De combien de façons le podium peut-il être formé ?
Solve online
Ex. 36.27Application
Combien d'anagrammes (réarrangements utilisant toutes les lettres) une mot de 6 lettres, toutes distinctes, a-t-il ?
Solve online
Ex. 36.28ApplicationAnswer key
Deux dés ordinaires (faces 1 à 6) sont lancés. Combien de paires ordonnées $(d_1, d_2)$ résultent en somme paire ?
Solve online
Ex. 36.29UnderstandingAnswer key
Un mot de passe a 6 caractères alphanumériques (a-z minuscules ou 0-9), avec répétition autorisée. Écrivez une expression pour le nombre de mots de passe qui contiennent au moins un chiffre numérique.
Solve online
Ex. 36.30Understanding
Combien de chemins existent dans le plan cartésien de $(0, 0)$ à $(3, 2)$ , se déplaçant uniquement vers la droite $(+1, 0)$ ou vers le haut $(0, +1)$ à chaque pas ?
Solve online
Ex. 36.31Understanding
Combien de nombres entiers à 3 chiffres (entre 100 et 999) ne contiennent pas le chiffre 0 ?
Solve online
Ex. 36.32Understanding
Dans un jeu de 52 cartes (26 rouges, 26 noires ; 4 rois au total), combien de cartes sont rouges ou rois ? Quelle formule s'applique et pourquoi ?
Solve online
Ex. 36.33Modeling
L'algorithme de chiffrement AES-128 utilise des clés de 128 bits (chaque bit est 0 ou 1). Combien de clés distinctes existent ? Justifiez en utilisant le PFD.
Solve online
Ex. 36.34Modeling
Un guichet automatique exige un code PIN de 4 chiffres. Combien de codes PIN distincts commencent par le chiffre 1 ?
Solve online
Ex. 36.35Modeling
Un restaurant propose 8 plats : 3 avec viande et 5 végétariens. Un client végétarien va choisir exactement 1 plat. Combien d'options a-t-il ?
Solve online
Ex. 36.36Modeling
Une adresse réseau IPv4 est représentée par 32 bits (chaque bit est 0 ou 1). Combien d'adresses IPv4 distinctes existent ?
Solve online
Ex. 36.37Modeling
5 livres distincts seront disposés sur une étagère. 2 de ces livres doivent rester toujours ensemble (côte à côte). De combien de façons la disposition peut-elle être faite ?
Solve online
Ex. 36.38Modeling
5 livres distincts seront disposés sur une étagère. De combien de façons les livres A et B restent-ils séparés (jamais côte à côte) ?
Solve online
Ex. 36.39UnderstandingAnswer key
Soient $A$ avec $m$ éléments et $B$ avec $n$ éléments, avec $m \leq n$ . Déterminez le nombre de fonctions injectives $f: A \to B$ . Justifiez par le PFD.
Solve online
Ex. 36.40Challenge
De 5 livres distincts (A, B, C, D, E) disposés sur une étagère, combien de dispositions existent où A et B restent séparés ET C et D restent séparés ? (Défi : appliquez l'inclusion-exclusion deux fois.)
Solve online

Sources de cette leçon

OpenStax College Algebra 2e — Jay Abramson et al. · OpenStax · 2022 · EN · CC-BY 4.0 · §11.5 (Counting Principles). Source primaire.
Book of Proof, 3rd ed. — Richard Hammack · 2018, 3rd ed. · EN · CC-BY-ND · Cap. 3 (Counting), §3.1 (Multiplication Principle), §3.2 (Lists and Functions). Source primaire.
Wikilivros — Matemática elementar / Combinatória — collaboratif · PT-BR · CC-BY-SA · PFC, factorielle, applications brésiliennes.