Trois statuts par élément

Exercice de TD · niveau 2 · mathématiques (PCSI), chapitre 14 — Dénombrement · A. Cardinaux et opérations

Énoncé

Soit $E$ un ensemble à $n$ éléments.

a) Combien de couples $(A, B)$ de parties de $E$ vérifient $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 $(k n)$ se lit « $k$ parmi $n$ » —, puis retrouver cette identité par la formule du binôme.

c) Généraliser : combien de suites $(A_{1}, \dots, A_{r})$ de parties de $E$ vérifient $A_{1} \subset A_{2} \subset \dots \subset A_{r}$ ?

Corrigé

Ce qu'on a le droit d'utiliser. Le principe de multiplication, et sa forme du cours : il y a $q^{n}$ applications d'un ensemble à $n$ éléments dans un ensemble à $q$ éléments — pour chaque élément, $q$ choix indépendants d'image. La stratégie : décrire un objet composé par le statut de chaque élément.

a) Trois statuts. Se donner un couple $(A, B)$ avec $A \subset B$ , c'est attribuer à chaque élément $x$ de $E$ exactement l'un de trois statuts : $x \in A$ (et alors $x \in B$ ) ; $x \in B$ mais $x \in / A$ ; $x \in / B$ (et alors $x \in / A$ ). Réciproquement, un statut choisi pour chaque élément définit $A$ , l'ensemble des éléments du premier statut, et $B$ , celui des éléments des deux premiers, avec $A \subset B$ . Les choix sont indépendants d'un élément à l'autre : il y a $3^{n}$ couples. (Dans le langage des applications : un couple emboîté, c'est une application de $E$ dans un ensemble à trois éléments.)

Le point délicat : où vit l'hypothèse. Un quatrième statut existerait a priori, « dans $A$ mais pas dans $B$ » : c'est exactement lui que la condition $A \subset B$ interdit. Sans elle, il y aurait quatre statuts et $4^{n} = (2^{n})^{2}$ couples, ce qui est bien le nombre de couples de parties quelconques.

b) L'identité, par tranches. 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$ . Le principe d'addition donne $k = 0 \sum n (k n) 2^{k} = 3^{n} .$ Par le binôme, avec $a = 2$ et $b = 1$ : $(2 + 1)^{n} = \sum_{k = 0}^{n} (k n) 2^{k} 1^{n - k}$ . Le comptage explique le calcul : $3 = 2 + 1$ est le nombre de statuts — deux façons d'être dans $B$ , une d'en être dehors.

c) Les chaînes. Pour une suite emboîtée $A_{1} \subset \dots \subset A_{r}$ , le statut d'un élément $x$ est le plus petit indice $i$ tel que $x \in A_{i}$ — il est alors dans tous les $A_{j}$ pour $j \geq i$ —, ou « aucun » si $x \in / A_{r}$ : $r + 1$ statuts possibles. Réciproquement, un statut par élément définit la chaîne, $A_{i}$ étant l'ensemble des éléments de statut au plus $i$ . Donc il y a $(r + 1)^{n}$ chaînes : $2^{n}$ pour $r = 1$ , ce sont les parties ; $3^{n}$ pour $r = 2$ , c'est le a). Le tri selon $∣ A_{r} ∣ = k$ donne de même $\sum_{k = 0}^{n} (k n) r^{k} = (r + 1)^{n}$ — une fois $A_{r}$ choisie, les $r - 1$ autres parties forment une chaîne de parties de $A_{r}$ , et il y en a $r^{k}$ —, qui est le binôme avec $a = r$ et $b = 1$ .

Contrôles. Pour $E = {1, 2}$ : $B = \emptyset$ donne $1$ couple, $B = {1}$ et $B = {2}$ en donnent $2$ chacun, $B = {1, 2}$ en donne $4$ : $9 = 3^{2}$ . Une énumération exhaustive des chaînes $A_{1} \subset A_{2} \subset A_{3}$ pour $n = 4$ en trouve $256 = 4^{4}$ .

Ce que l'exercice installe. Un objet composé se compte par le statut de chaque élément : une partie, c'est deux statuts, un couple emboîté trois, une chaîne de $r$ parties $r + 1$ . 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. C'est aussi le modèle des probabilités du chapitre 15 : chaque élément « choisit » son statut indépendamment des autres.

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.