Combinaisons en dénombrement : la formule n!/(k!(n − k)!) et le triangle de Pascal

Le dénombrement ouvre la partie « Algèbre et géométrie » du programme de spécialité de terminale (BO spécial n° 8 du 25 juillet 2019, section « Combinatoire et dénombrement »). Le programme demande deux démonstrations, faites ici : la relation de Pascal, par le calcul et par une méthode combinatoire, et l'égalité qui dit que la somme des (nk) pour k de 0 à n vaut 2ⁿ, par dénombrement. Dans tout l'article, n et k sont des entiers naturels et E est un ensemble fini à n éléments.

Trois objets à ne pas confondre avant de compter

Choisir k éléments dans E peut vouloir dire trois choses. Deux questions tranchent : l'ordre compte-t-il ? un même élément peut-il revenir ?

Objet	Ordre	Répétition	Nombre	Exemple
k-uplet (ou k-liste) d'éléments de E	oui	oui	nᵏ	un code de 4 chiffres : 10⁴
k-uplet d'éléments distincts	oui	non	n(n − 1)…(n − k + 1) = n!/(n − k)!	délégué puis suppléant dans une classe de 30 : 30 × 29 = 870
combinaison (partie à k éléments)	non	non	(nk) = n!/(k!(n − k)!)	3 élèves pour une même tâche : (303) = 4 060

Le programme dit « k-uplets d'éléments distincts » plutôt qu'« arrangements ». Les permutations de E sont les n-uplets d'éléments distincts : il y en a n!.

D'où vient la division par k!

On compte les k-uplets d'éléments distincts de deux façons. Directement : n choix pour le premier élément, n − 1 pour le deuxième, jusqu'à n − k + 1 pour le k-ième, soit n(n − 1)…(n − k + 1). En deux étapes : on choisit la partie à k éléments, de (nk) façons, puis l'ordre de ses k éléments, de k! façons ; chaque k-uplet est obtenu exactement une fois. Donc (nk) × k! = n(n − 1)…(n − k + 1), et pour 0 ≤ k ≤ n, (nk) = n(n − 1)…(n − k + 1)/k! = n!/(k!(n − k)!), avec 0! = 1.

Avec E = {a, b, c, d} et k = 2 : 4 × 3 = 12 couples d'éléments distincts, chaque partie comme {a, b} correspondant à deux couples, donc 12/2 = 6 parties.

Valeurs à connaître : (n0) = 1 (la partie vide), (n1) = n, (n2) = n(n − 1)/2 (le nombre de paires). La symétrie (nk) = (nn−k) se justifie sans calcul : choisir les k éléments qu'on garde revient à choisir les n − k qu'on laisse. C'est pourquoi (3227) se calcule comme (325).

Pascal et 2ⁿ : les deux démonstrations du programme

Relation de Pascal. Pour n ≥ 2 et 1 ≤ k ≤ n − 1 : (nk) = (n−1k−1) + (n−1k).

Par une méthode combinatoire. Fixons un élément a de E. Une partie de E à k éléments contient a, ou ne le contient pas, et ces deux cas sont disjoints. Celles qui contiennent a sont déterminées par les k − 1 autres éléments, choisis parmi les n − 1 éléments différents de a : il y en a (n−1k−1). Celles qui ne contiennent pas a sont des parties à k éléments de E privé de a : il y en a (n−1k). Le principe additif donne la relation.

Par le calcul. On réduit au même dénominateur k!(n − k)! :

(n−1k−1) + (n−1k) = (n − 1)!/((k − 1)!(n − k)!) + (n − 1)!/(k!(n − 1 − k)!) = (n − 1)! × k/(k!(n − k)!) + (n − 1)! × (n − k)/(k!(n − k)!) = (n − 1)! × n/(k!(n − k)!) = n!/(k!(n − k)!).

On a utilisé k! = k × (k − 1)! et (n − k)! = (n − k) × (n − k − 1)!, ce qui demande k ≥ 1 et n − k ≥ 1 : c'est là que servent les hypothèses sur k.

