mathématiques (PTSI) · Chapitre 15 · Exercice de TD

Trois statuts par élément

Dénombrement · A. Cardinaux et opérations · niveau 2

É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é de la question 1

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.

Question 2 : comment l'IA t'aide

Élève

Je classe les couples selon $k = ∣ B ∣$ et je choisis d'abord $B$ parmi les $(k n)$ parties à $k$ éléments. Pour $A$ , je ne sais pas si je dois compter des parties de $B$ ou des parties de $E$ .

Une fois $B$ choisi, la seule contrainte sur $A$ est $A \subset B$ : parmi quelles parties choisis-tu $A$ , et combien y en a-t-il ? Le nombre de choix dépend-il de la partie $B$ choisie, ou seulement de son cardinal ?

Élève

$A$ est une partie de $B$ , qui a $k$ éléments : le nombre de choix ne dépend que de $k$ . Le nombre de couples avec $∣ B ∣ = k$ est donc un produit de deux facteurs.

Pourquoi peux-tu ensuite additionner ces nombres pour $k$ allant de $0$ à $n$ , et à quel total cette somme doit-elle être égale d'après le a) ? Pour la seconde preuve, quels termes $a$ et $b$ choisir dans la formule du binôme ?

L'IA ne donne pas la réponse : elle pose la question qui fait avancer. À toi de continuer.

Continue cet exercice avec l'IA

Reprends la question 2 là où le dialogue s'arrête, puis la suite de l'exercice.

Continuer avec l'IA — gratuit, sans inscription

Gratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.

Le cours du chapitre · Tous les exercices du chapitre

Continuer avec l'IA, gratuit →