Combinaisons d'un ensemble fini

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

Soit $\text{A}$ un ensemble fini à $n$ éléments. Le nombre de parties de $\text{A}$ est égal à $2^n$.

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

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$.

Soient $n$ et $k$ deux entiers naturels tels que $k⩽n$. Alors :
1.$\left(\begin{array}{l}n\\ k\end{array}\right)=\frac{n!}{k!(n-k)!}$ et $\left(\begin{array}{c}n\\ k\end{array}\right)=\left(\begin{array}{c}n\\ n-k\end{array}\right)$.
2. Relation de Pascal : si $1⩽k⩽n-1,\left(\begin{array}{l}n\\ k\end{array}\right)=\left(\begin{array}{l}n-1\\ k-1\end{array}\right)+\left(\begin{array}{c}n-1\\ k\end{array}\right)$.
3. De plus,$\left(\begin{array}{l}n\\ 0\end{array}\right)=1$. Si $n⩾1,\left(\begin{array}{l}n\\ 1\end{array}\right)=n$ et si $n⩾2,\left(\begin{array}{l}n\\ 2\end{array}\right)=\frac{n(n-1)}{2}$.

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.

Voir

Activité C

p. 35, exercice

94

p. 50 et exercice

105

p. 35.

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)$.

Pour les nombres, il existe $\left(\begin{array}{c}10\\ 3\end{array}\right)=\frac{10!}{3!7!}=120$ combinaisons possibles.
Pour les lettres, on dispose de $\left(\begin{array}{l}6\\ 2\end{array}\right)=15$ combinaisons.
Au total, il y a donc $120\times 15=1800$ grilles possibles.

Exercices

43

et

44

p. 45