Cours complet : Combinatoire et dénombrement
La combinatoire est la branche des mathématiques qui étudie le dénombrement des configurations et des arrangements d'éléments. Elle fournit des outils essentiels pour le calcul des probabilités et l'analyse de situations discretes. Les techniques de dénombrement reposent sur des principes fondamentaux (principe additif, principe multiplicatif) et des formules specifiques (arrangements, permutations, combinaisons, coefficients binomiaux). Ces outils permettent de résoudre des problemes varies : calcul du nombre de mots de passe possibles, de tirages dans une urne, de chemins dans un reseau, ou de distributions d'objets. La maitrise de ces outils est indispensable pour aborder les probabilités et la loi binomiale au programme de Terminale.
Prérequis
- Ensembles : réunion, intersection, cardinal
- Calcul litteral et puissances
- Notion de fonction de N dans R
- Produit cartesien de deux ensembles
1. Principes fondamentaux du dénombrement
Le principe additif stipule que si deux ensembles A et B sont disjoints, le cardinal de leur réunion est |A union B| = |A| + |B|. Plus généralement, pour n ensembles disjoints, |A1 union ... union An| = |A1| + ... + |An|.
Le principe multiplicatif indique que si une experience comporte deux étapes indépendantes, la première ayant p issues et la seconde q issues, le nombre total d'issues est p x q. Par extension, pour k étapes avec n1, n2, ..., nk issues respectivement, le total est n1 x n2 x ... x nk.
Le nombre de p-listes (ou p-uplets) d'éléments d'un ensemble a n éléments est n^p si les répétitions sont autorisees. Les arbres de dénombrement permettent de visualiser les choix successifs et de compter les chemins possibles.
Méthode — Choisir le bon outil de dénombrement
- Identifier si l'ordre compte ou non dans le probleme
- déterminer si les répétitions sont autorisees
- Avec répétition + ordre : p-listes ($n^p $)
- Sans répétition + ordre : arrangements $A(n,p)$
- Sans répétition + sans ordre : combinaisons $C(n,p)$
Exemple : Combien de codes PIN a 4 chiffres (0-9) sont possibles ?
- Identifier le type : On choisit 4 chiffres parmi 10, l'ordre compte et les répétitions sont autorisees : c'est une p-liste.
- Appliquer la formule : p-listes de 4 parmi 10
⚠️ Attention : Ne pas confondre le principe additif (OU = additionner) et le principe multiplicatif (ET = multiplier). Le principe additif s'applique uniquement a des ensembles disjoints.
2. Permutations et factorielle
Une permutation d'un ensemble E a n éléments est un arrangement ordonne de tous les éléments de E. Le nombre de permutations de n éléments est n! = n x (n-1) x (n-2) x ... x 2 x 1 (factorielle de n).
Par convention, 0! = 1. Les premières valeurs de la factorielle sont : 1! = 1, 2! = 2, 3! = 6, 4! = 24, 5! = 120, 6! = 720, 7! = 5040, 10! = 3 628 800.
La factorielle croit tres rapidement : n! est de l'ordre de (n/e)^n x sqrt(2*pi*n) (formule de Stirling). Les permutations interviennent dans de nombreux problemes : ordre d'arrivee d'une course, classement de livres sur une etagere, distribution de cartes.
Méthode — Calculer le nombre d'anagrammes
- Compter le nombre total de lettres $n $
- Identifier les lettres qui se repetent et compter leurs occurrences
- Si toutes les lettres sont distinctes : $n!$
- Si des lettres se repetent :$\frac{n!}{n_1! \times n_2! \times ... \times n_k!}$
Exemple : Combien d'anagrammes du mot ANANAS ?
- Compter les lettres : ANANAS a 6 lettres : A apparait 3 fois, N apparait 2 fois, S apparait 1 fois.
- Appliquer la formule : Permutations avec répétitions
⚠️ Attention : Ne pas oublier $0! = 1$. C'est une convention nécessaire pour la cohérence des formules (par exemple $C(n,0) = \frac{n!}{0!n!} = 1$).
3. Arrangements
Un arrangement de p éléments parmi n (p <= n) est un choix ordonne de p éléments parmi n éléments distincts, sans répétition. Le nombre d'arrangements est note A(n,p) = n! / (n-p)!.
On peut aussi écrire A(n,p) = n x (n-1) x (n-2) x ... x (n-p+1), soit le produit de p facteurs consecutifs decroissants a partir de n. Les arrangements interviennent quand l'ordre des éléments choisis compte et qu'il n'y a pas de répétition.
La relation entre arrangements et permutations : A(n,n) = n! (une permutation est un arrangement de n parmi n).
Méthode — Calculer un arrangement
- vérifier que l'ordre compte et qu'il n'y a pas de répétition
- Identifier $n $ (ensemble total) et $p $ (nombre d'éléments choisis)
- Calculer le produit de $p $ facteurs decroissants a partir de $n $
- Ou utiliser la formule $\frac{n!}{(n-p)!}$
Exemple : Combien de podiums possibles pour une course de 10 athletes ?
- Identifier le type : On choisit 3 athletes parmi 10 dans un ordre precis (1er, 2e, 3e) : c'est un arrangement.
- Calculer : A(10,3) = 10 x 9 x 8
⚠️ Attention : Un arrangement n'est pas une combinaison ! A(10,3) = 720 mais C(10,3) = 120. Le rapport est exactement p! = 3! = 6.
4. Combinaisons et coefficients binomiaux
Une combinaison de p éléments parmi n est un sous-ensemble de p éléments choisis parmi n, sans tenir compte de l'ordre. Le nombre de combinaisons est le coefficient binomial C(n,p) = n! / (p! x (n-p)!).
Proprietes essentielles : C(n,0) = C(n,n) = 1, C(n,1) = C(n,n-1) = n, et la symétrie C(n,p) = C(n,n-p). La relation de Pascal est C(n+1,p+1) = C(n,p) + C(n,p+1). Le triangle de Pascal permet de calculer les coefficients binomiaux de proche en proche.
La relation entre combinaisons et arrangements est A(n,p) = C(n,p) x p!, car un arrangement est une combinaison ordonnee.
Méthode — Calculer C(n,p) efficacement
- Si p > n/2, utiliser la symétrie C(n,p) = C(n,n-p) pour reduire le calcul
- écrire le produit de p facteurs decroissants au numerateur : n x (n-1) x ... x (n-p+1)
- Diviser par p! au dénominateur
- Simplifier avant de multiplier pour eviter les grands nombres
Exemple : Combien de mains de 5 cartes dans un jeu de 52 ?
- Identifier le type : L'ordre des cartes dans la main n'importe pas, pas de répétition : c'est une combinaison.
- Calculer C(52,5) : On utilise la formule simplifiee
⚠️ Attention : C(n,0) = 1 et non 0 : il y a exactement une facon de ne rien choisir (l'ensemble vide). Ne pas confondre C(n,p) (sans ordre) et A(n,p) (avec ordre).
5. La formule du binome de Newton
La formule du binome de Newton donne le developpement de (a + b)^n pour tout entier naturel n : (a + b)^n = somme pour k de 0 a n de C(n,k) x a^(n-k) x b^k.
Cas particuliers importants : (1 + x)^n = somme de C(n,k) x x^k. En posant x = 1 : somme de C(n,k) = 2^n (nombre total de sous-ensembles). En posant a = 1 et b = -1 : somme de (-1)^k x C(n,k) = 0.
Le binome de Newton permet de developper des expressions, de trouver des coefficients specifiques et de démontrer des identites combinatoires.
Méthode — Developper $(a+b)^n $ avec le binome de Newton
- Identifier $n $,$a $ et $b $ dans l'expression
- Lire les coefficients $C(n,k)$ sur la $n $-ieme ligne du triangle de Pascal
- écrire chaque terme :$C(n,k) \times a^{n-k} \times b^k $
- Simplifier si nécessaire
Exemple : Developper $(2x + 3)^3$.
- Identifier : $a = 2x $,$b = 3$,$n = 3$. Les coefficients sont $C(3,0)=1, C(3,1)=3, C(3,2)=3, C(3,3)=1$.
- Developper : $(2x+3)^3 = 1 \times (2x)^3 + 3 \times (2x)^2 \times 3 + 3 \times (2x) \times 9 + 1 \times 27$
⚠️ Attention : Dans $(a+b)^n $, attention a bien elever $a $ ET $b $ aux bonnes puissances. Par exemple dans (2x+3)^3, le terme en k=1 est $C(3,1) \times (2x)^2 \times 3^1 = 3 \times 4x^2 \times 3 = 36x^2$, pas $3 \times 2x^2 \times 3$.
Conclusion
La combinatoire fournit des outils puissants pour le dénombrement : permutations (n!), arrangements (A(n,p)) et combinaisons (C(n,p)). Le binome de Newton relie ces outils a l'algèbre. Ces techniques sont fondamentales pour le calcul des probabilités.
Mots-clés