Problème — Dénombrer avec le produit cartésien et la bijection

• L'ensemble de ces $n$-uplets est le produit cartésien $\{0,1{\}}^n=\{0,1\}\times \cdots \times \{0,1\}$ ($n$ facteurs). D'après le principe multiplicatif du chapitre 7 :

$$\text{Card}(\{0,1{\}}^n)=\underset{n\text{ facteurs}}{\underbrace{2\times 2\times \cdots \times 2}}=2^n.$$

Autrement dit, chaque coordonnée se choisit indépendamment parmi deux valeurs, et les choix se multiplient.

• À une partie $A\subset E$, associons le $n$-uplet $\phi (A)=(x_1;\dots ;x_n)$ défini par

$$x_i=1\text{ si }{e}_i\in A,x_i=0\text{ si }{e}_i\notin A.$$

Montrons que $\phi$ est une bijection de l'ensemble des parties de $E$ sur $\{0,1{\}}^n$, c'est-à-dire que tout $n$-uplet a un antécédent et un seul.

• Existence : soit $(x_1;\dots ;x_n)\in \{0,1{\}}^n$. La partie $A=\{e_i\mid x_i=1\}$ vérifie bien $\phi (A)=(x_1;\dots ;x_n)$.
• Unicité : si deux parties $A$ et $B$ ont le même codage, alors pour chaque $i$, $e_i$ appartient à $A$ exactement quand il appartient à $B$ ; les deux parties ont donc les mêmes éléments, donc $A=B$.

Chaque $n$-uplet a donc un antécédent et un seul : $\phi$ est une bijection.

• Deux ensembles finis en bijection ont le même nombre d'éléments : ce qui est compté d'un côté est compté de l'autre, sans oubli ni doublon. Donc $E$ possède exactement $2^n$ parties — c'est le théorème du chapitre 7, et sa démonstration tient tout entière dans cette bijection.

• Pour $n=3$ :

$$\begin{array}{lll}\varnothing \leftrightarrow (0,0,0),& \{e_1\}\leftrightarrow (1,0,0),& \{e_2\}\leftrightarrow (0,1,0),\\ \{e_3\}\leftrightarrow (0,0,1),& \{e_1,e_2\}\leftrightarrow (1,1,0),& \{e_1,e_3\}\leftrightarrow (1,0,1),\\ \{e_2,e_3\}\leftrightarrow (0,1,1),& \{e_1,e_2,e_3\}\leftrightarrow (1,1,1).& \end{array}$$

On compte $8$ parties d'un côté, $8$ triplets de l'autre, et $2^3=8$ : tout concorde.

• Imposer $e_1\in A$, c'est imposer $x_1=1$. La première coordonnée n'offre alors plus qu'un seul choix, les $n-1$ autres restant libres :

$$1\times \underset{n-1\text{ facteurs}}{\underbrace{2\times \cdots \times 2}}=2^{n-1}.$$

Il y a donc $2^{n-1}$ parties contenant $e_1$ — soit exactement la moitié, ce qui se comprend : ajouter ou retirer $e_1$ appaire les parties deux à deux. On voit ici l'intérêt du codage : une contrainte sur les éléments devient une contrainte sur une coordonnée du produit cartésien, et le dénombrement redevient une simple multiplication.