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 $\operatorname{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}=\operatorname{Card}(\mathcal{P}(\mathrm{A}))=\operatorname{Card}\left(\mathrm{A}_{1} \cup \ldots \cup \mathrm{A}_{n}\right)=\displaystyle\sum_{k=0}^{n} \operatorname{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 ?