Les couples de parties emboîtées

Exercice de TD · niveau 2 · mathématiques MPSI, chapitre 18 — Dénombrement · A. Cardinaux et opérations

Énoncé

Soit $E$ un ensemble de cardinal $n$ .

a) Combien y a-t-il de couples $(A, B)$ de parties de $E$ tels que $A \subset B$ ?

b) En classant ces couples selon le cardinal de $B$ , en déduire $k = 0 \sum n (k n) 2^{k} = 3^{n}$ (le coefficient binomial se lit « $k$ parmi $n$ »), puis retrouver cette identité par la formule du binôme.

c) Combien y a-t-il de couples $(A, B)$ de parties disjointes de $E$ ? De triplets $(A, B, C)$ avec $A \subset B \subset C$ ?

Corrigé

Ce qu'on a le droit d'utiliser. Le principe de multiplication, sous la forme du cours : le nombre d'applications d'un ensemble à $n$ éléments dans un ensemble à $q$ éléments est $q^{n}$ — une partie de $E$ est une application de $E$ dans ${0, 1}$ , ce qui donne les $2^{n}$ parties. La stratégie est la même : décrire un couple $(A, B)$ par le statut de chaque élément.

a) Trois statuts par élément. Soit $(A, B)$ un couple de parties avec $A \subset B$ . Chaque élément $x \in E$ est dans exactement une des trois situations : $x \in A$ (et alors $x \in B$ ) ; $x \in B ∖ A$ ; $x \in / B$ . Associons au couple l'application $s : E \to {0, 1, 2}$ qui vaut $2$ sur $A$ , $1$ sur $B ∖ A$ , $0$ hors de $B$ . Réciproquement, une application $s : E \to {0, 1, 2}$ quelconque définit $A = s^{- 1} ({2})$ et $B = s^{- 1} ({1, 2})$ , qui vérifient $A \subset B$ , et l'on retrouve $s$ à partir de $(A, B)$ . Les deux constructions sont inverses l'une de l'autre : les couples emboîtés sont en bijection avec les applications de $E$ dans ${0, 1, 2}$ . Il y en a $3^{n}$ .

Autrement dit : pour chacun des $n$ éléments, trois choix indépendants — dans $A$ , dans $B$ seulement, dans aucun —, et le principe de multiplication donne $3^{n}$ .

b) L'identité, par le tri. Classons les couples selon $k = ∣ B ∣$ , de $0$ à $n$ : les classes sont disjointes et recouvrent tout. Pour $k$ fixé, on choisit $B$ parmi les $(k n)$ parties à $k$ éléments, puis $A$ parmi les $2^{k}$ parties de $B$ — toute partie de $B$ convient. Le principe d'addition donne $3^{n} = k = 0 \sum n (k n) 2^{k} .$ Par le binôme. La formule du binôme, $(a + b)^{n} = k = 0 \sum n (k n) a^{k} b^{n - k}$ , avec $a = 2$ et $b = 1$ , donne $(2 + 1)^{n} = k = 0 \sum n (k n) 2^{k}$ , c'est-à-dire exactement l'identité. Le comptage et le calcul se rejoignent ; et l'on voit ce que le calcul cache : $3 = 2 + 1$ est le nombre de statuts, $2 + 1$ étant « dans $B$ » à deux façons plus « hors de $B$ ».

c) Deux variantes. Parties disjointes. Un couple $(A, B)$ avec $A \cap B = \emptyset$ donne encore trois statuts exclusifs par élément : dans $A$ , dans $B$ , dans aucun des deux ; et réciproquement. Donc $3^{n}$ couples, autant que de couples emboîtés — ce n'est pas un hasard : $(A, B) \mapsto (A, A \cup B)$ est une bijection des couples disjoints sur les couples emboîtés, d'inverse $(A, B) \mapsto (A, B ∖ A)$ . Triplets emboîtés. Pour $A \subset B \subset C$ , chaque élément a quatre statuts — dans $A$ , dans $B ∖ A$ , dans $C ∖ B$ , hors de $C$ — d'où $4^{n}$ triplets ; et le même tri donne $k = 0 \sum n (k n) 3^{k} = 4^{n}$ , qui est le binôme avec $a = 3$ , $b = 1$ .

Contrôle pour $n = 2$ . Les couples emboîtés de parties de ${a, b}$ : $B = \emptyset$ en donne $1$ ; $B = {a}$ ou ${b}$ en donnent $2$ chacun ; $B = {a, b}$ en donne $4$ . Total $1 + 2 + 2 + 4 = 9 = 3^{2}$ .

Ce que l'exercice installe. Un objet composé se compte par le statut de chaque élément : une partie est une application vers ${0, 1}$ , un couple emboîté vers ${0, 1, 2}$ , une chaîne de $r$ parties vers ${0, \dots, r}$ . Et une identité binomiale s'obtient en comptant le même ensemble globalement puis par tranches — le binôme n'est que la version calculatoire de ce tri.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.