Combinatoire et dénombrement
Arrangements, permutations, combinaisons, triangle de Pascal.
📄 Télécharger le PDF📋 Sommaire
Capacités exigibles — Programme officiel (BO)
- Dans le cadre d'un problème de dénombrement, utiliser une représentation adaptée (ensembles, arbres, tableaux, diagrammes) et reconnaître les objets à dénombrer.
- Effectuer des dénombrements simples dans des situations issues de divers domaines scientifiques (informatique, génétique, théorie des jeux, probabilités, etc.).
Démonstrations exigibles — Programme officiel (BO)
- Démonstration par dénombrement de la relation : \(\displaystyle\sum_{k=0}^{n}\dbinom{n}{k} = 2^n\).
- Démonstrations de la relation de Pascal (par le calcul et par une méthode combinatoire).
Exemples d'algorithme — Programme officiel (BO)
- Pour un entier \(n\) donné, génération de la liste des coefficients \(\dbinom{n}{k}\) à l'aide de la relation de Pascal.
- Génération des permutations d'un ensemble fini, ou tirage aléatoire d'une permutation.
- Génération des parties à 2, 3 éléments d'un ensemble fini.
1. Introduction
Dans de nombreux problèmes de probabilités, calculer \(P(A)\) revient à compter le nombre d'issues favorables et le nombre total d'issues. Ce chapitre fournit les outils combinatoires pour effectuer ces comptages efficacement, sans avoir à lister exhaustivement toutes les possibilités.
La question centrale est : l'ordre compte-t-il ?
- Oui (podium, anagramme, code) → arrangements et permutations.
- Non (comité, main de cartes, groupe) → combinaisons.
2. Cours
A — Arrangements et permutations
B — Combinaisons
Justification : pour chaque élément, on choisit indépendamment de l'inclure (1) ou non (0) dans une partie → \(2^n\) séquences binaires distinctes.
- Symétrie : \(\dbinom{n}{k} = \dbinom{n}{n-k}\) (choisir \(k\) éléments revient à exclure \(n-k\) éléments).
- Relation de Pascal : pour \(1 \leq k \leq n-1\) : \[ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \]
- Cas particuliers : \[ \binom{n}{0} = 1, \quad \binom{n}{1} = n, \quad \binom{n}{2} = \frac{n(n-1)}{2} \]
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
3. Exemples guidés
\(5! = 120\)
\(\dfrac{10!}{7!} = 10 \times 9 \times 8 = 720\) (on simplifie les facteurs communs).
\(\dbinom{8}{3} = \dfrac{8!}{3! \times 5!} = \dfrac{8 \times 7 \times 6}{3 \times 2 \times 1} = \dfrac{336}{6} = 56\).
Situation : 10 coureurs s'affrontent. Combien de podiums (1er, 2e, 3e distincts) possibles ?
L'ordre compte (la médaille d'or est différente de la médaille d'argent). C'est un 3-arrangement de 10 éléments : \[ A_{10}^3 = \frac{10!}{7!} = 10 \times 9 \times 8 = 720 \text{ podiums} \]
Situation : Parmi 12 personnes, choisir un comité de 4 membres (sans rôle attribué).
L'ordre ne compte pas → combinaison : \[ \binom{12}{4} = \frac{12!}{4! \times 8!} = \frac{12 \times 11 \times 10 \times 9}{4 \times 3 \times 2 \times 1} = \frac{11880}{24} = 495 \]
Situation : On tire 5 cartes dans un jeu de 52. Quelle est la probabilité d'obtenir exactement 2 as ?
Nombre total de mains de 5 cartes : \(\dbinom{52}{5} = 2\,598\,960\).
Mains favorables : 2 as parmi 4 et 3 non-as parmi 48 : \[ \binom{4}{2} \times \binom{48}{3} = 6 \times 17\,296 = 103\,776 \]
Probabilité : \[ P = \frac{103\,776}{2\,598\,960} \approx 0{,}0399 \approx 4\,\% \]
En appliquant \(\dbinom{n}{k} = \dbinom{n-1}{k-1} + \dbinom{n-1}{k}\) à chaque étape :
| \(n\) | Coefficients \(\binom{n}{k}\) | |||||
|---|---|---|---|---|---|---|
| 0 | 1 | |||||
| 1 | 1 | 1 | ||||
| 2 | 1 | 2 | 1 | |||
| 3 | 1 | 3 | 3 | 1 | ||
| 4 | 1 | 4 | 6 | 4 | 1 | |
| 5 | 1 | 5 | 10 | 10 | 5 | 1 |
4. Exercices progressifs
Calculer :
- \(7!\)
- \(\dbinom{6}{2}\)
- \(\dfrac{9!}{6!}\)
- Le nombre d'anagrammes du mot MATHS.
1. \(7! = 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 5040\).
2. \(\dbinom{6}{2} = \dfrac{6!}{2! \times 4!} = \dfrac{6 \times 5}{2 \times 1} = 15\).
3. \(\dfrac{9!}{6!} = 9 \times 8 \times 7 = 504\).
4. MATHS comporte 5 lettres toutes distinctes (M, A, T, H, S). Le nombre d'anagrammes est \(5! = 120\).
Dans une classe de 30 élèves :
- Combien de groupes de 3 élèves peut-on former ?
- Combien de groupes de 3 si le délégué de classe doit toujours être dans le groupe ?
1. On choisit 3 élèves parmi 30, sans tenir compte de l'ordre : \[ \binom{30}{3} = \frac{30 \times 29 \times 28}{3 \times 2 \times 1} = \frac{24\,360}{6} = 4\,060 \]
2. Le délégué est déjà dans le groupe, il reste à choisir 2 élèves parmi les 29 autres : \[ \binom{29}{2} = \frac{29 \times 28}{2} = 406 \]
Au Loto, on tire 6 numéros distincts parmi 49 (l'ordre ne compte pas).
- Combien de combinaisons de 6 numéros possibles ?
- Un joueur a exactement 5 numéros « bons » (c'est-à-dire parmi les 6 gagnants). Combien de grilles de 6 numéros peuvent contenir exactement ces 5 bons numéros ?
1. \[ \binom{49}{6} = \frac{49!}{6! \times 43!} = \frac{49 \times 48 \times 47 \times 46 \times 45 \times 44}{720} = 13\,983\,816 \] Il y a près de 14 millions de combinaisons possibles !
2. Pour avoir exactement 5 numéros bons :
- Choisir 5 numéros parmi les 6 gagnants : \(\dbinom{6}{5} = 6\) façons.
- Choisir le 6e numéro parmi les \(49 - 6 = 43\) numéros non gagnants : \(\dbinom{43}{1} = 43\) façons.
- Montrer que \(\dbinom{n}{k} = \dbinom{n}{n-k}\) en utilisant la formule factorielle.
- En déduire \(\dbinom{10}{7}\) sachant que \(\dbinom{10}{3} = 120\).
1. \[ \binom{n}{n-k} = \frac{n!}{(n-k)!\,\bigl(n-(n-k)\bigr)!} = \frac{n!}{(n-k)!\,k!} = \binom{n}{k} \] L'égalité est immédiate car \(k!(n-k)! = (n-k)!k!\).
2. Par symétrie : \(\dbinom{10}{7} = \dbinom{10}{10-7} = \dbinom{10}{3} = 120\).
Interprétation : choisir 7 éléments parmi 10 revient à choisir les 3 éléments qu'on n'inclut pas.
Démontrer algébriquement la relation de Pascal : \[ \binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1} \quad \text{pour } 0 \leq k \leq n-1 \]
On développe le membre gauche en réduisant au même dénominateur. Le dénominateur commun est \(k!(n-k)!\) multiplié intelligemment :
\[ \binom{n}{k} + \binom{n}{k+1} = \frac{n!}{k!(n-k)!} + \frac{n!}{(k+1)!(n-k-1)!} \]On met au même dénominateur \((k+1)!(n-k)!\) :
\[ = \frac{n!(k+1)}{(k+1)!(n-k)!} + \frac{n!(n-k)}{(k+1)!(n-k)!} = \frac{n!\bigl[(k+1)+(n-k)\bigr]}{(k+1)!(n-k)!} = \frac{n!(n+1)}{(k+1)!(n-k)!} \] \[ = \frac{(n+1)!}{(k+1)!\bigl((n+1)-(k+1)\bigr)!} = \binom{n+1}{k+1} \]La relation est démontrée. \(\square\)
Démontrer que pour tout entier \(n \geq 0\) : \[ \sum_{k=0}^{n} \binom{n}{k} = 2^n \] On pourra utiliser deux approches différentes.
Approche 1 — Argument combinatoire :
Le membre gauche \(\displaystyle\sum_{k=0}^n \binom{n}{k}\) compte le nombre total de parties d'un ensemble \(E\) à \(n\) éléments, en les regroupant par cardinal : \(\binom{n}{0}\) parties de cardinal 0, \(\binom{n}{1}\) de cardinal 1, …, \(\binom{n}{n}\) de cardinal \(n\).
Le nombre total de parties d'un ensemble à \(n\) éléments est \(2^n\) (pour chaque élément, 2 choix : inclus ou exclu). Donc \(\displaystyle\sum_{k=0}^n \binom{n}{k} = 2^n\). \(\square\)
Approche 2 — Formule du binôme :
La formule du binôme de Newton donne, pour tous réels \(a\) et \(b\) : \[ (a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k} \] En prenant \(a = b = 1\) : \[ 2^n = (1+1)^n = \sum_{k=0}^{n} \binom{n}{k} 1^k \cdot 1^{n-k} = \sum_{k=0}^{n} \binom{n}{k} \] Ce qui établit le résultat. \(\square\)
Vérification pour \(n = 3\) : \(\binom{3}{0} + \binom{3}{1} + \binom{3}{2} + \binom{3}{3} = 1 + 3 + 3 + 1 = 8 = 2^3\) ✓.
📌 Fiche de synthèse
L'ordre compte-t-il ?
- Oui → arrangements ou permutations.
- Non → combinaisons.
Formules à retenir
- \(n! = n \times (n-1) \times \cdots \times 1\), \quad \(0! = 1\).
- Arrangements : \(A_n^k = \dfrac{n!}{(n-k)!}\) (\(k\) facteurs décroissants à partir de \(n\)).
- Permutations : \(n!\).
- Combinaisons : \(\dbinom{n}{k} = \dfrac{n!}{k!(n-k)!}\).
Propriétés des coefficients binomiaux
- Symétrie : \(\dbinom{n}{k} = \dbinom{n}{n-k}\).
- Pascal : \(\dbinom{n}{k} + \dbinom{n}{k+1} = \dbinom{n+1}{k+1}\).
- Somme : \(\displaystyle\sum_{k=0}^n \binom{n}{k} = 2^n\).
- Cas simples : \(\dbinom{n}{0} = 1\), \(\dbinom{n}{1} = n\), \(\dbinom{n}{2} = \dfrac{n(n-1)}{2}\).
Stratégie pour les problèmes de probabilité
- Identifier l'univers \(\Omega\) et son cardinal (souvent une combinaison).
- Compter les issues favorables (décomposer si nécessaire, utiliser le principe multiplicatif).
- Appliquer \(P(A) = \dfrac{|A|}{|\Omega|}\) si équiprobabilité.
📐 Démonstrations exigibles
Ces démonstrations sont exigibles au baccalauréat — Terminale Spécialité Mathématiques.
Somme des coefficients binomiaux : \(\sum_{k=0}^{n}\binom{n}{k} = 2^n\)
Pour tout entier \(n \geq 0\) : \(\displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n\).
Preuve par dénombrement :
L'ensemble \(\{1, 2, \ldots, n\}\) possède \(2^n\) sous-ensembles (pour chaque élément : inclus ou non — deux choix indépendants).
D'autre part, les sous-ensembles de cardinal \(k\) sont au nombre de \(\dbinom{n}{k}\). En regroupant par cardinal :
\[\sum_{k=0}^{n} \binom{n}{k} = 2^n \quad \square\]Preuve par le binôme de Newton (admis) :
\[(1+1)^n = \sum_{k=0}^{n} \binom{n}{k} 1^k \cdot 1^{n-k} = \sum_{k=0}^{n} \binom{n}{k} = 2^n\]Relation de Pascal
Pour tout \(1 \leq k \leq n\) : \(\dbinom{n}{k} + \dbinom{n}{k-1} = \dbinom{n+1}{k}\).
Preuve par le calcul :
\[\binom{n}{k} + \binom{n}{k-1} = \frac{n!}{k!\,(n-k)!} + \frac{n!}{(k-1)!\,(n-k+1)!}\] \[= \frac{n!}{k!\,(n-k+1)!}\bigl[(n-k+1) + k\bigr] = \frac{n!\cdot(n+1)}{k!\,(n+1-k)!} = \frac{(n+1)!}{k!\,(n+1-k)!} = \binom{n+1}{k}\]Preuve combinatoire :
On veut choisir \(k\) éléments parmi \(\{1, \ldots, n+1\}\). On distingue deux cas :
- L'élément \(n+1\) n'est pas sélectionné : on choisit \(k\) éléments parmi \(\{1,\ldots,n\}\) → \(\dbinom{n}{k}\) façons.
- L'élément \(n+1\) est sélectionné : on choisit \(k-1\) éléments parmi \(\{1,\ldots,n\}\) → \(\dbinom{n}{k-1}\) façons.
Ces deux cas étant disjoints et exhaustifs : \(\dbinom{n+1}{k} = \dbinom{n}{k} + \dbinom{n}{k-1}\). \(\square\)
💻 Exemples d'algorithme
Algorithmes au programme de ce chapitre, à implémenter en Python.
Génération des coefficients binomiaux par la relation de Pascal
Calcul du triangle de Pascal ligne par ligne, sans utiliser de factorielles.
def triangle_pascal(N):
"""
Génère le triangle de Pascal jusqu'à la ligne N.
Utilise la relation de Pascal : C(n,k) = C(n-1,k-1) + C(n-1,k).
"""
C = [[0] * (N + 1) for _ in range(N + 1)]
for n in range(N + 1):
C[n][0] = 1
C[n][n] = 1
for k in range(1, n):
C[n][k] = C[n-1][k-1] + C[n-1][k]
return C
# Affichage du triangle pour N = 8
C = triangle_pascal(8)
for n in range(9):
ligne = " ".join(str(C[n][k]) for k in range(n + 1))
print(f"n={n}: {ligne}")
# Accès direct : C(7, 3) = ?
print(f"\nC(7,3) = {C[7][3]}") # doit valoir 35Génération de toutes les permutations
Générer les \(n!\) permutations d'une liste par récursion ou tirage aléatoire.
# ── Toutes les permutations par récursion ───────────────────
def permutations(lst):
"""Retourne la liste de toutes les permutations de lst."""
if len(lst) <= 1:
return [lst[:]]
resultat = []
for i in range(len(lst)):
reste = lst[:i] + lst[i+1:]
for perm in permutations(reste):
resultat.append([lst[i]] + perm)
return resultat
perms = permutations([1, 2, 3, 4])
print(f"Nombre de permutations de 4 éléments : {len(perms)} (4! = 24)")
# ── Tirage aléatoire d'une permutation ──────────────────────
import random
def permutation_aleatoire(lst):
"""Algorithme de Fisher-Yates : permutation uniforme en O(n)."""
lst = lst[:]
n = len(lst)
for i in range(n - 1, 0, -1):
j = random.randint(0, i)
lst[i], lst[j] = lst[j], lst[i]
return lst
print(permutation_aleatoire(list(range(1, 8))))Génération des parties à \(k\) éléments
Générer toutes les parties (sous-ensembles) à \(k\) éléments d'un ensemble à \(n\) éléments.
def parties_k(lst, k):
"""Génère toutes les parties à k éléments de lst (récursif)."""
if k == 0:
return [[]]
if not lst or k > len(lst):
return []
# Cas 1 : on prend lst[0] dans la partie
avec = [[lst[0]] + p for p in parties_k(lst[1:], k - 1)]
# Cas 2 : on ne prend pas lst[0]
sans = parties_k(lst[1:], k)
return avec + sans
# Parties à 2 éléments de {1, 2, 3, 4, 5}
p2 = parties_k([1, 2, 3, 4, 5], 2)
print(f"Parties à 2 éléments de {{1..5}} : C(5,2) = {len(p2)}")
for p in p2:
print(p)