Fiche à trous · Terminale · Mathématiques

Dénombrement — k-uplets, permutations, combinaisons

Complétez de mémoire, puis vérifiez avec la page de corrigé.

Combien de codes à quatre chiffres, de podiums, de mains de cinq cartes ? Dénombrer, c'est compter sans tout écrire, en reconnaissant d'abord l'objet compté. Si l'ordre compte, on compte des $k$ -uplets : $n^{k}$ avec répétitions, $n (n - 1) \dots (n - k + 1)$ sans répétition ; si l'ordre ne compte pas, on compte des parties à $k$ éléments : $(k n)$ .

Ensembles, k-uplets et principes de comptage

Définition — ensembles, k-uplets, produit cartésien :

Propriété

Dénombrer avec les deux principes

Exemple

Un mot de passe compte 4 caractères, chacun une lettre minuscule (26 possibles) ou un chiffre (10 possibles). Combien y en a-t-il ? Combien contiennent au moins un chiffre ?

Résultat :

Piège

« Au moins un chiffre : 4 places pour le chiffre, 10 chiffres, puis $3 6^{3}$ pour le reste, soit $4 \times 10 \times 3 6^{3} = 1866240$ . »

devant « au moins un », passer au complémentaire, ou découper en cas disjoints : exactement 1, 2, 3 ou 4 chiffres.

Les parties d'un ensemble

Propriété

10.

Exemple

Une pizzeria propose 6 garnitures, à choisir librement. Combien de pizzas différentes ? Combien avec au moins une garniture ?

Résultat :

Piège

« Un ensemble à 6 éléments a $2 \times 6 = 12$ parties », ou oublier $\emptyset$ et $E$ .

contrôler sur ${a, b}$ : $\emptyset$ , ${a}$ , ${b}$ , ${a, b}$ , soit $2^{2} = 4$ parties.

Listes d'éléments distincts, permutations, factorielle

Définition — factorielle :

Propriété

16.

Tirer k objets parmi n, un par un

Exemple

Huit nageurs disputent une finale. Combien de podiums (or, argent, bronze) sont possibles ? De combien de façons peut-on attribuer les 8 couloirs aux 8 nageurs ?

Résultat :

Piège

« Codes de 4 chiffres tous différents : $1 0^{4} = 10000$ . »

à chaque rang, se demander combien de choix restent.

Combinaisons et coefficients binomiaux

Définition — combinaison :

22.

Propriété

Exemple

Dans une classe de 12 filles et 10 garçons, on choisit 3 élèves pour un conseil, sans fonction distincte. Combien de choix ? Combien avec exactement 2 filles ?

Résultat :

Dénombrer un tirage simultané

Piège

« Mains de 3 cartes d'un jeu de 32 : $32 \times 31 \times 30 = 29760$ . »

un tirage simultané se compte avec $(k n)$ .

Relation et triangle de Pascal

Propriété

31.

Propriété

Construire le triangle de Pascal

Exemple

La ligne 6 du triangle est 1, 6, 15, 20, 15, 6, 1. Écrire la ligne 7, puis donner le nombre de parties à 3 éléments d'un ensemble à 7 éléments.

Résultat :

38.

Piège

Écrire $(k n) + (k + 1 n) = (k n + 1)$ , ou ajouter deux coefficients de lignes différentes.

tester sur le triangle : $(0 2) + (1 2) = 1 + 2 = 3 = (1 3)$ .

L'ordre compte-t-il ? Les répétitions sont-elles permises ?
« Au moins un » : complémentaire, ou cas disjoints ?
Le même nombre de choix à chaque étape, quels que soient les précédents ?
Un contrôle sur un petit cas, par un arbre ou une liste ?

Corrigé · à détacher

Dénombrement — k-uplets, permutations, combinaisons