Un ensemble à n éléments a 2ⁿ parties. Numérotons les éléments de E : e₁, …, eₙ. À chaque partie A de E, on associe le n-uplet (c₁, …, cₙ) de {0 ; 1} où cᵢ vaut 1 si eᵢ appartient à A et 0 sinon. C'est une bijection, et il y a 2ⁿ tels n-uplets par le principe multiplicatif. Classons maintenant ces mêmes parties selon leur nombre d'éléments k, de 0 à n : les classes sont disjointes et la classe k contient (nk) parties. Le principe additif donne (n0) + (n1) + … + (nn) = 2ⁿ. Une suite de n épreuves succès/échec est un tel n-uplet, et le nombre de suites à k succès est (nk) : c'est ce qui fonde la loi binomiale. Le même résultat se démontre aussi par récurrence.

La démarche sur une copie de devoir surveillé

1. Décrire un résultat en une phrase : « une main est une partie à 5 éléments de l'ensemble des 32 cartes ».
2. Décider si l'ordre compte et si les répétitions sont permises.
3. Étapes successives : multiplier (principe multiplicatif) ; cas qui ne se recouvrent pas : additionner (principe additif).
4. Pour « au moins un », passer par le complémentaire.
5. Conclure par une phrase avec le nombre écrit en entier.

Exemple 1 · Mains de 5 cartes et as

Énoncé. On tire simultanément 5 cartes d'un jeu de 32 cartes, qui contient 4 as. Combien de mains sont possibles ? Combien contiennent exactement 2 as ? Combien contiennent au moins un as ?

Rédaction. Une main est une partie à 5 éléments de l'ensemble des 32 cartes : il y en a (325) = 201 376. Une main à exactement 2 as se construit en choisissant 2 as parmi les 4, puis 3 cartes parmi les 28 qui ne sont pas des as : (42) × (283) = 6 × 3 276 = 19 656 mains. Pour « au moins un as », on compte le complémentaire : les mains sans as sont les parties à 5 éléments des 28 autres cartes, au nombre de (285) = 98 280. Il y a donc 201 376 − 98 280 = 103 096 mains contenant au moins un as.

Exemple 2 · Les chemins dans un quadrillage

Énoncé. Sur un quadrillage, on va du point (0 ; 0) au point (5 ; 3) en ne faisant que des pas d'une unité vers la droite (D) ou vers le haut (H). Combien de chemins existe-t-il ?

Rédaction. Un chemin est un mot de 8 lettres contenant exactement 5 D et 3 H, et réciproquement chaque tel mot décrit un chemin. Un tel mot est déterminé par les positions de ses 3 lettres H, qui forment une partie à 3 éléments de {1, …, 8}. Il y a donc (83) = 8 × 7 × 6/6 = 56 chemins. Choisir les 5 positions des D donnait (85), le même nombre, par symétrie.

Quand les issues sont équiprobables, une probabilité se calcule ensuite en divisant le nombre de cas favorables par le nombre total de cas, qui est souvent lui-même un coefficient (nk), comme dans l'exercice 2.

Ce que montre le triangle de Pascal

La figure range les (nk) en lignes, de gauche à droite pour k = 0 à n. Le triangle se remplit ligne par ligne, de n = 0 à n = 6, puis les disques et les traits dorés marquent la relation de Pascal : 4 et 6, sur la ligne 4, ont pour somme le 10 placé en dessous, sur la ligne 5. Chaque ligne commence et finit par 1 et se lit de la même façon dans les deux sens (la symétrie). À droite, la somme de chaque ligne vaut 1, 2, 4, 8, …, 64 : c'est 2ⁿ.

Ordre compté en trop, as comptés deux fois : les fautes de dénombrement

