Listes et parties d'un ensemble

2.1 Nombre de $k$-uplets

Propriété (programme). Si $A$ est un ensemble à $n$ éléments et $k \geq 1$ un entier, le nombre de $k$-uplets (ou $k$-listes) d'éléments de $A$ est $\mathrm{Card}(A^k) = n^k.$

C'est le principe multiplicatif avec $k$ facteurs égaux à $n$ : $n$ choix pour le premier élément, $n$ pour le deuxième, et ainsi de suite. Dans un $k$-uplet, l'ordre compte et les répétitions sont permises.

Exemple 5 (un code). Un cadenas a quatre molettes, chacune avec les chiffres de $0$ à $9$. Un code est un $4$-uplet de $\{0\,;1\,;\ldots\,;9\}$ : il y a $10^4 = 10\,000$ codes, de $0000$ à $9999$.

Exemple 6 (génétique). L'ADN est écrit avec quatre bases, notées $A$, $C$, $G$ et $T$. Une suite de trois bases, appelée codon, est un triplet de $\{A\,;C\,;G\,;T\}$ : il y a $4^3 = 64$ codons.

Exemple 7 (informatique). Un octet est une suite de huit bits, chacun valant $0$ ou $1$ : c'est un $8$-uplet de $\{0\,;1\}$. Il y a $2^8 = 256$ octets différents.

2.2 Nombre de parties d'un ensemble

Les parties de $E = \{a\,;b\,;c\}$, rangées selon leur nombre d'éléments, sont :

• $\varnothing$ ;
• $\{a\}$, $\{b\}$, $\{c\}$ ;
• $\{a\,;b\}$, $\{a\,;c\}$, $\{b\,;c\}$ ;
• $\{a\,;b\,;c\}$.

Il y en a $8 = 2^3$.

Propriété (programme). Un ensemble à $n$ éléments a $2^n$ parties.

Pourquoi : un codage par des 0 et des 1. Écrivons $E = \{x_1\,;x_2\,;\ldots\,;x_n\}$. À chaque partie $A$ de $E$, on associe le $n$-uplet $(c_1\,;c_2\,;\ldots\,;c_n)$ de $\{0\,;1\}$ défini par : $c_i = 1$ si $x_i \in A$, et $c_i = 0$ sinon.

• Pour $E = \{a\,;b\,;c\}$ : $\{a\,;c\}$ est codée par $(1\,;0\,;1)$, $\varnothing$ par $(0\,;0\,;0)$ et $E$ par $(1\,;1\,;1)$.
• Inversement, un $n$-uplet de $\{0\,;1\}$ code une seule partie : celle des éléments $x_i$ pour lesquels $c_i = 1$.

Chaque partie correspond ainsi à un $n$-uplet de $\{0\,;1\}$ et un seul, et réciproquement (c'est une bijection). Il y a donc autant de parties que de $n$-uplets de $\{0\,;1\}$, c'est-à-dire $2^n$.

Trois autres façons de voir ces $2^n$ objets (programme).

• Des mots de longueur $n$ sur un alphabet à deux lettres : $(1\,;0\,;1)$ s'écrit simplement $101$.
• Des chemins dans un arbre à $n$ niveaux, avec deux branches à chaque nœud : au niveau $i$, on prend $x_i$ ou on ne le prend pas. L'arbre a $2^n$ chemins.
• Les issues d'une succession de $n$ épreuves à deux issues, succès $S$ ou échec $\overline{S}$ (les épreuves de Bernoulli du chapitre 11) : une issue est un $n$-uplet de $\{S\,;\overline{S}\}$, et il y en a $2^n$. Pour $n = 3$ : $SSS$, $SS\overline{S}$, $S\overline{S}S$, $S\overline{S}\,\overline{S}$, $\overline{S}SS$, $\overline{S}S\overline{S}$, $\overline{S}\,\overline{S}S$, $\overline{S}\,\overline{S}\,\overline{S}$.

Exemple 8. Une pizzeria propose une base, sur laquelle on ajoute ou non chacun de $6$ ingrédients. Une pizza correspond à une partie de l'ensemble des $6$ ingrédients : il y a $2^6 = 64$ pizzas différentes, en comptant la pizza sans ingrédient (la partie vide).