Terminale — Programme officiel (BO 2019) · Math@mine
Dans une classe de 35 élèves, on veut elire un delegue titulaire et un delegue suppleant. De combien de facons peut-on former ce binome ? Et si l’on souhaite simplement choisir 2 delegues sans distinction de role ?
En 1654, Blaise Pascal publie le Traité du triangle arithmétique, où il organise les coefficients binomiaux dans un tableau triangulaire. Mais ce triangle était déjà connu des mathématiciens chinois (Yang Hui, XIIIe siècle) et perses (Al-Karaji, Xe siècle). La correspondance entre Pascal et Fermat sur les jeux de hasard a aussi posé les bases du calcul des probabilités.
Lire l’article : Le triangle de Pascal — voyage à travers les civilisations →
Sur un quadrillage 4 x 3, on part du coin inférieur gauche pour atteindre le coin supérieur droit en se deplacant uniquement vers la droite ou vers le haut. Combien de chemins différents existe-t-il ?
Soient \(A\) et \(B\) deux ensembles finis disjoints, de cardinaux respectifs \(p\) et \(q\). Notons les éléments :
\(A = \{a_1, a_2, \ldots, a_p\}\), \(B = \{b_1, b_2, \ldots, b_q\}.\)
Comme \(A \cap B = \varnothing\), tous les \(a_i\) sont distincts des \(b_j\). La liste :
\(a_1, a_2, \ldots, a_p, b_1, b_2, \ldots, b_q\)
énumère les éléments de \(A \cup B\) sans répétition. Elle contient \(p + q\) termes distincts, donc \(\text{card}(A \cup B) = p + q = \text{card}(A) + \text{card}(B)\).
Cas non disjoint. Si \(A \cap B \neq \varnothing\), on compte deux fois les éléments communs. La formule générale est :
\(\text{card}(A \cup B) = \text{card}(A) + \text{card}(B) - \text{card}(A \cap B).\) ∎
Notons \(E_1 = \{x_1, \ldots, x_p\}\) l’ensemble des choix pour la première étape et, pour chaque \(x_i\), notons \(E_2(x_i) = \{y_{i,1}, \ldots, y_{i,q}\}\) l’ensemble des \(q\) choix possibles à la seconde étape (sa taille \(q\) est supposée indépendante de \(x_i\)).
Une opération complète est un couple \((x_i, y_{i,j})\) où \(1 \le i \le p\) et \(1 \le j \le q\). L’ensemble total des opérations est :
\(E = \bigcup_{i=1}^{p} \{(x_i, y_{i,1}), (x_i, y_{i,2}), \ldots, (x_i, y_{i,q})\}.\)
Ce sont \(p\) « tranches » disjointes (une par choix de \(x_i\)), chacune contenant \(q\) couples. D’après le principe additif appliqué \(p\) fois :
\(\text{card}(E) = \underbrace{q + q + \cdots + q}_{p\text{ termes}} = p \times q.\) ∎
Un menu propose 3 entrees et 5 plats. Le nombre de menus différents (une entree puis un plat) est \(3 \times 5 = 15\).
Calculer \(\dfrac{8!}{6!}\).
\(\dfrac{8!}{6!} = \dfrac{8 \times 7 \times 6!}{6!} = 8 \times 7 = 56\).
Principe : on développé la factorielle du numérateur jusqu’à retrouver celle du dénominateur, puis on simplifie.
Par le principe multiplicatif (section 1). On place les \(n\) éléments un par un :
Total : \(n \times (n-1) \times (n-2) \times \cdots \times 1 = n!\). ∎
Les permutations de \(\{a, b, c\}\) sont : \(abc\), \(acb\), \(bac\), \(bca\), \(cab\), \(cba\), soit \(3! = 6\) permutations.
Par le principe multiplicatif. On choisit les \(k\) éléments un par un, dans l’ordre :
Total : \(n(n-1)(n-2)\cdots(n-k+1)\). C’est un produit de \(k\) facteurs consecutifs.
Pour voir que c’est \(\dfrac{n!}{(n-k)!}\), on ecrit :
\(n(n-1)\cdots(n-k+1) = \dfrac{n!}{(n-k)!}\)
car \(n! = \underbrace{n(n-1)\cdots(n-k+1)}_{k \text{ facteurs}} \times (n-k)!\). ∎
Elire un delegue titulaire et un suppleant parmi 35 élèves : l’ordre compte (titulaire puis suppleant).
\(A_{35}^2 = 35 \times 34 = 1\,190\) binomes possibles.
On peut construire un arrangement de \(k\) éléments parmi \(n\) en deux étapes :
Par le principe multiplicatif : \(A_n^k = \binom{n}{k} \times k!\).
En inversant : \(\binom{n}{k} = \dfrac{A_n^k}{k!} = \dfrac{n!}{k!\,(n-k)!}\). On retrouve la formule du coefficient binomial. ∎
Choisir 2 delegues (sans role distinct) parmi 35 élèves :
\(\binom{35}{2} = \dfrac{35 \times 34}{2} = 595\) groupes possibles.
Par la formule : \(\binom{n}{n-k} = \dfrac{n!}{(n-k)!\,(n-(n-k))!} = \dfrac{n!}{(n-k)!\,k!} = \binom{n}{k}\). ∎
Interprétation : choisir \(k\) éléments a prendre, c’est la même chose que choisir \(n-k\) éléments a laisser.
Argument combinatoire. Un ensemble a \(n\) éléments possede \(2^n\) sous-ensembles au total (chaque élément est pris ou non : 2 choix par élément, soit \(2^n\) par le principe multiplicatif).
Par ailleurs, on peut classer ces sous-ensembles selon leur taille \(k\) : il y en a \(\binom{n}{k}\) de taille \(k\). Comme tout sous-ensemble a une taille unique entre 0 et \(n\) :
\(\displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n\). ∎
On retrouvera ce résultat comme cas particulier du binome de Newton (\(a = b = 1\)) en section 6.
Calculer \(\binom{8}{3}\).
\(\binom{8}{3} = \dfrac{8!}{3!\,5!} = \dfrac{8 \times 7 \times 6}{3 \times 2 \times 1} = \dfrac{336}{6} = 56\).
On veut choisir \(k\) éléments parmi \(n+1\). Fixons le dernier élément (le \((n+1)\)e). Il y a deux cas :
Ces deux cas sont disjoints et exhaustifs. Par le principe additif :
\(\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}\). ∎
On part du membre de droite et on met au même dénominateur :
\(\binom{n}{k-1} + \binom{n}{k} = \dfrac{n!}{(k-1)!(n-k+1)!} + \dfrac{n!}{k!(n-k)!}\)
Le dénominateur commun est \(k!(n-k+1)!\). On multiplie :
\(= \dfrac{n! \cdot k}{k!(n-k+1)!} + \dfrac{n! \cdot (n-k+1)}{k!(n-k+1)!} = \dfrac{n!\,(k + n - k + 1)}{k!(n-k+1)!}\)
\(= \dfrac{n!\,(n+1)}{k!(n+1-k)!} = \dfrac{(n+1)!}{k!(n+1-k)!} = \binom{n+1}{k}\). ∎
| \(n\) | \(k=0\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) |
|---|---|---|---|---|---|---|
| 0 | 1 | |||||
| 1 | 1 | 1 | ||||
| 2 | 1 | 2 | 1 | |||
| 3 | 1 | 3 | 3 | 1 | ||
| 4 | 1 | 4 | 6 | 4 | 1 | |
| 5 | 1 | 5 | 10 | 10 | 5 | 1 |
Pour trouver \(\binom{5}{2}\), on lit la ligne \(n=5\), colonne \(k=2\) : on obtient 10.
Verification : \(\binom{5}{2} = \dfrac{5!}{2!\,3!} = \dfrac{120}{2 \times 6} = 10\). ✓
On note \(\mathcal{P}(n)\) la propriété : \((a + b)^n = \displaystyle\sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k\).
Initialisation (\(n = 0\)) : \((a+b)^0 = 1\) et \(\displaystyle\sum_{k=0}^{0} \binom{0}{0} a^0 b^0 = 1\). ✓
Heredite. Supposons \(\mathcal{P}(n)\) vraie. Alors :
\((a+b)^{n+1} = (a+b) \cdot (a+b)^n = (a+b)\displaystyle\sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k\)
En distribuant :
\(= \displaystyle\sum_{k=0}^{n} \binom{n}{k} a^{n+1-k} b^k \;+\; \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^{k+1}\)
Dans la seconde somme, on pose \(j = k+1\) (donc \(j\) va de 1 à \(n+1\)) :
\(= \displaystyle\sum_{k=0}^{n} \binom{n}{k} a^{n+1-k} b^k \;+\; \sum_{j=1}^{n+1} \binom{n}{j-1} a^{n+1-j} b^{j}\)
On isole le terme \(k=0\) de la première somme (\(a^{n+1}\)) et le terme \(j=n+1\) de la seconde (\(b^{n+1}\)), puis on regroupe les termes restants (\(k\) de 1 à \(n\)) :
\(= a^{n+1} + \displaystyle\sum_{k=1}^{n}\left[\binom{n}{k} + \binom{n}{k-1}\right] a^{n+1-k} b^k + b^{n+1}\)
Par la relation de Pascal (demontree en section 5) : \(\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}\). Donc :
\((a+b)^{n+1} = \displaystyle\sum_{k=0}^{n+1} \binom{n+1}{k} a^{n+1-k} b^k\)
C’est \(\mathcal{P}(n+1)\). ✓
Conclusion : par le principe de récurrence, \(\mathcal{P}(n)\) est vraie pour tout \(n \in \mathbb{N}\). ∎
\((a+b)^3 = \binom{3}{0}a^3 + \binom{3}{1}a^2b + \binom{3}{2}ab^2 + \binom{3}{3}b^3 = a^3 + 3a^2b + 3ab^2 + b^3\)
\((1+x)^4 = 1 + 4x + 6x^2 + 4x^3 + x^4\)
On retrouve les coefficients de la 4e ligne du triangle de Pascal : 1, 4, 6, 4, 1.
On applique la formule du binôme \((a+b)^n = \displaystyle\sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k\).
Première identité (\(a = b = 1\)).
\(2^n = (1+1)^n = \displaystyle\sum_{k=0}^{n} \binom{n}{k}\cdot 1^{n-k}\cdot 1^k = \sum_{k=0}^{n}\binom{n}{k}.\)
Interprétation combinatoire. \(2^n\) compte les parties d’un ensemble à \(n\) éléments (chaque élément est « choisi » ou non). En groupant ces parties par taille, on retrouve \(\sum_k \binom{n}{k}\) : le nombre de parties de taille \(k\).
Seconde identité (\(a = 1\), \(b = -1\), \(n \ge 1\)).
\(0 = 0^n = (1 + (-1))^n = \displaystyle\sum_{k=0}^{n} \binom{n}{k}\cdot 1^{n-k}\cdot (-1)^k = \sum_{k=0}^{n}(-1)^k \binom{n}{k}.\)
Interprétation. Pour \(n \ge 1\), un ensemble à \(n\) éléments a autant de parties de taille paire que de taille impaire. ∎
On pose \(a = 2x\) et \(b = -3\). Le terme général est \(\binom{4}{k}(2x)^{4-k}(-3)^k\).
Donc \((2x-3)^4 = 16x^4 - 96x^3 + 216x^2 - 216x + 81\).
Avec distinction de role (arrangement) : On choisit un titulaire parmi 35 élèves, puis un suppleant parmi les 34 restants. Le nombre de binomes possibles est \(A_{35}^2 = 35 \times 34 = 1\,190\).
Sans distinction de role (combinaison) : On choisit 2 delegues parmi 35 sans ordre. Le nombre de groupes possibles est \(\binom{35}{2} = \dfrac{35 \times 34}{2} = 595\).
Le nombre de possibilites est différent car dans le premier cas, l’ordre compte (titulaire/suppleant sont des roles différents), tandis que dans le second cas, les deux delegues ont le même statut. Chaque combinaison correspond à \(2! = 2\) arrangements, d’ou \(1\,190 = 2 \times 595\).
Il faut effectuer 7 déplacements au total : 4 vers la droite (D) et 3 vers le haut (H). Le nombre de chemins est le nombre de facons de placer les 3 déplacements H parmi les 7 positions :
\(\binom{7}{3} = \dfrac{7!}{3!\,4!} = \dfrac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35\) chemins.
| Notion | Formule | Exemple |
|---|---|---|
| Factorielle | \(n! = 1 \times 2 \times \cdots \times n\) | \(5! = 120\) |
| Arrangement | \(A_n^k = \dfrac{n!}{(n-k)!}\) | \(A_5^2 = 20\) |
| Combinaison | \(\binom{n}{k} = \dfrac{n!}{k!(n-k)!}\) | \(\binom{5}{2} = 10\) |
| Relation de Pascal | \(\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}\) | \(\binom{5}{2} = \binom{4}{1} + \binom{4}{2}\) |
| Binome de Newton | \((a+b)^n = \displaystyle\sum_{k=0}^n \binom{n}{k}a^{n-k}b^k\) | \((1+x)^3 = 1+3x+3x^2+x^3\) |
Combinatoire et dénombrement : teste d’abord ton intuition.
« \(n! = n \times n\), c’est-à-dire le carré de \(n\). »
Cette affirmation est-elle correcte ?
Faux. \(n! = 1 \times 2 \times 3 \times \cdots \times n\), c’est le produit de tous les entiers de 1 à \(n\). Par exemple \(4! = 24\), alors que \(4 \times 4 = 16\).
Mini-test : que vaut \(6!\) ?
« Un arrangement et une combinaison, c’est la même chose. »
Cette affirmation est-elle correcte ?
Faux. Un arrangement tient compte de l'ordre, pas une combinaison. \(A_n^k = k! \times \binom{n}{k}\). Par exemple, choisir un president puis un tresorier parmi 5 personnes : \(A_5^2 = 20\). Choisir un groupe de 2 : \(\binom{5}{2} = 10\).
Mini-test : choisir 3 lettres parmi A, B, C, D sans ordre. Combien ?
« \(0! = 0\). »
Cette affirmation est-elle correcte ?
Faux. Par convention, \(0! = 1\). C’est indispensable pour que les formules de combinaisons fonctionnent : \(\binom{n}{0} = \frac{n!}{0! \cdot n!} = 1\).
Mini-test : que vaut \(\binom{5}{0}\) ?
« \(\binom{n}{0} = 0\) car on ne choisit rien. »
Cette affirmation est-elle correcte ?
Faux. \(\binom{n}{0} = 1\) : il y a exactement une facon de ne choisir aucun élément (l’ensemble vide). De même \(\binom{n}{n} = 1\).
Mini-test : \(\binom{100}{0} + \binom{100}{100} = ?\)
« \((a+b)^n = a^n + b^n\). »
Cette affirmation est-elle correcte ?
Faux. C’est une erreur tres frequente ! \((a+b)^2 = a^2 + 2ab + b^2 \neq a^2 + b^2\). La formule correcte est le binome de Newton : \((a+b)^n = \sum_{k=0}^n \binom{n}{k} a^{n-k}b^k\).
Mini-test : \((1+1)^3 = ?\)
« \(\binom{n}{k} = \binom{n}{n-k}\) pour tout \(0 \leq k \leq n\). »
Cette affirmation est-elle correcte ?
C’est vrai ! Choisir \(k\) éléments parmi \(n\) revient à choisir les \(n-k\) éléments qu’on ne prend pas. Par exemple \(\binom{10}{3} = \binom{10}{7} = 120\).
Mini-test : \(\binom{8}{2} = ?\)