• Compter avec l'ordre ce qui n'en a pas. Pour une main, 32 × 31 × 30 × 29 × 28 compte chaque main 5! = 120 fois. Se demander si échanger deux éléments donne un résultat différent.
• Le faux « au moins un ». 4 × (314) (un as, puis 4 cartes quelconques) donne 125 860, plus que le vrai 103 096 : une main à deux as est comptée deux fois. Le complémentaire évite le piège.
• Confondre nᵏ et (nk). (104) = 210 alors que 10⁴ = 10 000.
• Multiplier là où il faut additionner. « Exactement 2 as ou exactement 3 as » : deux cas disjoints qu'on additionne ; « 2 as et 3 autres cartes » : deux choix successifs qu'on multiplie.
• Un résultat de calculatrice sans l'expression. La copie doit montrer (283) avant 3 276.

Trois exercices corrigés sur les combinaisons

Exercice 1 · Quatre coefficients sans calculatrice

Énoncé. Calculer (73), (108) et (202). Combien de poignées de main échangent 15 personnes si chacune serre la main de toutes les autres une fois ?

Correction. (73) = 7 × 6 × 5/(3 × 2 × 1) = 35. Par symétrie, (108) = (102) = 10 × 9/2 = 45. (202) = 20 × 19/2 = 190. Une poignée de main correspond à une paire de personnes, c'est-à-dire une partie à 2 éléments de l'ensemble des 15 personnes : il y en a (152) = 15 × 14/2 = 105.

Exercice 2 · Mots de passe et grille de loto

Énoncé. a) Combien de mots de passe de 6 lettres peut-on former avec les 26 lettres minuscules ? Combien si les 6 lettres doivent être distinctes ? b) Une grille consiste à choisir 5 numéros parmi 49, puis un numéro « chance » parmi 10. Combien de grilles différentes existe-t-il ? c) On joue une grille de 5 numéros. Quelle est la probabilité que exactement 3 d'entre eux fassent partie des 5 numéros tirés au sort ?

Correction. a) Un mot de passe est un 6-uplet de lettres, l'ordre comptant et les répétitions étant permises : 26⁶ = 308 915 776. Avec des lettres distinctes : 26 × 25 × 24 × 23 × 22 × 21 = 165 765 600. b) Les 5 numéros forment une partie à 5 éléments de {1, …, 49} : (495) = 1 906 884 choix, et 10 choix pour le numéro chance, donc 19 068 840 grilles. c) Les tirages des 5 numéros sont équiprobables, au nombre de (495). Ceux qui contiennent exactement 3 des numéros joués s'obtiennent en choisissant 3 numéros parmi les 5 joués et 2 parmi les 44 autres : (53) × (442) = 10 × 946 = 9 460. La probabilité vaut 9 460/1 906 884 ≈ 0,005.

Exercice 3 · Un comité et son président, compté de deux façons

Énoncé. Soient n et k deux entiers avec 1 ≤ k ≤ n. a) Démontrer par le calcul que k(nk) = n(n−1k−1). b) Retrouver ce résultat en comptant, dans un groupe de n personnes, les comités de k membres dont l'un est désigné président. c) En déduire la valeur de la somme des k(nk) pour k allant de 1 à n.

Correction. a) k(nk) = k × n!/(k!(n − k)!) = n!/((k − 1)!(n − k)!) = n × (n − 1)!/((k − 1)!((n − 1) − (k − 1))!) = n(n−1k−1). b) On choisit d'abord le comité, de (nk) façons, puis son président parmi ses k membres : k(nk) possibilités. On peut aussi choisir d'abord le président parmi les n personnes, puis les k − 1 autres membres parmi les n − 1 restantes : n(n−1k−1) possibilités. On a compté le même ensemble de deux façons, d'où l'égalité. c) La somme vaut n × ((n−10) + (n−11) + … + (n−1n−1)) = n × 2ⁿ⁻¹, d'après le nombre de parties d'un ensemble à n − 1 éléments. Pour n = 4 : 1 × 4 + 2 × 6 + 3 × 4 + 4 × 1 = 32 = 4 × 2³.