Combinatoire et dénombrement : cours de Terminale et exercices

1Cardinal, principe additif et principe multiplicatif

Définition. Un ensemble $E$ est fini s’il possède un nombre fini d’éléments ; ce nombre est son cardinal, noté $\Card(E)$ . L’ensemble vide $\varnothing$ a pour cardinal $0$ .

Propriété — principe additif. Si $A$ et $B$ sont deux parties finies d’un ensemble $E$ :

\Card(A\cup B)=\Card(A)+\Card(B)-\Card(A\cap B),\qquad\text{et }\ \Card(A\cup B)=\Card(A)+\Card(B)\ \text{ si }A\cap B=\varnothing.

Pour le complémentaire d’une partie $A$ de $E$ : $\Card\bigl(\overline{A}\bigr)=\Card(E)-\Card(A)$ .

Propriété — principe multiplicatif. $\Card(A\times B)=\Card(A)\times\Card(B)$ . Plus généralement, $k$ choix successifs offrant respectivement $n_1,n_2,\dots,n_k$ possibilités conduisent à $n_1\times n_2\times\cdots\times n_k$ résultats : c’est le nombre de chemins de l’arbre.

2 $k$ -uplets et parties d’un ensemble

Définition. Un $k$ -uplet (ou $k$ -liste) d’éléments de $E$ est une liste ordonnée de $k$ éléments de $E$ , les répétitions étant autorisées : c’est un élément de $E^{k}$ .

Propriété. Si $\Card(E)=n$ , alors $E$ possède $n^{k}$ $k$ -uplets et $2^{n}$ parties.

Remarque. Décrire une partie de $E$ , c’est répondre « oui » ( $1$ ) ou « non » ( $0$ ) pour chacun des $n$ éléments : les parties de $E$ sont en bijection avec les $n$ -uplets de $\ens{0\,;1}$ , d’où le $2^{n}$ .

3Arrangements et permutations

Définition. Un arrangement de $k$ éléments de $E$ est un $k$ -uplet d’éléments deux à deux distincts de $E$ (ordonné, sans répétition). Une permutation de $E$ est un arrangement de tous ses éléments.

Notation. Pour $n\in\N^{*}$ , $n!=1\times 2\times\cdots\times n$ (« factorielle $n$ »), et $0!=1$ .

Propriété. Si $\Card(E)=n$ et $0\leq k\leq n$ , le nombre d’arrangements de $k$ éléments de $E$ est

A_n^{k}=n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}\ \ (k\text{ facteurs}),\qquad\text{et }\ A_n^{n}=n!\ \text{ permutations}.

4Combinaisons et coefficients binomiaux

Définition. Une combinaison de $k$ éléments de $E$ est une partie de $E$ à $k$ éléments (non ordonnée, sans répétition). Leur nombre est le coefficient binomial $\dbinom{n}{k}$ , qui se lit « $k$ parmi $n$ ».

Propriété. Pour $0\leq k\leq n$ :

\binom{n}{k}=\frac{A_n^{k}}{k!}=\frac{n!}{k!\,(n-k)!}\,;

en particulier $\tbinom{n}{0}=\tbinom{n}{n}=1$ , $\tbinom{n}{1}=n$ (si $n\geq1$ ) et $\tbinom{n}{2}=\frac{n(n-1)}{2}$ (si $n\geq2$ ).

Propriété — symétrie. $\tbinom{n}{k}=\tbinom{n}{n-k}$ : à chaque partie on associe son complémentaire.

Propriété — relation de Pascal. Pour $1\leq k\leq n-1$ : $\tbinom{n-1}{k-1}+\tbinom{n-1}{k}=\tbinom{n}{k}$ ; c’est la règle de construction du triangle de Pascal.

$n\backslash k$	0	1	2	3	4	5	6
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
6	1	6	15	20	15	6	1

Figure 1 — Triangle de Pascal.

Propriété — somme d’une ligne. $\displaystyle\sum_{k=0}^{n}\binom{n}{k}=2^{n}$ : on classe les $2^{n}$ parties de $E$ selon leur nombre d’éléments.

5Choisir le bon modèle

Méthode — quatre questions. (1) L’ordre compte-t-il ? (2) Les répétitions sont-elles autorisées ? (3) Combien d’objets choisit-on ? (4) Les choix sont-ils successifs (multiplicatif) ou exclusifs (additif) ?

Formulairetirage de

k

