Mémento Combinatoire et dénombrement — Formules et astuces

📖 Résumé de cours

1. Vocabulaire : ensembles finis et cardinal

Un ensemble fini $E$ possède un nombre fini d'éléments, appelé cardinal de $E$ et noté $Card (E)$ ou $∣ E ∣$ . Dénombrer, c'est compter le nombre d'éléments d'un ensemble ou le nombre de configurations possibles. Si $A$ et $B$ sont deux ensembles finis disjoints, on a $Card (A \cup B) = Card (A) + Card (B)$ . Dans le cas général, $Card (A \cup B) = Card (A) + Card (B) - Card (A \cap B)$ .

2. Principe additif

Si une situation se décompose en plusieurs cas disjoints (qui n'ont aucune issue commune), le nombre total de possibilités est la somme des possibilités de chaque cas. Par exemple, choisir une carte rouge OU une figure noire : on additionne après avoir vérifié qu'il n'y a pas de double comptage.

Exemple : un menu propose 3 entrées végétariennes et 4 entrées non végétariennes. Comme ces choix s'excluent, il y a $3 + 4 = 7$ entrées possibles.

3. Principe multiplicatif

Lorsqu'un choix se fait en plusieurs étapes successives indépendantes, le nombre total de possibilités est le produit du nombre de possibilités à chaque étape. C'est le principe fondamental du dénombrement.

Exemple : un menu avec 3 entrées, 5 plats et 2 desserts offre $3 \times 5 \times 2 = 30$ repas différents. On parle aussi de cardinal d'un produit cartésien : $Card (A \times B) = Card (A) \times Card (B)$ .

4. k-uplets (listes avec répétition)

Un $k$ -uplet (ou $k$ -liste) d'un ensemble $E$ à $n$ éléments est une suite ordonnée de $k$ éléments de $E$ , les répétitions étant autorisées. Par le principe multiplicatif, chacune des $k$ positions peut être remplie de $n$ façons :

$n^{k}$

Exemple : un code de carte bancaire à 4 chiffres correspond à un $4$ -uplet de ${0, \dots, 9}$ : il y a $1 0^{4} = 10000$ codes possibles. L'ordre compte et un même chiffre peut se répéter.

5. k-uplets d'éléments distincts : les arrangements

Un arrangement de $k$ éléments parmi $n$ est un $k$ -uplet d'éléments deux à deux distincts : l'ordre compte, sans répétition. La première position offre $n$ choix, la deuxième $n - 1$ , etc., jusqu'à la $k$ -ième qui en offre $n - k + 1$ . On note ce nombre $A_{n}^{k}$ :

$A_{n}^{k} = n (n - 1) \dots (n - k + 1) = \frac{n !}{( n - k )!} (0 \leq k \leq n)$

Exemple : un podium (or, argent, bronze) parmi 8 athlètes : $A_{8}^{3} = 8 \times 7 \times 6 = 336$ classements possibles.

6. Permutations et factorielle

Une permutation d'un ensemble à $n$ éléments est un arrangement de ses $n$ éléments : c'est un rangement ordonné de tous les éléments. Leur nombre est la factorielle de $n$ :

$n! = n \times (n - 1) \times \dots \times 2 \times 1$

avec la convention $0! = 1$ . Une permutation est le cas particulier $A_{n}^{n} = n!$ .

Exemple : le nombre de façons de ranger 5 livres distincts sur une étagère est $5! = 120$ .

7. Combinaisons et coefficient binomial

Une combinaison de $k$ éléments parmi $n$ est un sous-ensemble (une partie) à $k$ éléments : l'ordre ne compte pas et il n'y a pas de répétition. Le nombre de combinaisons est le coefficient binomial $(k n)$ :

$(k n) = \frac{A _{n}^{k}}{k !} = \frac{n !}{k ! ( n - k )!}$

On divise les arrangements par $k!$ car chaque sous-ensemble est compté $k!$ fois (une fois par ordre de ses éléments).

Exemple : tirer 3 cartes d'un jeu de 32 (l'ordre est sans importance) : $(3 32) = \frac{32 \times 31 \times 30}{3 !} = 4960$ mains.

8. Propriétés du coefficient binomial

Cas particuliers : $(0 n) = (n n) = 1$ et $(1 n) = (n - 1 n) = n$ .

Symétrie : choisir les $k$ éléments d'une partie revient à choisir les $n - k$ éléments qu'on laisse de côté, d'où

$(k n) = (n - k n)$

Relation de Pascal : pour $1 \leq k \leq n - 1$ ,

$(k - 1 n - 1) + (k n - 1) = (k n)$

Elle s'interprète en fixant un élément : soit on le prend (il reste $(k - 1 n - 1)$ choix), soit on ne le prend pas ( $(k n - 1)$ choix).

9. Triangle de Pascal

La relation de Pascal permet de construire ligne par ligne le triangle de Pascal, où chaque coefficient est la somme des deux situés juste au-dessus de lui. La ligne $n$ donne tous les $(k n)$ pour $k$ allant de $0$ à $n$ . C'est un moyen rapide de calculer les petits coefficients sans factorielle.

10. Parties d'un ensemble

Le nombre total de parties (sous-ensembles) d'un ensemble à $n$ éléments est $2^{n}$ : pour chaque élément, on décide de le prendre ou non, soit $2$ choix indépendants. En classant les parties selon leur taille, on retrouve la formule du binôme évaluée en $1$ :

$k = 0 \sum n (k n) = 2^{n}$

