Nombre de parties d'un ensemble

Parties d'un ensemble et mots binaires

Une partie d'un ensemble $E$ est un ensemble $A$ dont tous les éléments sont des éléments de $E$. On écrit $A \subset E$. Deux parties sont toujours possibles : l'ensemble vide $\varnothing$ et $E$ lui-même.

Prenons $E = \{a, b, c\}$. Pour fabriquer une partie, on décide pour chaque élément s'il y est (on note 1) ou non (on note 0). Chaque partie correspond alors à un mot de trois symboles, et réciproquement.

Cette correspondance est une bijection : à chaque partie correspond un seul mot, et à chaque mot une seule partie. Il y a donc autant de parties de $E$ que de mots binaires de longueur $3$.

Combien y a-t-il de mots binaires de longueur $n$ ? On choisit chaque symbole parmi $2$ valeurs, $n$ fois de suite. C'est le principe multiplicatif : on compte les $n$-uplets de $\{0, 1\}$, c'est-à-dire les éléments de $\{0,1\}^n$.

Pour $n = 3$, on retrouve $2^3 = 8$ parties, comme dans le tableau. Essaie avec le widget : chaque combinaison de bits est une partie d'un ensemble à $4$ éléments.

Parties de cardinal donné et principe additif

Reprenons les $8$ parties de $\{a, b, c\}$ et classons-les selon leur nombre d'éléments :

On reconnaît les coefficients binomiaux $\binom{3}{k}$, qui comptent les parties à $k$ éléments. On a bien $1 + 3 + 3 + 1 = 8 = 2^3$.

Le principe additif explique ce calcul : les parties de cardinal $0$, de cardinal $1$, etc. forment des ensembles deux à deux disjoints, dont la réunion est $\mathcal P(E)$. On additionne donc leurs nombres d'éléments.

Retour au début : pour la crêperie, il y a $2^5 = 32$ crêpes possibles, dont $31$ avec au moins une garniture.

Bijections et parties de cardinal pair

Une bijection permet de compter un ensemble en le remplaçant par un autre plus simple. C'est ce que nous avons fait avec les mots binaires. Pour la rédiger, il faut préciser :

1. comment on passe d'une partie à un mot (et inversement) ;

2. que chaque objet a une seule image et un seul antécédent.

Compter les parties de cardinal pair : pour $n = 5$, d'après la section précédente, ce nombre vaut

C'est la moitié de $2^5 = 32$. Est-ce un hasard ? Non. On fixe un élément $x$ de $E$ et, pour toute partie $A$, on la remplace par la partie $A'$ obtenue en ajoutant $x$ si $x\notin A$, ou en le retirant si $x \in A$. Cela change le cardinal de $1$, donc la parité. L'opération est sa propre réciproque : c'est une bijection entre parties de cardinal pair et parties de cardinal impair.

Lien avec la formule du binôme

Pour tous réels $a$ et $b$ et tout entier $n$ :

En prenant $a = b = 1$, on obtient $2^n = \sum_{k=0}^{n}\binom{n}{k}$, ce qui redonne la propriété de la section 2.

En prenant $a = -1$ et $b = 1$, on obtient, pour $n \geq 1$ :

Les termes avec $k$ pair sont positifs, ceux avec $k$ impair sont négatifs. La somme est nulle, donc

Il y a autant de parties de cardinal pair que de cardinal impair, ce qui confirme la bijection de la section précédente.

Dénombrements plus fins

Couples de parties emboîtées

On veut compter les couples $(A, B)$ de parties de $E$ tels que $A \subset B$. Pour chaque élément $x$ de $E$, il y a exactement trois situations possibles : $x \in A$ (donc aussi dans $B$), $x \in B \setminus A$, ou $x \notin B$.

Les choix se font indépendamment pour chaque élément : principe multiplicatif, $3 \times 3 \times \dots \times 3 = 3^n$ couples.

On peut aussi compter selon le cardinal $k$ de $B$. Il y a $\binom{n}{k}$ façons de choisir $B$, puis $2^k$ parties $A$ de $B$ (principe multiplicatif), puis on additionne sur $k$ (principe additif) :

On retrouve bien $3^n$, comme avec la formule du binôme pour $a=2$, $b=1$.

Codes binaires sans deux « 1 » consécutifs

Les mots binaires ne sont pas toujours libres : parfois une contrainte réduit le nombre. Notons $c_n$ le nombre de mots binaires de longueur $n$ sans deux « 1 » consécutifs.

Avec $c_3 = 5$ et $c_4 = 8$, on construit la suite $2, 3, 5, 8, 13, \dots$ (la suite de Fibonacci). Un tableur ou une boucle Python le fait très bien :

c = [2, 3]

for n in range(8):

    c.append(c[-1] + c[-2])

print(c[-1])

Retour au début : pour la crêperie, la méthode « présent ou absent » donne $2^5 = 32$ crêpes.

L'essentiel

• Une partie de $E$ est un sous-ensemble de $E$ ; $\varnothing$ et $E$ en font partie.

• Un ensemble à $n$ éléments possède $2^n$ parties : chaque élément est présent ou absent, ce qui définit une bijection avec les mots binaires de longueur $n$.

• Le nombre de parties à $k$ éléments est $\binom{n}{k}$. Par le principe additif, $\sum_{k=0}^{n}\binom{n}{k} = 2^n$.

• Pour $n \geq 1$, il y a autant de parties de cardinal pair que de cardinal impair : $2^{n-1}$ chacune.

• Pour les contraintes, on sépare en cas disjoints (principe additif) ou on passe au complémentaire ; les choix indépendants se multiplient.