FICHE DE RÉVISION – Combinatoire et dénombrement
(Niveau : Terminale)
Combinatoire et Dénombrement
L’art de compter : principes fondamentaux, permutations, arrangements et combinaisons pour dénombrer efficacement.
Partie 1 : Principes Fondamentaux du Dénombrement
Comment compter le nombre d’éléments dans un ensemble sans les lister un par un ?1. Notions de Base : k-uplets et Produit Cartésien
- Un k-uplet (ou k-liste) est une liste ordonnée de \(k\) éléments. L’ordre compte et les répétitions sont possibles. Notation : \((x_1, x_2, …, x_k)\). (Un 2-uplet est un couple, un 3-uplet est un triplet).
- Le Produit Cartésien \(A \times B\) est l’ensemble de tous les couples \((a, b)\) avec \(a \in A\) et \(b \in B\).
- Si \(A\) a \(n\) éléments et \(B\) a \(p\) éléments, alors \(A \times B\) a \(n \times p\) éléments.
- Le produit cartésien de \(k\) ensembles \(A_1 \times … \times A_k\) est l’ensemble des k-uplets \((a_1, …, a_k)\) où \(a_i \in A_i\).
- \(A^k = A \times A \times … \times A\) (k fois) est l’ensemble des k-uplets d’éléments de A.
Si \(A = \{1, 2\}\), \(B = \{a, b, c\}\). \(A \times B = \{(1,a), (1,b), (1,c), (2,a), (2,b), (2,c)\}\). Il y a \(2 \times 3 = 6\) éléments. \(A^3 = A \times A \times A = \{(1,1,1), (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1), (2,2,2)\}\). Il y a \(2^3 = 8\) éléments.
2. Principe Additif
Si des ensembles \(A_1, A_2, …, A_k\) sont deux à deux disjoints (ils n’ont aucun élément en commun), alors le nombre d’éléments dans leur réunion est la somme de leurs nombres d’éléments :
$$ \text{Card}(A_1 \cup A_2 \cup … \cup A_k) = \text{Card}(A_1) + \text{Card}(A_2) + … + \text{Card}(A_k) $$
(Card(A) désigne le cardinal, c’est-à-dire le nombre d’éléments de A).
Dans une classe, il y a 15 filles et 17 garçons. L’ensemble Filles et l’ensemble Garçons sont disjoints. Nombre total d’élèves = Card(Filles \(\cup\) Garçons) = Card(Filles) + Card(Garçons) = 15 + 17 = 32.
3. Principe Multiplicatif
Si une situation se déroule en \(k\) étapes successives, et qu’il y a \(n_1\) choix pour la première étape, \(n_2\) choix pour la deuxième (quel que soit le 1er choix), …, \(n_k\) choix pour la k-ième (quels que soient les choix précédents), alors le nombre total de résultats possibles est le produit :
$$ N = n_1 \times n_2 \times … \times n_k $$
C’est directement lié au cardinal du produit cartésien.
Cas particulier : Nombre de k-uplets (k-listes) : Le nombre de k-uplets d’un ensemble \(A\) à \(n\) éléments est \(n^k\) (car il y a \(n\) choix pour chaque position dans le k-uplet).
$$ \text{Card}(A^k) = n^k $$
Combien de menus (entrée, plat, dessert) peut-on composer avec 3 entrées, 4 plats et 2 desserts ? Nombre de choix = \(3 \times 4 \times 2 = 24\) menus possibles. Combien de codes à 4 chiffres peut-on former ? C’est un 4-uplet d’éléments de l’ensemble \{0, 1, …, 9\} (qui a \(n=10\) éléments). Nombre de codes = \(10^4 = 10000\).
Le principe multiplicatif est PARTOUT ! Représente la situation avec un arbre (même mentalement) ou des cases à remplir. Si les choix à chaque étape sont indépendants, tu multiplies le nombre de possibilités à chaque étape. C’est la base de beaucoup de dénombrements.
Partie 2 : Arrangements et Permutations (Ordre Important)
1. k-uplets d’Éléments Distincts (Arrangements sans répétition)
On cherche à former une liste ordonnée de \(k\) éléments distincts (sans répétition) choisis parmi \(n\) éléments (\(k \le n\)).
Nombre de choix :
– \(n\) choix pour le 1er élément.
– \(n-1\) choix pour le 2ème (car on ne peut pas reprendre le 1er).
– \(n-2\) choix pour le 3ème…
– \(n-k+1\) choix pour le k-ième.
Le nombre de k-uplets d’éléments distincts (ou arrangements de \(k\) parmi \(n\)), noté \(A_n^k\), est :
$$ A_n^k = n \times (n-1) \times … \times (n-k+1) $$
Tiercé dans une course de 8 chevaux : On choisit 3 chevaux distincts dans un ordre précis (1er, 2ème, 3ème). C’est un 3-uplet d’éléments distincts parmi 8. Nombre de tiercés possibles = \(A_8^3 = 8 \times (8-1) \times (8-3+1) = 8 \times 7 \times 6 = 336\).
2. Factorielle et Permutations
La factorielle d’un entier \(n \ge 1\), notée \(n!\), est le produit de tous les entiers de 1 à \(n\).
$$ n! = n \times (n-1) \times … \times 2 \times 1 $$
Par convention, \(0! = 1\).
Une permutation d’un ensemble à \(n\) éléments est un arrangement ordonné de tous ses éléments. C’est un n-uplet d’éléments distincts.
Le nombre de permutations d’un ensemble à \(n\) éléments est :
$$ A_n^n = n \times (n-1) \times … \times 1 = n! $$
On peut réécrire le nombre d’arrangements avec les factorielles :
$$ A_n^k = \frac{n!}{(n-k)!} $$
Combien d’anagrammes du mot « MATHS » (5 lettres distinctes) ? C’est le nombre de permutations d’un ensemble à 5 éléments. Nombre = \(5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\). Calcul de \(A_8^3\) avec factorielle : \(A_8^3 = \frac{8!}{(8-3)!} = \frac{8!}{5!} = \frac{8 \times 7 \times 6 \times 5!}{5!} = 8 \times 7 \times 6 = 336\).
Partie 3 : Combinaisons (Ordre non Important)
Ici, on choisit un groupe d’éléments sans tenir compte de l’ordre.
Une combinaison de \(k\) éléments parmi \(n\) (\(0 \le k \le n\)) est un sous-ensemble (une partie) de \(k\) éléments choisis dans un ensemble à \(n\) éléments. L’ordre ne compte pas.
Le nombre de combinaisons de \(k\) parmi \(n\), noté \(\binom{n}{k}\) (lire « k parmi n ») ou \(C_n^k\), est donné par la formule :
$$ \binom{n}{k} = \frac{A_n^k}{k!} = \frac{n!}{k!(n-k)!} $$
(C’est le nombre d’arrangements divisé par le nombre de façons d’ordonner les \(k\) éléments choisis).
Cas particuliers :
\(\binom{n}{0} = 1\) (Il y a 1 façon de choisir 0 élément : l’ensemble vide).
\(\binom{n}{1} = n\) (Il y a n façons de choisir 1 élément).
\(\binom{n}{2} = \frac{n(n-1)}{2}\) (Nombre de paires).
\(\binom{n}{n} = 1\) (Il y a 1 façon de choisir tous les éléments).
Symétrie : Choisir \(k\) éléments revient au même que choisir les \(n-k\) éléments qu’on ne prend pas.
$$ \binom{n}{k} = \binom{n}{n-k} $$
Tirage du Loto : On choisit 5 boules parmi 49, sans ordre. C’est une combinaison de 5 parmi 49. Nombre de tirages = \(\binom{49}{5} = \frac{49!}{5!(49-5)!} = \frac{49!}{5!44!} = \frac{49 \times 48 \times 47 \times 46 \times 45}{5 \times 4 \times 3 \times 2 \times 1} = 1\ 906\ 884\). Dans une classe de 30 élèves, combien de groupes de 3 délégués peut-on former ? L’ordre ne compte pas. Nombre de groupes = \(\binom{30}{3} = \frac{30!}{3!27!} = \frac{30 \times 29 \times 28}{3 \times 2 \times 1} = 10 \times 29 \times 14 = 4060\).
La question clé : **Est-ce que l’ordre compte ?**
– Si **OUI** (ex: classement, code, mot, numéro de tel) \(\rightarrow\) k-uplets (si répétition possible) ou Arrangements (si pas de répétition).
– Si **NON** (ex: tirage de boules simultané, choix d’un groupe, main de cartes) \(\rightarrow\) Combinaisons.
Partie 4 : Triangle de Pascal et Nombre de Parties
1. Relation et Triangle de Pascal
La Relation de Pascal lie les coefficients binomiaux : Pour \(1 \le k \le n-1\)
$$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} $$
(Choisir k éléments parmi n, c’est soit choisir un élément spécial et k-1 parmi les n-1 autres, soit ne pas choisir l’élément spécial et k parmi les n-1 autres).
Cette relation permet de construire le Triangle de Pascal ligne par ligne, où chaque nombre est la somme des deux nombres juste au-dessus :
n=0: 1
n=1: 1 1
n=2: 1 2 1
n=3: 1 3 3 1
n=4: 1 4 6 4 1
n=5: 1 5 10 10 5 1
... (Ligne n contient les \(\binom{n}{k}\) pour k=0 à n)
\(\binom{4}{2} = 6\). On vérifie : \(\binom{3}{1} + \binom{3}{2} = 3 + 3 = 6\). OK.
Démonstrations de la Relation de Pascal
Méthode Combinatoire (expliquée dans la règle) :
Soit E un ensemble à n éléments. On fixe un élément \(a \in E\).
Pour former une partie A à k éléments de E :
– Soit A contient \(a\). Il faut alors choisir les \(k-1\) autres éléments parmi les \(n-1\) éléments restants de \(E \setminus \{a\}\). Il y a \(\binom{n-1}{k-1}\) façons.
– Soit A ne contient pas \(a\). Il faut alors choisir les \(k\) éléments parmi les \(n-1\) éléments restants de \(E \setminus \{a\}\). Il y a \(\binom{n-1}{k}\) façons.
Ces deux cas sont disjoints et couvrent toutes les possibilités. Par le principe additif : \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\).
Méthode par le Calcul : (Plus technique)
On part du membre de droite et on met au même dénominateur :
\(\binom{n-1}{k-1} + \binom{n-1}{k} = \frac{(n-1)!}{(k-1)!(n-1-(k-1))!} + \frac{(n-1)!}{k!(n-1-k)!}\)
\(= \frac{(n-1)!}{(k-1)!(n-k)!} + \frac{(n-1)!}{k!(n-k-1)!}\)
Dénominateur commun : \(k!(n-k)!\).
\(= \frac{k \times (n-1)!}{k!(n-k)!} + \frac{(n-k) \times (n-1)!}{k!(n-k)!}\)
\(= \frac{(n-1)! [k + (n-k)]}{k!(n-k)!} = \frac{(n-1)! \times n}{k!(n-k)!}\)
\(= \frac{n!}{k!(n-k)!} = \binom{n}{k}\).
2. Nombre de Parties d’un Ensemble
Le nombre total de parties (sous-ensembles) d’un ensemble \(E\) à \(n\) éléments est \(2^n\).
Cela correspond à la somme des nombres de parties à 0 élément, 1 élément, …, n éléments :
$$ \sum_{k=0}^{n} \binom{n}{k} = \binom{n}{0} + \binom{n}{1} + … + \binom{n}{n} = 2^n $$
Lien avec {0,1} : Choisir une partie de E revient à décider pour chaque élément s’il est « dedans » (1) ou « dehors » (0). C’est comme former un n-uplet de {0, 1}. Il y a \(2^n\) tels n-uplets.
Démonstration de \(\sum \binom{n}{k} = 2^n\)
Méthode 1 (Dénombrement direct) :
Pour construire une partie A d’un ensemble E à n éléments \(\{e_1, …, e_n\}\), on prend une décision pour chaque élément : soit on le met dans A, soit on ne le met pas.
Il y a 2 choix pour \(e_1\) (dedans/dehors).
Il y a 2 choix pour \(e_2\).
…
Il y a 2 choix pour \(e_n\).
Par le principe multiplicatif, il y a \(2 \times 2 \times … \times 2\) (n fois) = \(2^n\) façons de construire une partie.
Or, le nombre total de parties est aussi la somme du nombre de parties à 0 élément (\(\binom{n}{0}\)), à 1 élément (\(\binom{n}{1}\)), …, à n éléments (\(\binom{n}{n}\)).
Donc \(\sum_{k=0}^{n} \binom{n}{k} = 2^n\).
Méthode 2 (Binôme de Newton – si vu) :
La formule du binôme est \((a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k\).
En prenant \(a=1\) et \(b=1\), on obtient :
\((1+1)^n = \sum_{k=0}^{n} \binom{n}{k} 1^{n-k} 1^k = \sum_{k=0}^{n} \binom{n}{k}\).
Donc \(2^n = \sum_{k=0}^{n} \binom{n}{k}\).
Partie 5 : Entraînement (Exercices)
- Exercice 1 (Principes) : Une urne contient 5 boules Rouges, 3 Vertes, 2 Bleues. a) Combien de tirages possibles si on tire 3 boules successivement avec remise ? b) Combien de tirages possibles si on tire 3 boules successivement sans remise ? c) Combien de tirages possibles si on tire simultanément 3 boules ?
- Exercice 2 (Permutation) : Combien d’anagrammes du mot « TERMINALE » ? (Attention aux lettres répétées !)
- Exercice 3 (Combinaison) : Dans une classe de 15 filles et 10 garçons, on veut former un comité de 4 personnes. a) Combien de comités possibles au total ? b) Combien de comités contenant exactement 2 filles et 2 garçons ? c) Combien de comités contenant au moins une fille ?
- Exercice 4 (Triangle de Pascal) : Calculer \(\binom{6}{3}\) en utilisant la relation de Pascal et la ligne n=5 du triangle : 1 5 10 10 5 1.
Partie 6 : Corrections Détaillées
Correction Exercice 1 (Tirages)
Total = 5+3+2 = 10 boules.
a) Tirage successif avec remise (ordre compte, répétition possible) :
C’est un 3-uplet d’éléments parmi 10.
Nombre = \(n^k = 10^3 = 1000\) tirages.
b) Tirage successif sans remise (ordre compte, pas de répétition) :
C’est un arrangement de 3 parmi 10.
Nombre = \(A_{10}^3 = 10 \times 9 \times 8 = 720\) tirages.
c) Tirage simultané (ordre ne compte pas, pas de répétition) :
C’est une combinaison de 3 parmi 10.
Nombre = \(\binom{10}{3} = \frac{10!}{3!7!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 10 \times 3 \times 4 = 120\) tirages.
Correction Exercice 2 (Anagrammes)
Mot « TERMINALE » : 9 lettres.
Lettres répétées : E (2 fois), A (1 fois), L (1 fois), T (1 fois), R (1 fois), M (1 fois), I (1 fois), N (1 fois). Seul le E est répété.
Si toutes les lettres étaient distinctes, il y aurait \(9!\) anagrammes.
Comme les deux E sont indiscernables, on a divisé le nombre par le nombre de permutations des E (soit \(2!\)).
Nombre d’anagrammes = \(\frac{9!}{2!} = \frac{362880}{2} = 181440\).
(La formule générale pour les anagrammes d’un mot de n lettres avec \(n_1\) fois la lettre 1, \(n_2\) fois la lettre 2… est \(\frac{n!}{n_1! n_2! …}\) ).
Correction Exercice 3 (Comités)
15 Filles (F), 10 Garçons (G). Total 25 élèves. On forme un comité de 4 (ordre ne compte pas).
a) Comités possibles au total :
On choisit 4 élèves parmi 25.
Nombre = \(\binom{25}{4} = \frac{25 \times 24 \times 23 \times 22}{4 \times 3 \times 2 \times 1} = 25 \times 2 \times 23 \times 11 = 12650\).
b) Comités avec 2 Filles ET 2 Garçons :
Principe multiplicatif : (Choix des 2 Filles) \(\times\) (Choix des 2 Garçons).
– Choix des 2 Filles parmi 15 : \(\binom{15}{2} = \frac{15 \times 14}{2} = 105\).
– Choix des 2 Garçons parmi 10 : \(\binom{10}{2} = \frac{10 \times 9}{2} = 45\).
Nombre = \(105 \times 45 = 4725\).
c) Comités avec au moins une fille :
Méthode de l’événement contraire (plus simple).
Contraire de « au moins une fille » = « aucune fille » = « que des garçons » (donc 4 garçons).
– Nombre de comités avec 4 garçons : Choisir 4 G parmi 10. \(\binom{10}{4} = \frac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 \times 1} = 10 \times 3 \times 7 = 210\).
– Nombre de comités avec au moins une fille = Total – Nombre de comités sans fille.
Nombre = \(12650 – 210 = 12440\).
Correction Exercice 4 (Triangle de Pascal)
On veut calculer \(\binom{6}{3}\) en utilisant la ligne n=5 : 1 5 10 10 5 1.
Ces nombres sont \(\binom{5}{0}, \binom{5}{1}, \binom{5}{2}, \binom{5}{3}, \binom{5}{4}, \binom{5}{5}\).
On utilise la relation de Pascal : \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\).
Avec n=6 et k=3 :
\(\binom{6}{3} = \binom{6-1}{3-1} + \binom{6-1}{3} = \binom{5}{2} + \binom{5}{3}\).
On lit les valeurs sur la ligne n=5 :
\(\binom{5}{2} = 10\) (le 3ème nombre, car k commence à 0).
\(\binom{5}{3} = 10\) (le 4ème nombre).
Donc \(\binom{6}{3} = 10 + 10 = 20\).
Besoin d'aide en mathématiques ?
Je propose des cours de remise à niveau en visio ou en présentiel
Cours de Maths
tout niveau
€
30
/Heure
Tout niveau
Revoir les notions non comprises
Réaliser les devoirs avec méthode
Apprendre à s’organiser efficacement
Préparer les contrôles / Bac
Programme en fonction de vos besoins
Exclusif