Combinatoire et dénombrement
Savoir compter sans lister : factorielle, arrangements, permutations, combinaisons, triangle de Pascal et binôme de Newton.
1. La factorielle
Définition
Pour tout entier naturel n ≥ 1, on appelle factorielle de n, notée n!, le produit de tous les entiers de 1 à n :
n! = 1 × 2 × 3 × ⋯ × n
Convention : 0! = 1
Exemples
- 3! = 1 × 2 × 3 = 6
- 5! = 1 × 2 × 3 × 4 × 5 = 120
- 7! = 5 040
- 10! = 3 628 800
Relation de récurrence : (n+1)! = (n+1) × n!. Ainsi 6! = 6 × 5! = 6 × 120 = 720.
2. Principe multiplicatif
Si une expérience se décompose en k étapes successives et indépendantes, avec n₁ choix à la première étape, n₂ choix à la deuxième, …, n_k choix à la k-ième, alors le nombre total de résultats possibles est :
N = n₁ × n₂ × ⋯ × n_k
Exemple
Un code PIN à 4 chiffres (0 à 9, chiffres répétables) : 10 × 10 × 10 × 10 = 10 000 codes possibles.
Un menu avec 3 entrées, 4 plats et 2 desserts : 3 × 4 × 2 = 24 menus différents.
3. k-uplets (p-listes) — tirages avec remise
Définition
Un k-uplet (ou p-liste) d"un ensemble E à n éléments est une liste ordonnée de k éléments de E où les répétitions sont autorisées.
Nombre de k-uplets = n^k
Exemple
On tire successivement 3 cartes d"un jeu de 32 en remettant la carte à chaque fois. Le nombre de tirages ordonnés possibles est 32³ = 32 768.
4. Arrangements (sans remise, ordonnés)
Définition
Un arrangement de k éléments parmi n (avec k ≤ n) est une liste ordonnée de k éléments distincts tirés dans un ensemble de n éléments. Les répétitions sont interdites.
A(n, k) = n! / (n - k)! = n × (n-1) × ⋯ × (n-k+1)
Produit de k facteurs consécutifs décroissants à partir de n.
Exemples résolus
Exemple 1 — Podium d"une course
12 coureurs participent. Combien y a-t-il de façons différentes d"attribuer la 1re, la 2e et la 3e place ?
A(12, 3) = 12 × 11 × 10 = 1 320
Exemple 2 — Mots de 4 lettres
Combien de "mots" de 4 lettres distinctes peut-on former avec l"alphabet de 26 lettres ?
A(26, 4) = 26! / 22! = 26 × 25 × 24 × 23 = 358 800
5. Permutations
Définition
Une permutation de n éléments est un arrangement de n éléments parmi n, c"est-à-dire un rangement ordonné de tous les éléments d"un ensemble.
Nombre de permutations = A(n, n) = n!
Exemple
De combien de façons peut-on ranger 5 livres différents sur une étagère ?
5! = 120 façons.
6. Combinaisons — coefficient binomial
Définition
Une combinaison de k éléments parmi n est un sous-ensemble (non ordonné, sans répétition) de k éléments pris dans un ensemble de n éléments. Le nombre de telles combinaisons est noté C(n, k) ou C_n^k ou encore "n sur k" (coefficient binomial).
C(n, k) = n! / (k! × (n - k)!)
Relation avec les arrangements : C(n, k) = A(n, k) / k!
On divise par k! car l"ordre des k éléments choisis n"importe pas.
Propriétés immédiates
- C(n, 0) = 1 et C(n, n) = 1
- C(n, 1) = n
- Symétrie : C(n, k) = C(n, n - k)
Exemples résolus
Exemple 1 — Comité de 3 personnes
Dans un groupe de 10 personnes, combien de comités de 3 membres peut-on former ?
C(10, 3) = 10! / (3! × 7!) = (10 × 9 × 8) / (3 × 2 × 1) = 720 / 6 = 120
Exemple 2 — Combinaison au loto
Au loto français on tire 5 numéros parmi 49 (sans ordre, sans remise). Le nombre de grilles possibles est :
C(49, 5) = 49! / (5! × 44!) = 1 906 884
7. Triangle de Pascal et relation de Pascal
Relation de Pascal
Pour tout entier n ≥ 1 et tout entier k avec 1 ≤ k ≤ n - 1 :
C(n, k) = C(n - 1, k - 1) + C(n - 1, k)
Interprétation : on fixe un élément e. Les combinaisons de k parmi n sont soit celles qui contiennent e (C(n-1, k-1)), soit celles qui ne le contiennent pas (C(n-1, k)).
Triangle de Pascal
On dispose les coefficients C(n, k) en triangle : la n-ième ligne (n ≥ 0) contient C(n, 0), C(n, 1), …, C(n, n). Chaque valeur intérieure est la somme des deux valeurs situées au-dessus d"elle (relation de Pascal).
| 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 | |
Somme d"une ligne : C(n, 0) + C(n, 1) + ⋯ + C(n, n) = 2^n. Exemple : ligne n = 5 → 1 + 5 + 10 + 10 + 5 + 1 = 32 = 2⁵.
8. Formule du binôme de Newton
Théorème
Pour tous réels a et b et tout entier naturel n :
(a + b)^n = Σ_k=0^n C(n, k) × a^(n-k) × b^k
c"est-à-dire : C(n,0)a^n + C(n,1)a^(n-1)b + C(n,2)a^(n-2)b² + ⋯ + C(n,n)b^n
Exemples
Développement de (1 + x)^4
(1+x)^4 = C(4,0) + C(4,1)x + C(4,2)x² + C(4,3)x³ + C(4,4)x⁴
= 1 + 4x + 6x² + 4x³ + x⁴
Développement de (a + b)^3
(a+b)^3 = a³ + 3a²b + 3ab² + b³
Application : calcul de 1,01^10
On pose a = 1, b = 0,01 et n = 10. En ne gardant que les premiers termes :
1,01^10 ≈ 1 + 10 × 0,01 + 45 × 0,0001 ≈ 1 + 0,1 + 0,0045 ≈ 1,1045
(valeur exacte ≈ 1,10462, l"approximation est très bonne)
Exercices corrigés
Clique sur "Voir la correction" pour afficher la solution détaillée.
Délégation et arrangements
Un lycée compte 30 élèves en classe de Terminale. On souhaite désigner un délégué, un délégué adjoint et un secrétaire (trois rôles distincts, une personne ne peut avoir qu"un seul rôle).
- Combien y a-t-il de façons de constituer ce bureau ?
- Combien de bureaux différents peut-on former si le délégué doit être une fille, sachant qu"il y a 12 filles dans la classe ?
Voir la correction ▼
Question 1
On choisit 3 personnes parmi 30 dans un ordre précis (délégué ≠ adjoint ≠ secrétaire). Il s"agit donc d"un arrangement de 3 parmi 30.
A(30, 3) = 30 × 29 × 28 = 24 360 bureaux possibles.
Question 2
La délégué est choisie parmi les 12 filles (12 choix). L"adjoint et le secrétaire sont choisis parmi les 29 élèves restants, dans l"ordre.
12 × 29 × 28 = 12 × 812 = 9 744 bureaux.
Combinaisons et triangle de Pascal
On dispose d"un sac contenant 7 billes rouges et 5 billes bleues (12 billes au total, toutes distinguables par un numéro).
- Combien de façons y a-t-il de choisir 4 billes parmi les 12 ?
- Combien de façons y a-t-il d"obtenir exactement 3 billes rouges et 1 bleue ?
- Vérifier la relation C(12, 4) = C(11, 3) + C(11, 4).
Voir la correction ▼
Question 1
Choix de 4 billes parmi 12, sans ordre ni répétition :
C(12, 4) = 12! / (4! × 8!) = (12 × 11 × 10 × 9) / (4 × 3 × 2 × 1) = 11 880 / 24 = 495
Question 2
On choisit 3 rouges parmi 7 et 1 bleue parmi 5. Ces choix sont indépendants donc on multiplie (principe multiplicatif) :
C(7, 3) × C(5, 1) = 35 × 5 = 175
Vérification : C(7, 3) = (7 × 6 × 5) / 6 = 35. Correct.
Question 3
Vérifions la relation de Pascal : C(n,k) = C(n-1,k-1) + C(n-1,k) avec n = 12, k = 4.
C(11, 3) = (11 × 10 × 9) / 6 = 165 C(11, 4) = (11 × 10 × 9 × 8) / 24 = 330 C(11, 3) + C(11, 4) = 165 + 330 = 495 = C(12, 4) ✓
Binôme de Newton — application
Soit n un entier naturel non nul.
- Développer (1 + x)^5 en utilisant le binôme de Newton.
- En déduire la valeur de la somme S = C(5,0) - C(5,1) + C(5,2) - C(5,3) + C(5,4) - C(5,5).
Voir la correction ▼
Question 1
On lit les coefficients sur la ligne n = 5 du triangle de Pascal : 1, 5, 10, 10, 5, 1.
(1+x)^5 = 1 + 5x + 10x² + 10x³ + 5x⁴ + x⁵
Question 2
La somme S alterne les signes : S = Σ (-1)^k C(5, k) pour k de 0 à 5. C"est exactement le développement de (1 + (-1))^5 = (1 - 1)^5.
(1 - 1)^5 = 0^5 = 0
Vérification directe : 1 - 5 + 10 - 10 + 5 - 1 = 0. ✓
Généralisation : pour tout n ≥ 1, Σ (-1)^k C(n,k) = 0. Autrement dit, la somme des coefficients binomiaux de rang pair égale celle des coefficients de rang impair.
Récapitulatif des formules essentielles
| Objet | Notation | Formule |
|---|---|---|
| Factorielle | n! | 1 × 2 × ⋯ × n |
| k-uplets (avec remise) | — | n^k |
| Arrangements (sans remise) | A(n, k) | n! / (n-k)! |
| Permutations | A(n, n) | n! |
| Combinaisons | C(n, k) | n! / (k! × (n-k)!) |
| Relation de Pascal | — | C(n,k) = C(n-1,k-1) + C(n-1,k) |
| Binôme de Newton | (a+b)^n | Σ C(n,k) a^(n-k) b^k |