Exemple : un ensemble de 4 objets possède $2^{4} = 16$ parties (en comptant l'ensemble vide et l'ensemble entier).

11. Lien avec la loi binomiale

Le coefficient binomial $(k n)$ compte le nombre de façons de placer les $k$ succès parmi $n$ répétitions. C'est exactement ce qui apparaît dans la loi binomiale $B (n, p)$ : si $X$ suit cette loi, alors

$P (X = k) = (k n) p^{k} (1 - p)^{n - k}$

Le facteur $(k n)$ dénombre les arrangements de succès et d'échecs, les puissances donnant la probabilité d'une issue particulière. La combinatoire fonde ainsi la modélisation probabiliste des épreuves répétées indépendantes.

🔑 Formules clés à retenir

Cardinal d'une réunion : $Card (A \cup B) = Card (A) + Card (B) - Card (A \cap B)$ .
Produit cartésien : $Card (A \times B) = Card (A) \times Card (B)$ .
$k$ -uplets (avec ordre et répétition) : $n^{k}$ .
Factorielle : $n! = n \times (n - 1) \times \dots \times 1$ , avec $0! = 1$ .
Arrangements (ordre, sans répétition) : $A_{n}^{k} = \frac{n !}{( n - k )!}$ .
Permutations : $A_{n}^{n} = n!$ .
Combinaisons (sans ordre, sans répétition) : $(k n) = \frac{n !}{k ! ( n - k )!}$ .
Symétrie : $(k n) = (n - k n)$ .
Relation de Pascal : $(k - 1 n - 1) + (k n - 1) = (k n)$ .
Cas particuliers : $(0 n) = (n n) = 1$ et $(1 n) = n$ .
Nombre de parties : $k = 0 \sum n (k n) = 2^{n}$ .
Loi binomiale : $P (X = k) = (k n) p^{k} (1 - p)^{n - k}$ .

💡 Astuces & erreurs à éviter

Le piège central : ordre ou pas ? Confondre arrangement et combinaison est l'erreur la plus fréquente. Demandez-vous toujours : « si j'échange deux éléments, est-ce une nouvelle situation ? » Si oui, c'est un arrangement.
Répétition ou non. « Tirage avec remise » ou « positions indépendantes » $\Rightarrow$ répétition autorisée ( $n^{k}$ ). « Tirage sans remise » ou « éléments distincts » $\Rightarrow$ pas de répétition ( $A_{n}^{k}$ ou $(k n)$ ).
Mots-clés trompeurs. « Comité », « équipe », « groupe », « main » $\to$ combinaison. « Code », « mot », « podium », « classement », « anagramme » $\to$ ordre $\to$ arrangement ou permutation.
Ne pas oublier $0! = 1$ ni $(0 n) = 1$ : l'ensemble vide est une partie valide, ce qui justifie le terme constant des sommes.
Additif vs multiplicatif. « ET » / étapes successives $\Rightarrow$ on multiplie. « OU » / cas exclusifs $\Rightarrow$ on additionne. Mélanger les deux fausse tout le calcul.
Symétrie utile. Pour calculer $(k n)$ quand $k$ est grand, utilisez $(k n) = (n - k n)$ : par exemple $(48 50) = (2 50) = 1225$ .
Double comptage. Quand des cas se chevauchent, n'oubliez pas de retrancher l'intersection (formule du crible) pour ne pas compter deux fois.
Anagrammes avec lettres répétées. Le nombre d'anagrammes d'un mot n'est pas $n!$ si des lettres se répètent : il faut diviser par les factorielles des effectifs de chaque lettre répétée.

🎯 Méthodes de résolution

Identifier la nature du tirage. Repérer combien d'éléments on choisit ( $k$ ) dans un ensemble de taille $n$ , et si l'on construit une liste ordonnée ou un sous-ensemble.
L'ordre compte-t-il ? Se demander si échanger deux éléments change la configuration. Podium, code, mot, classement : l'ordre compte. Main de cartes, comité, sous-ensemble : l'ordre ne compte pas.
Y a-t-il répétition ? Un même élément peut-il apparaître plusieurs fois ? Tirage avec remise ou positions indépendantes : répétition possible. Tirage sans remise, personnes distinctes : pas de répétition.
Choisir la formule selon la grille. Ordre + répétition $\to n^{k}$ . Ordre + sans répétition $\to A_{n}^{k} = \frac{n !}{( n - k )!}$ . Sans ordre + sans répétition $\to (k n) = \frac{n !}{k ! ( n - k )!}$ . Cas $k = n$ avec ordre $\to$ permutation $n!$ .
Arrangement ou combinaison ? Si l'énoncé évoque un rangement, un mot, un classement, une affectation à des places distinctes : arrangement. Si l'on forme un groupe, une équipe, une poignée d'objets sans rôle distinct : combinaison. Astuce : combinaison $=$ arrangement $\div k!$ .
Décomposer un problème complexe. Découper en étapes successives (principe multiplicatif, on multiplie) ou en cas disjoints (principe additif, on additionne). Vérifier que les cas ne se recouvrent pas.
Utiliser le complémentaire si besoin. Pour dénombrer « au moins un », il est souvent plus simple de compter le contraire (« aucun ») puis de soustraire du total.
Vérifier la cohérence du résultat. Contrôler les ordres de grandeur, vérifier $0 \leq k \leq n$ , et que combinaisons $\leq$ arrangements pour les mêmes $n$ et $k$ .

✏️

Exercices corrigés

S'entraîner sur ce chapitre

📄

Annales du bac

Sujets corrigés 2022–2024

📋

Autres mémentos

Tous les chapitres