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_1 façons ou de n_2 façons (les deux cas étant incompatibles), alors elle peut être réalisée de n_1 + n_2 façons.
Plus généralement, si les cas sont mutuellement exclusifs :
[formule]
Exemple : Dans un restaurant, le menu propose 3 entrées chaudes ou 4 entrées froides. Le nombre de choix d'entrée est :
[formule]
Principe multiplicatif : Si une action se décompose en étapes successives, la première pouvant être réalisée de n_1 façons, la deuxième de n_2 façons, etc., alors le nombre total de façons est :
[formule]
Exemple : Pour composer un menu avec 3 entrées, 4 plats et 2 desserts :
[formule]
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 :
[formule]
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 :
[formule]
Exemple : De combien de façons peut-on ranger 5 livres sur une étagère ?
[formule]
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_n^k :
[formule]
Exemple : Dans une course de 10 chevaux, combien y a-t-il de tiercés possibles (les 3 premiers dans l'ordre) ?
[formule]
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 :
[formule]
Relation entre arrangements et combinaisons : Comme un arrangement tient compte de l'ordre et une combinaison non :
[formule]
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 ?
[formule]
Propriétés des coefficients binomiaux : Pour tout n 0 et 0 k n :
Symétrie** : n{k} = n{n-k}
Valeurs aux bords** : n{0} = n{n} = 1
Formule de Pascal** : n+1{k+1} = n{k} + n{k+1}
Somme** : _{k=0}^{n} n{k} = 2^n
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).
[formule]
Lecture du triangle : La ligne n du triangle de Pascal donne les valeurs de n{0}, n{1}, , n{n}.
Par exemple, ligne n=4 : 4{0}=1, 4{1}=4, 4{2}=6, 4{3}=4, 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 :
[formule]
[formule]
Exemple : développer (a+b)^3 : [formule]
[formule]
Exemple : développer (2x - 1)^4 : On pose a = 2x et b = -1 :
[formule]
[formule]
Cas particuliers utiles : En posant a = 1 et b = 1 dans le binôme :
[formule]
En posant a = 1 et b = -1 :
[formule]
Ce qui donne : la somme des coefficients binomiaux de rang pair est égale à celle de rang impair, et chacune vaut 2^{n-1}.
À 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^k = n!{(n-k)!}
Combinaisons** de k parmi n (ordre ne compte pas) : n{k} = n!{k!(n-k)!}
Formule de Pascal** : n+1{k+1} = n{k} + n{k+1}
Binôme de Newton** : (a+b)^n = _{k=0}^{n} n{k} a^{n-k} b^k