Combinatoire et dénombrement
Introduction
La combinatoire est la branche des mathématiques qui étudie le dénombrement, c'est-à-dire l'art de compter le nombre de façons de réaliser une action ou de choisir des éléments. Ces techniques sont essentielles en probabilités et dans de nombreux domaines scientifiques.
1. Principes fondamentaux du dénombrement
Principe additif : Si une action peut être réalisée de n₁ façons ou de n₂ façons (les deux cas étant incompatibles), alors elle peut être réalisée de n₁ + n₂ façons.
Plus généralement, si les cas sont mutuellement exclusifs :
Nombre total = n₁ + n₂ + ⋯ + nₖ
Exemple : Dans un restaurant, le menu propose 3 entrées chaudes ou 4 entrées froides. Le nombre de choix d'entrée est :
3 + 4 = 7
Principe multiplicatif : Si une action se décompose en étapes successives, la première pouvant être réalisée de n₁ façons, la deuxième de n₂ façons, etc., alors le nombre total de façons est :
n₁ × n₂ × ⋯ × nₖ
Exemple : Pour composer un menu avec 3 entrées, 4 plats et 2 desserts :
3 × 4 × 2 = 24 menus possibles
Attention :
- Principe additif : on choisit l'un OU l'autre (cas exclusifs)
- Principe multiplicatif : on choisit l'un ET l'autre (étapes successives)
2. Permutations
Factorielle : Pour tout entier naturel n ≥ 1, on définit la factorielle de n :
n! = n × (n-1) × (n-2) × ⋯ × 2 × 1
Par convention : 0! = 1.
Exemples de factorielles :
- 1! = 1
- 3! = 3 × 2 × 1 = 6
- 5! = 5 × 4 × 3 × 2 × 1 = 120
- 10! = 3 628 800
Permutation : Une permutation d'un ensemble de n éléments est un arrangement ordonné de tous ces éléments.
Le nombre de permutations de n éléments est :
n!
Exemple : De combien de façons peut-on ranger 5 livres sur une étagère ?
5! = 120 façons
3. Arrangements
Arrangement : Un arrangement de k éléments parmi n (avec k ≤ n) est un choix ordonné de k éléments parmi n.
Le nombre d'arrangements est noté Aₙᵏ :
Aₙᵏ = (n!)/((n-k)!) = n × (n-1) × ⋯ × (n-k+1)
Exemple : Dans une course de 10 chevaux, combien y a-t-il de tiercés possibles (les 3 premiers dans l'ordre) ?
A₁₀³ = (10!)/(7!) = 10 × 9 × 8 = 720
Quand utiliser les arrangements ? : On utilise les arrangements quand :
- L'ordre des éléments choisis compte
- On ne choisit qu'une partie des éléments
4. Combinaisons
Combinaison : Une combinaison de k éléments parmi n est un choix de k éléments parmi n sans tenir compte de l'ordre.
Le nombre de combinaisons est le coefficient binomial :
C(n,k) = Cₙᵏ = (n!)/(k!(n-k)!)
Relation entre arrangements et combinaisons : Comme un arrangement tient compte de l'ordre et une combinaison non :
C(n,k) = (Aₙᵏ)/(k!)
En effet, chaque combinaison de k éléments donne naissance à k! arrangements (permutations de ces k éléments).
Exemple : De combien de façons peut-on choisir 3 délégués parmi 10 élèves ?
C(10,3) = (10!)/(3! × 7!) = (10 × 9 × 8)/(3 × 2 × 1) = 120
Propriétés des coefficients binomiaux : Pour tout n ≥ 0 et 0 ≤ k ≤ n :
Symétrie : C(n,k) = C(n,n-k)
Valeurs aux bords : C(n,0) = C(n,n) = 1
Formule de Pascal (pour k ≤ n - 1) : C(n+1,k+1) = C(n,k) + C(n,k+1)
Somme : Σ(k=0→n) C(n,k) = 2ⁿ
5. Triangle de Pascal
Triangle de Pascal : Le triangle de Pascal est un tableau triangulaire où chaque coefficient est la somme des deux coefficients situés au-dessus de lui (formule 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
Lecture du triangle : La ligne n du triangle de Pascal donne les valeurs de C(n,0), C(n,1), …, C(n,n).
Par exemple, ligne n=4 : C(4,0)=1, C(4,1)=4, C(4,2)=6, C(4,3)=4, C(4,4)=1.
6. Formule du binôme de Newton
Binôme de Newton : Pour tous réels a et b et tout entier naturel n :
(a + b)ⁿ = Σ(k=0→n) C(n,k) aⁿ⁻ᵏ bᵏ
= C(n,0) aⁿ + C(n,1) aⁿ⁻¹ b + C(n,2) aⁿ⁻² b² + ⋯ + C(n,n) bⁿ
Exemple : développer (a+b)³ : (a+b)³ = C(3,0)a³ + C(3,1)a² b + C(3,2)a b² + C(3,3)b³
= a³ + 3a² b + 3a b² + b³
Exemple : développer (2x - 1)⁴ : On pose a = 2x et b = -1 :
(2x - 1)⁴ = Σ(k=0→4) C(4,k) (2x)⁴⁻ᵏ (-1)ᵏ
= 16x⁴ - 32x³ + 24x² - 8x + 1
Cas particuliers utiles : En posant a = 1 et b = 1 dans le binôme :
2ⁿ = Σ(k=0→n) C(n,k)
En posant a = 1 et b = -1, pour n ≥ 1 :
0 = Σ(k=0→n) (-1)ᵏ C(n,k)
Ce qui donne, pour n ≥ 1 : la somme des coefficients binomiaux de rang pair est égale à celle de rang impair, et chacune vaut 2ⁿ⁻¹.
À retenir
Résumé :
Principe additif (OU) : on additionne les possibilités
Principe multiplicatif (ET) : on multiplie les possibilités
Permutations de n éléments : n!
Arrangements de k parmi n (ordre compte) : Aₙᵏ = (n!)/((n-k)!)
Combinaisons de k parmi n (ordre ne compte pas) : C(n,k) = (n!)/(k!(n-k)!)
Formule de Pascal (pour k ≤ n - 1) : C(n+1,k+1) = C(n,k) + C(n,k+1)
Binôme de Newton : (a+b)ⁿ = Σ(k=0→n) C(n,k) aⁿ⁻ᵏ bᵏ