1. Le nombre d'éléments d'un ensemble fini $E$ est son cardinal, $card (E)$ . Une partie $A$ de $E$ ( $A \subset E$ ) est un ensemble dont tous les éléments sont dans $E$  ; $\emptyset$ et $E$ en sont deux. La réunion $A \cup B$ , l'intersection $A \cap B$ et le complémentaire $\overline{A} = E ∖ A$ s'emploient comme en probabilités ; $A$ et $B$ sont disjoints si $A \cap B = \emptyset$ . Pour des ensembles quelconques $A$ et $B$ , un couple $(a, b)$ est formé d'un élément $a$ de $A$ puis d'un élément $b$ de $B$ : l'ordre compte, $(1, 2) \neq = (2, 1)$ , et les répétitions sont permises, $(1, 1)$ est un couple. Le produit cartésien $A \times B$ est l'ensemble de ces couples. De même, $A \times B \times C$ est l'ensemble des triplets, $A_{1} \times \dots \times A_{k}$ celui des $k$ -uplets (ou $k$ -listes), et $A^{k}$ celui des $k$ -uplets d'éléments de $A$ : $R^{2}$ est l'ensemble des couples de réels.
2. Principes additif et multiplicatif (admis). Si $A_{1}, \dots, A_{p}$ sont finis et deux à deux disjoints, le cardinal de leur réunion est la somme de leurs cardinaux ; ainsi $card (\overline{A}) = card (E) - card (A)$ . Le cardinal d'un produit cartésien est le produit des cardinaux ; en particulier, si $card (E) = n$ , il y a $n^{k}$ $k$ -uplets d'éléments de $E$ . Ce principe vaut pour des choix successifs : si le 1^er choix offre $n_{1}$ possibilités, puis le 2^e $n_{2}$ quel que soit le premier, etc., il y a $n_{1} \times n_{2} \times \dots \times n_{k}$ résultats.
3. $card (A \times B) = card (A) \times card (B) card (E^{k}) = n^{k}$
4. $A \times B$ avec $A = {a, b, c}$ et $B = {1, 2}$ : un chemin de l'arbre, un couple.
5. Reconnaître l'objet — liste ordonnée (un code, un classement) ou ensemble (une main, un groupe) ? répétitions permises ? — puis découper en cas disjoints et ajouter ; devant « au moins un », passer au complémentaire.
6. Décomposer en choix successifs et multiplier, en vérifiant que le nombre de possibilités d'une étape ne dépend pas des choix précédents ; contrôler sur un petit cas, par un arbre ou une liste.
7. Un mot de passe est un 4-uplet des 36 caractères : il y en a $3 6^{4} = 1679616$ . « Au moins un chiffre » est le contraire de « que des lettres », qui en compte $2 6^{4}$ :
8. 1 679 616 mots de passe, dont 1 222 640 avec au moins un chiffre.
9. Nombre de parties (démontré). Un ensemble $E = {x_{1}, \dots, x_{n}}$ à $n$ éléments possède $2^{n}$ parties. Preuve : à une partie $P$ , on associe le $n$ -uplet $(ε_{1}, \dots, ε_{n})$ de ${0, 1}^{n}$ , où $ε_{i} = 1$ si $x_{i} \in P$ et $ε_{i} = 0$ sinon. Chaque $n$ -uplet code une seule partie et réciproquement : c'est une bijection, donc il y a autant de parties que de $n$ -uplets, soit $2^{n}$ . Ce nombre compte aussi les mots de longueur $n$ sur un alphabet à deux lettres, les chemins d'un arbre à $n$ niveaux de deux branches, et les issues de $n$ épreuves de Bernoulli : l'issue SSES (S succès, E échec) est associée à la partie ${1, 2, 4}$ des rangs des succès.
10. Les $2^{3} = 8$ parties de ${a, b, c}$ : un chemin, un mot de 0 et de 1, une partie. En rouge, 101 code ${a, c}$ .
11. Une pizza est une partie de l'ensemble des 6 garnitures ; seule $\emptyset$ n'a aucune garniture :
12. 64 pizzas, dont 63 avec au moins une garniture.
13. Pour tout entier $n ⩾ 1$ , factorielle $n$ est le produit $n! = 1 \times 2 \times \dots \times n$ , et l'on pose $0! = 1$ . Ainsi $(n + 1)! = (n + 1) \times n!$  ; les valeurs croissent très vite : $10! = 3628800$ .
14. $k$ -uplets d'éléments distincts, permutations (démontré). Soit $E$ un ensemble à $n$ éléments et $1 ⩽ k ⩽ n$ . Pour un $k$ -uplet d'éléments distincts, on a $n$ choix pour le 1^er terme, $n - 1$ pour le 2^e, …, $n - k + 1$ pour le $k$ -ième. Par le principe multiplicatif, leur nombre est le produit de ces $k$ facteurs ; en le complétant par $(n - k)!$ , on obtient $n!$ , d'où la seconde écriture (pour $k > n$ , il n'y en a aucun). Permutations : une permutation de $E$ est un $n$ -uplet formé de ses $n$ éléments, chacun une fois, c'est-à-dire une façon de les ranger ; avec $k = n$ , $E$ possède $n!$ permutations.
15. $n (n - 1) \dots (n - k + 1) = \frac{n !}{( n - k )!}$
16. Les permutations de ${a, b, c}$ : à chaque niveau, un choix de moins.
17. Avec remise : l'ordre compte et un objet peut revenir ; on compte des $k$ -uplets, $n^{k}$ .
18. Sans remise : l'ordre compte, sans répétition ; $n (n - 1) \dots (n - k + 1)$ , que l'on calcule en simplifiant : $\frac{10 !}{7 !} = 10 \times 9 \times 8 = 720$ , sans jamais calculer $10!$ .
19. Un podium est un triplet de nageurs distincts, dans l'ordre or, argent, bronze : $8 \times 7 \times 6 = 336$ . Attribuer les couloirs, c'est ranger les 8 nageurs, une permutation :
20. 336 podiums et 40 320 répartitions des couloirs.
21. Soit $E$ un ensemble à $n$ éléments et $0 ⩽ k ⩽ n$ . Une combinaison de $k$ éléments de $E$ est une partie de $E$ à $k$ éléments : l'ordre ne compte pas et il n'y a pas de répétition. Leur nombre se note $(k n)$ , lu « $k$ parmi $n$ » : c'est un coefficient binomial. Il compte aussi les mots de longueur $n$ formés de $k$ lettres H et $n - k$ lettres D (on choisit les places des H), les chemins d'un quadrillage faits de $k$ pas vers le haut et $n - k$ vers la droite, et les issues de $n$ épreuves de Bernoulli qui comptent exactement $k$ succès.
22. 3 pas D et 2 pas H : $(2 5) = 10$ chemins de O à B. En bleu, le nombre de chemins qui mènent à chaque point.
23. Formules, cas particuliers, symétrie (démontrés). Pour $k ⩾ 1$ , ranger de toutes les façons ( $k!$ ) chaque partie à $k$ éléments donne chaque $k$ -uplet d'éléments distincts une fois : $(k n) \times k! = n (n - 1) \dots (n - k + 1)$ , et l'on divise par $k!$ . Pour $k = 0$ , les deux membres valent 1. Cas particuliers : $(0 n) = (n n) = 1$ , $(1 n) = n$ , $(2 n) = n (n - 1) /2$ . Symétrie : $A \mapsto \overline{A}$ est une bijection des parties à $k$ éléments sur celles à $n - k$ éléments, donc $(n - k n) = (k n)$ .
24. $(k n) = \frac{n ( n - 1 ) \dots ( n - k + 1 )}{k !} = \frac{n !}{k ! ( n - k )!}$
25. Un choix est une partie à 3 éléments des 22 élèves : $(3 22) = (22 \times 21 \times 20) \div 6 = 1540$ . Avec 2 filles parmi 12, puis 1 garçon parmi 10 :
26. 1 540 choix, dont 660 avec exactement 2 filles.
27. Test de l'échange : si échanger deux objets ne change rien, l'ordre ne compte pas : on compte des parties.
28. Traduire les contraintes : « exactement 2 filles » : choix successifs, on multiplie ; « au moins une » : complémentaire.
29. Relation de Pascal (démontrée de deux façons). Pour $n ⩾ 1$ et $0 ⩽ k ⩽ n - 1$ : $(k n) + (k + 1 n) = (k + 1 n + 1)$ . Par le calcul : on réduit au dénominateur $(k + 1)! (n - k)!$ , ci-dessous. Par dénombrement : dans un ensemble à $n + 1$ éléments, fixons $a$ . Parmi les parties à $k + 1$ éléments, $(k n)$ contiennent $a$ (on choisit les $k$ autres parmi les $n$ restants) et $(k + 1 n)$ ne le contiennent pas. Ces deux ensembles sont disjoints : on ajoute.
30. $(k n) + (k + 1 n) = \frac{n ! ( k + 1 ) + n ! ( n - k )}{( k + 1 )! ( n - k )!} = \frac{( n + 1 )!}{( k + 1 )! ( n - k )!} = (k + 1 n + 1)$
31. Triangle de Pascal : $(2 5) + (3 5) = 10 + 10 = 20 = (3 6)$ , sous le second terme. À droite, la somme de chaque ligne.
32. Somme d'une ligne (démontrée par dénombrement). Selon leur nombre d'éléments $k = 0, 1, \dots, n$ , les parties d'un ensemble $E$ à $n$ éléments se répartissent en $n + 1$ ensembles deux à deux disjoints, de cardinaux $(0 n), (1 n), \dots, (n n)$ . Par le principe additif, leur somme est le nombre total de parties de $E$ : $2^{n}$ .
33. $(0 n) + (1 n) + \dots + (n n) = \sum_{k = 0}^{n} (k n) = 2^{n}$
34. Bords puis intérieur : chaque ligne commence et finit par 1 ; dans le triangle aligné à gauche, chaque autre coefficient est la somme de celui qui est juste au-dessus et du voisin de gauche de ce dernier.
35. Contrôler : chaque ligne est symétrique, et sa somme vaut $2^{n}$ .
36. On ajoute les voisins de la ligne 6 : $1 + 6 = 7$ , $6 + 15 = 21$ , $15 + 20 = 35$ , puis la symétrie complète la ligne. Contrôle :
37. ligne 7 : 1, 7, 21, 35, 35, 21, 7, 1, donc $(3 7) = 35$ .
38. À gauche, chaque ligne vient de la précédente par la relation de Pascal. À droite, la condition x < y écrit chaque partie une seule fois, $(2 4) = 6$ et $(3 4) = 4$  ; melange offre $n \times (n - 1) \times \dots \times 2 = n!$ suites de tirages, une par permutation : toutes ont la même chance de sortir.