objets dans un ensemble à

n

éléments

Ordonné avec répétition (tirages successifs avec remise, codes, mots) : $n^{k}$ $k$ -uplets.
Ordonné sans répétition (tirages successifs sans remise, podium, rangement) : $A_n^{k}=\dfrac{n!}{(n-k)!}$ ; si $k=n$ : $n!$ .
Non ordonné sans répétition (tirage simultané, main de cartes, équipe, comité) : $\dbinom{n}{k}=\dfrac{n!}{k!\,(n-k)!}$ .
Équiprobabilité : si toutes les issues de $\Omega$ ont la même probabilité, $P(A)=\dfrac{\Card(A)}{\Card(\Omega)}$ .

6Savoir-faire du chapitre

Savoir-faire

Dénombrer une réunion, un complémentaire, un produit cartésien, une succession de choix (arbre, tableau).
Reconnaître un $k$ -uplet, un arrangement, une permutation ou une combinaison, et justifier le modèle choisi.
Calculer $n!$ , $A_n^{k}$ et $\binom{n}{k}$ , à la main ou à la calculatrice ; utiliser la symétrie et la relation de Pascal.
Dénombrer en contexte : codes, mots et anagrammes, mains de cartes, équipes, chemins d’un quadrillage.
Calculer une probabilité en situation d’équiprobabilité par $\Card(A)/\Card(\Omega)$ , souvent en passant par l’événement contraire.

7Exemples types

Exemplecodes et mots

Un code comporte $4$ caractères choisis parmi $26$ lettres et $10$ chiffres. Il y a $36^{4}=1\,679\,616$ codes possibles, mais seulement $A_{36}^{4}=36\times35\times34\times33=1\,413\,720$ codes à caractères deux à deux distincts.

Exempletirage simultané

Dans un jeu de $32$ cartes, on tire $5$ cartes simultanément : il y a $\binom{32}{5}=201\,376$ mains. Celles contenant exactement deux as sont au nombre de $\binom{4}{2}\times\binom{28}{3}=6\times3\,276=19\,656$ , d’où une probabilité $\dfrac{19\,656}{201\,376}\approx 0{,}098$ .

Exempleévénement contraire

Un comité de $3$ personnes est tiré au sort parmi $7$ femmes et $5$ hommes, soit $\binom{12}{3}=220$ comités. « Au moins une femme » a pour contraire « aucune femme », qui compte $\binom{5}{3}=10$ comités : la probabilité cherchée vaut $1-\dfrac{10}{220}=\dfrac{21}{22}\approx 0{,}955$ .

Pièges

Confondre ordonné et non ordonné : un tirage simultané donne des combinaisons, un tirage successif sans remise des arrangements, et $A_n^{k}=k!\times\binom{n}{k}$ .
$A_n^{k}$ et $\binom{n}{k}$ ne sont définis que pour $0\leq k\leq n$ : pour $k>n$ , il n’y a ni arrangement ni combinaison.
Le principe additif $\Card(A\cup B)=\Card(A)+\Card(B)$ exige $A\cap B=\varnothing$ : sinon, retrancher $\Card(A\cap B)$ , sous peine de compter deux fois.
« Au moins un » se traite presque toujours par l’événement contraire « aucun » ; « exactement $k$ » se traite en choisissant d’abord les $k$ places ou les $k$ objets.

← Calcul intégral Vecteurs, droites et plans de l’espace →

Combinatoire et dénombrement

1Cardinal, principe additif et principe multiplicatif

2 $k$ -uplets et parties d’un ensemble

3Arrangements et permutations

4Combinaisons et coefficients binomiaux

5Choisir le bon modèle

6Savoir-faire du chapitre

7Exemples types

Exercices, contrôles et sujets

Exercices de base

Exercices d'application

Contrôle A

Contrôle B

Approfondissement

Sujet type bac

Terminale · Mathématiques : les 17 chapitres

Combinatoire et dénombrement

1Cardinal, principe additif et principe multiplicatif

2kk-uplets et parties d’un ensemble

3Arrangements et permutations

4Combinaisons et coefficients binomiaux

5Choisir le bon modèle

6Savoir-faire du chapitre

7Exemples types

Exercices, contrôles et sujets

Exercices de base

Exercices d'application

Contrôle A

Contrôle B

Approfondissement

Sujet type bac

Terminale · Mathématiques : les 17 chapitres

2 $k$ -uplets et parties d’un ensemble