Terminale specialite
Combinatoire et dénombrement
En Premiere, on a déjà utilisé le principe multiplicatif dans des situations simples. En Terminale, on clarifie les cas : ordre, répétition, choix de positions ou choix d objets.
Version HTML statique du cours. Si JavaScript est actif, MathSups affiche l’expérience interactive avec QCM, exercices guidés et assistant IA.
Rappels et structures de base
En Premiere, on a déjà utilisé le principe multiplicatif dans des situations simples. En Terminale, on clarifie les cas : ordre, répétition, choix de positions ou choix d objets.
Couples, triplets et $k$-uplets
Un couple $(a,b)$ est une liste ordonnee de deux éléments. Plus generalement, un $k$-uplet est une liste ordonnee de $k$ éléments.
L'ordre compte : en général, $(a,b) \ne (b,a)$.
Produit cartesien
Si $A$ et $B$ sont deux ensembles, leur produit cartesien est :
$$A \times B = \{(a,b)\mid a\in A,\; b\in B\}$$
Si $A$ a $m$ éléments et $B$ a $n$ éléments, alors $A\times B$ a $mn$ éléments.
Plus generalement, si $A$ a $n$ éléments, alors $A^k$ contient $n^k$ $k$-uplets.
|A \times B| = |A|\,|B|
Pourquoi $n^k$ ?
Pour former un $k$-uplet avec répétition autorisée dans un ensemble a $n$ éléments, on a $n$ choix a chaque position. Le principe multiplicatif donne donc :
$$n \times n \times \cdots \times n = n^k$$
Permutations, arrangements et combinaisons
La bonne formule depend toujours de deux questions : l'ordre compte-t-il ? la répétition est-elle autorisée ?
Permutation, arrangement, combinaison
Une permutation de $n$ éléments compte les rangements complets : $$n!$$
Un arrangement de $k$ éléments parmi $n$ compte les choix ordonnés sans répétition : $$A_n^k=\frac{n!}{(n-k)!}$$
Une combinaison de $k$ éléments parmi $n$ compte les choix sans ordre : $$\binom{n}{k}=\frac{n!}{k!(n-k)!}$$
Quel outil choisir ?
Le tableau suivant aide a choisir la bonne formule :
| Situation | Formule | Exemple |
|---|---|---|
| ordre compte, répétition autorisée | $n^k$ | code a 4 chiffres avec répétition |
| ordre compte, sans répétition | $A_n^k$ | mot de 4 lettres distinctes |
| ordre ne compte pas, sans répétition | $\binom{n}{k}$ | choisir 4 élèves parmi 12 |
| on range tous les éléments | $n!$ | placer 6 livres différents |
Exemples détaillés
Exemple 1 : des codes de 4 lettres distinctes sur 26 lettres : $$A_{26}^4$$
Exemple 2 : une commission de 4 élèves parmi 12 : $$\binom{12}{4}$$
Exemple 3 : le nombre de suites binaires de longueur $8$ contenant exactement trois $1$ vaut $$\binom{8}{3}$$ car on choisit les positions des $1$.
Parties d'un ensemble et relation de Pascal
Le dénombrement des sous-ensembles est un point important du programme, car il apparait dans beaucoup de raisonnements combinatoires.
Nombre de parties d'un ensemble
Un ensemble a $n$ éléments possede exactement :
$$2^n$$
parties.
Pour chaque élément, on a en effet deux choix : il est présent, ou il ne l est pas.
2^n
Relation de Pascal
Pour $1 \le k \le n$, on a :
$$\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$$
Cette relation se comprend en séparant les groupes de $k$ éléments selon qu ils contiennent ou non un élément fixe.
\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}
Démonstration de la relation de Pascal
Soit $E$ un ensemble de $n+1$ éléments. Fixons un élément $x \in E$. On compte les parties de $k$ éléments de $E$ en les séparant en deux groupes :
- Celles qui contiennent $x$ : il reste à choisir $k-1$ éléments parmi les $n$ autres. Il y en a $\binom{n}{k-1}$.
- Celles qui ne contiennent pas $x$ : on choisit $k$ éléments parmi les $n$ autres. Il y en a $\binom{n}{k}$.
Par le principe additif : $\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}$. $\square$
Somme des coefficients binomiaux : $\sum_{k=0}^n \binom{n}{k} = 2^n$
Démonstration via le binôme de Newton : On applique la formule du binôme avec $a=b=1$ :
$$2^n = (1+1)^n = \sum_{k=0}^{n} \binom{n}{k} 1^{n-k} 1^k = \sum_{k=0}^{n} \binom{n}{k}$$
Interprétation combinatoire : $2^n$ est le nombre total de parties d'un ensemble à $n$ éléments ; en les groupant par taille $k$, on retrouve bien $\sum_{k=0}^n\binom{n}{k} = 2^n$.
\sum_{k=0}^{n}\binom{n}{k}=2^n
Formule du binôme de Newton
La formule du binôme de Newton généralise le développement de $(a+b)^n$. Les coefficients binomiaux apparaissent naturellement comme les coefficients de ce développement.
Formule du binôme de Newton
Pour tout réel (ou complexe) $a$ et $b$, et pour tout entier naturel $n$ :
$$\left(a+b\right)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$$
Autrement dit :
$$(a+b)^n = \binom{n}{0}a^n + \binom{n}{1}a^{n-1}b + \binom{n}{2}a^{n-2}b^2 + \cdots + \binom{n}{n}b^n$$
(a+b)^n = \sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k
Applications usuelles
Développement de $(1+x)^4$ :
$$(1+x)^4 = 1 + 4x + 6x^2 + 4x^3 + x^4$$
car $\binom{4}{0}=1,\ \binom{4}{1}=4,\ \binom{4}{2}=6,\ \binom{4}{3}=4,\ \binom{4}{4}=1$.
Développement de $(a-b)^3$ :
$$(a-b)^3 = a^3 - 3a^2b + 3ab^2 - b^3$$
Les signes alternent car $b$ est remplacé par $(-b)$.
Somme de tous les coefficients : En posant $a=b=1$ dans la formule, on retrouve $\displaystyle\sum_{k=0}^n\binom{n}{k}=2^n$.
QCM du chapitre
-
Question 1. Combien de sous-ensembles possede un ensemble a 5 éléments ?
- A. $10$
- B. $25$
- C. $32$
- D. $120$
Réponse. C. $32$
Explication. On utilisé $2^n$, donc ici $2^5=32$.
-
Question 2. Former un code a 3 chiffres distincts parmi 10 chiffres correspond a :
- A. $10^3$
- B. $A_{10}^3$
- C. $\binom{10}{3}$
- D. $3!$
Réponse. B. $A_{10}^3$
Explication. L'ordre compte et il n y a pas répétition.
-
Question 3. Choisir une commission de 3 élèves parmi 10 correspond a :
- A. une permutation
- B. un arrangement
- C. une combinaison
- D. un produit cartesien
Réponse. C. une combinaison
Explication. L'ordre ne compte pas : on choisit seulement un groupe.
Exercices guidés
Exercice 1. Compter des suites binaires
\binom{10}{4}
-
Étape 1. Identifier ce qu'on choisit.
On choisit les positions des quatre chiffres $1$. Les autres positions seront automatiquement occupees par des $0$. -
Étape 2. Compter ces choix.
Il y a donc $$\binom{10}{4}=210$$ suites possibles.\binom{10}{4}=210
Exercice 2. Compter des parties
2^8 \text{ et } \binom{8}{3}
-
Étape 1. Compter toutes les parties.
Le nombre total de parties est $$2^8=256.$$2^8=256
-
Étape 2. Compter les parties a 3 éléments.
On choisit 3 éléments parmi 8, donc il y en a $$\binom{8}{3}=56.$$\binom{8}{3}=56
À retenir
- Le produit cartesien vérifier $|A\times B|=|A|\,|B|$.
- Si un ensemble a $n$ éléments, alors $A^k$ contient $n^k$ $k$-uplets.
- Permutation de $n$ éléments : $n!$.
- Arrangement de $k$ éléments parmi $n$ : $A_n^k=\dfrac{n!}{(n-k)!}$.
- Combinaison de $k$ éléments parmi $n$ : $\binom{n}{k}=\dfrac{n!}{k!(n-k)!}$.
- Pour choisir la bonne formule, on demande : l'ordre compte-t-il ? la répétition est-elle autorisée ?
- Un ensemble a $n$ éléments possede $2^n$ parties.
- Relation de Pascal : $\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$.
- Ordre compte + répétition autorisée : $n^k$.
- Ordre compte + sans répétition : $A_n^k$.
- Ordre ne compte pas + sans répétition : $\binom{n}{k}$.
- Symétrie : $\binom{n}{k}=\binom{n}{n-k}$.
- Pour compter des sous-ensembles de taille $k$, on pense directement au coefficient binomial.
- Si les cas sont disjoints, on additionne ; si l'on remplit des positions successives, on multiplie.
- Dans un arbre de choix, chaque branche complete représente un cas possible a compter.