3

Combinaisons d’un ensemble fini

Exemple

Si $\text{A}=\{1;2;3\}$, alors $\{1;3\}$ et $\varnothing$ sont des parties de $\text{A}$.

On a toujours $\varnothing \in \mathcal{P}(\mathrm{A})$.

DÉMONSTRATION

Pour constituer une partie de $\text{A}$, il y a deux choix pour chaque élément de $\text{A}$ : l’incorporer dans cette partie ou pas. Puisque $\text{A}$ possède $n$ éléments, cela donne au total $2^n$ parties possibles. Il y a ainsi autant de parties de $\text{A}$ que de $n$-uplet de $\{0;1\}$, soit $2^n$.

Les nombres $\left(\begin{array}{l}n\\ k\end{array}\right)$ sont également appelés coefficients binomiaux et se lisent « $k$ parmi $n$ ».

La 2^e égalité du point 1. traduit le fait que choisir $k$ objets parmi $n$ revient à choisir les $n-k$ objets qu’on ne prend pas.

DÉMONSTRATION

Voir Activité

C

p. 35 , exercice

94

p. 50 et exercice

105

p. 35.

Les combinaisons ne font pas apparaître l’ordre des éléments.

DÉMONSTRATION

Soit $\text{A}$ un ensemble fini à $n$ éléments. Pour tout entier naturel $k$ inférieur ou égal à $n$, on note ${\text{A}}_k$ l’ensemble des parties de $\text{A}$ composées de $k$ éléments. On a ainsi $\mathrm{Card}\left({\mathrm{A}}_k\right)=\left(\begin{array}{l}n\\ k\end{array}\right)$. Les ${\text{A}}_k$ sont deux à deux disjoints et leur réunion est $\mathcal{P}(\mathrm{A})$. Ainsi :
$2^n=\mathrm{Card}(\mathcal{P}(\mathrm{A}))=\mathrm{Card}\left({\mathrm{A}}_1\cup \dots \cup {\mathrm{A}}_n\right)=\sum _{k=0}^n\mathrm{Card}\left({\mathrm{A}}_k\right)=\sum _{k=0}^n\left(\begin{array}{l}n\\ k\end{array}\right)$.

Dans une grille comportant les nombres 0 à 9 et les lettres $\text{A}$ à $\text{F}$, il faut choisir trois nombres et deux lettres. Combien de grilles différentes existe‑t‑il ?