Les cinq partitions d'un ensemble à trois éléments

Stratégie : dénombrer par disjonction sur la forme des morceaux. Une partition de $E$ est une famille de parties non vides, deux à deux disjointes, dont la réunion est $E$ tout entier. Comme $E$ a trois éléments, chaque partition a un, deux ou trois morceaux : on traite ces trois cas séparément, ce qui garantit qu'on n'en oublie ni n'en compte deux fois.

Cas d'un seul morceau. Le morceau unique doit recouvrir $E$ : c'est $E$ lui-même. Une seule partition :

$$\{\{a,b,c\}\}.$$

Cas de trois morceaux. Trois parties non vides et disjointes dans un ensemble à trois éléments : chacune contient exactement un élément. Une seule partition :

$$\{\{a\},\{b\},\{c\}\}.$$

Cas de deux morceaux. Les deux parties sont non vides, disjointes, de réunion $E$ : leurs cardinaux sont donc $1$ et $2$. La partition est entièrement déterminée par le choix de l'élément isolé, et il y a trois choix possibles :

$$\{\{a\},\{b,c\}\},\{\{b\},\{a,c\}\},\{\{c\},\{a,b\}\}.$$

⚠️ Le point délicat est de ne pas confondre une partition avec une suite de parties. La partition dont les morceaux sont $\{a\}$ et $\{b,c\}$ est la même que celle dont les morceaux sont $\{b,c\}$ et $\{a\}$ : l'ordre des morceaux ne compte pas. C'est pourquoi le cas à deux morceaux donne trois partitions et non six.

Conclusion. Il y a exactement $1+3+1=5$ partitions de $E$.

Le nombre de parties. Une partie de $E$ se décrit en décidant, pour chacun des trois éléments, s'il y appartient ou non : deux choix indépendants pour chaque élément, donc

$$\mathrm{card}\mathcal{P}(E)=2^3=8.$$

Ces huit parties sont l'ensemble vide, les trois singletons, les trois paires, et $E$ lui-même. On vérifie : $1+3+3+1=8$. ✔

Le nombre de couples. Un couple de $E\times E$ est la donnée d'une première coordonnée — trois choix — puis d'une seconde — trois choix encore, indépendants du premier :

$$\mathrm{card}(E\times E)=3\times 3=9.$$

Contrôle. Les trois nombres $5$, $8$ et $9$ sont bien distincts, et ils comptent trois objets de natures différentes : les découpages de $E$, les sous-ensembles de $E$, et les paires ordonnées d'éléments. Notons que $5<8$ : toute partition à deux morceaux détermine bien une partie, mais aucune des huit parties ne redonne à elle seule une partition, et l'ensemble vide, qui est une partie, n'est jamais un morceau de partition.

Ce que l'exercice installe. Trois constructions du cours mises côte à côte sur le même petit ensemble : la partition, l'ensemble des parties, le produit cartésien. Le nombre $2^n$ de parties et le nombre $n^2$ de couples se retrouvent d'un trait ; le nombre de partitions, lui, ne suit aucune formule simple — on l'appelle le nombre de Bell, et il vaut $1,2,5,15,52$ pour $n=1,2,3,4,5$.