Compter les chemins : coefficients binomiaux

Énoncé

On considère un schéma de Bernoulli à n épreuves, représenté par un arbre dont chaque chemin est une liste de succès et d'échecs. a) Pour n = 5, combien l'arbre a-t-il de chemins ? Combien de ces chemins comportent exactement 2 succès ? Exprimer ce nombre à l'aide d'un coefficient binomial et le calculer. b) Pour n = 7, combien de chemins comportent exactement 3 succès ? c) Pour n = 10, combien de chemins ne comportent aucun succès ? Combien ne comportent que des succès ? Retrouver ces deux nombres par des coefficients binomiaux. d) Pour n = 5, calculer C(5,k) pour k allant de 0 à 5, et vérifier que leur somme est le nombre total de chemins.

Indice : Un chemin à k succès est entièrement déterminé par les POSITIONS de ses succès : il s'agit de choisir k positions parmi n.

Correction

1. Étape 1 : Tout l'exercice repose sur une correspondance, celle qui fait entrer les coefficients binomiaux dans la loi binomiale : un chemin à k succès, c'est un choix de k positions parmi n. Le chemin SS̅SS̅ S̅, par exemple, correspond aux positions {1 ; 3}. Coefficient binomial (chapitre Combinatoire) : C(n,k) est le nombre de parties à k éléments d'un ensemble à n éléments : C(n,k) = (n!)/(k! (n-k)!) = (n × (n-1) × ⋯ × (n-k+1))/(k!) 👉 La seconde écriture — k facteurs décroissants à partir de n, divisés par k! — évite d'écrire des factorielles énormes pour les simplifier aussitôt.
2. Étape 2 : a) Chaque épreuve a 2 issues et il y a 5 épreuves : l'arbre a 2⁵ = 32 chemins. Un chemin à exactement 2 succès est déterminé par les positions de ses deux succès parmi les cinq épreuves. Il y en a C(5,2) = (5 × 4)/(2 × 1) = 10 On peut d'ailleurs les énumérer : {1;2}, {1;3}, {1;4}, {1;5}, {2;3}, {2;4}, {2;5}, {3;4}, {3;5}, {4;5} — dix paires, sans ordre, puisque {1;3} et {3;1} désignent le même chemin.

   C(5,2) = 10

3. Étape 3 : b) Trois positions de succès à choisir parmi sept : C(7,3) = (7 × 6 × 5)/(3 × 2 × 1) = 210/6 = 35 Il y a 35 chemins à exactement 3 succès sur les 2⁷ = 128 chemins de l'arbre.

   C(7,3) = 35

4. Étape 4 : c) Un seul chemin ne comporte aucun succès : celui qui ne passe que par des échecs. Un seul ne comporte que des succès. Les coefficients binomiaux le retrouvent, avec la convention 0! = 1 : C(10,0) = (10!)/(0! × 10!) = 1 — il n'y a qu'une façon de ne choisir aucune position ; C(10,10) = (10!)/(10! × 0!) = 1 — une seule façon de les choisir toutes.

   C(10,0) = C(10,10) = 1

5. Étape 5 : d) Pour n = 5 : | k | 0 | 1 | 2 | 3 | 4 | 5 | |:---:|:---:|:---:|:---:|:---:|:---:|:---:| | C(5,k) | 1 | 5 | 10 | 10 | 5 | 1 | 1 + 5 + 10 + 10 + 5 + 1 = 32 = 2⁵ ✓ Ce n'est pas une coïncidence : chacun des 32 chemins comporte un certain nombre k de succès, entre 0 et 5, et il est compté une fois et une seule, dans la colonne de son k. 👉 On voit aussi la symétrie C(5,k) = C(5,5-k) : choisir les positions des succès revient à choisir celles des échecs.
6. Étape 6 : L'erreur classique : Diviser par k! seulement, en oubliant le (n-k)! : on trouverait (5!)/(2!) = 60 au lieu de 10, soit six fois trop : il manque la division par (n-k)! = 3! = 6. Le contrôle « C(n,k) ne dépasse jamais 2ⁿ » le refuse aussitôt, puisque 60 > 2⁵ = 32. Autre piège : poser 0! = 0. La convention est 0! = 1, sans quoi C(n,0) ne serait pas défini. À retenir : Dans un arbre à n niveaux, le nombre de chemins à k succès est C(n,k) : c'est le facteur qui apparaîtra dans P(X = k). Contrôles gratuits : C(n,k) est un entier, symétrique en k et n - k, et la somme d'une ligne vaut 2ⁿ.