Exercice 28

1. Une relation sur $E$ est une partie de $E \times E$, qui a $n^{2}$ éléments d'après le lemme 6 du cours. Une relation réflexive contient obligatoirement les $n$ couples $(x,x)$ et choisit librement les $n^{2} - n$ autres. Une relation symétrique est déterminée par les couples $(x,y)$ avec $x \leqslant y$, pour une numérotation fixée de $E$ : il y en a $n + \frac{n(n-1)}{2} = \frac{n(n+1)}{2}$. Si elle est de plus réflexive, il ne reste à choisir que les $\frac{n(n-1)}{2}$ paires $\{x,y\}$ avec $x \neq y$. $$\boxed{2^{n^{2}} \text{ relations,} \quad 2^{n^{2} - n} \text{ réflexives,} \quad 2^{n(n+1)/2} \text{ symétriques,} \quad 2^{n(n-1)/2} \text{ réflexives et symétriques}}$$

2. Les partitions de $\{1,2,3\}$ sont $$\big\{\{1,2,3\}\big\},\quad \big\{\{1\},\{2,3\}\big\},\quad \big\{\{2\},\{1,3\}\big\},\quad \big\{\{3\},\{1,2\}\big\},\quad \big\{\{1\},\{2\},\{3\}\big\}.$$ Pour $\{1,2,3,4\}$, on classe les partitions selon la taille de leurs parties :

• une seule partie à $4$ éléments : $1$ partition ;

• une partie à $3$ éléments et un singleton : $4$ partitions, selon le singleton ;

• deux paires : $3$ partitions, selon le partenaire de $1$ ;

• une paire et deux singletons : $6$ partitions, selon la paire ;

• quatre singletons : $1$ partition.

D'après le cours, les relations d'équivalence sur un ensemble correspondent exactement à ses partitions : à une relation on associe l'ensemble de ses classes, et à une partition la relation « appartenir à la même partie » (proposition 8). $$\boxed{\text{Relations d'équivalence : } 5 \text{ sur un ensemble à } 3 \text{ éléments, } 15 \text{ sur un ensemble à } 4 \text{ éléments}}$$ Ces nombres, $1, 2, 5, 15, 52, \dots$, sont les nombres de Bell.

3. Un ordre total sur $E$ revient à ranger les éléments de $E$ du plus petit au plus grand : on choisit le plus petit élément ($n$ choix), puis le plus petit des restants ($n - 1$ choix), et ainsi de suite. $$\boxed{n! \text{ ordres totaux}}$$