Dénombrements de parties (1/2)

Exercice 1.
Soit {E} un ensemble fini de cardinal {n}.
Calculer le nombre de couples {(A,B)} de parties de E tels que:
1) {A\subset B} (deux démonstrations)\quad 2) {A\cap B= \emptyset}\quad 3) {A\cap B\ne \emptyset}.
Cliquer ici pour voir (ou cacher) le corrigé

    • Fixons {\text{card}(A)=k}. Il y a {\dbinom{n}{k}} manières de choisir {A\subset E}.

      Il y a alors {2^{n-k}} manières de choisir une partie {B} du complémentaire de {A}.

      Si {\text{card}(A)=k}, le nombre de couples {(A,B)} est donc {\dbinom{n}{k}2^{n-k}}.

      Mais on peut faire varier {k} de {0} à {n}.

      Le nombre de solutions au problème posé est donc : { \displaystyle\sum_{k=0}^{n}\dbinom{n}{k}2^{n-k}=(1+2)^n=3^n}

    • Au vu du résultat précédent, on peut penser qu’il y a une autre démonstration.

      Soit {\mathcal F} l’ensemble des applications de {E} dans {\{1,2,3\}}.

      Le cardinal de l’ensemble {\mathcal F} est {3^n}.

      Un élément {f} de {\mathcal F} est déterminé de manière unique par {A=f^{-1}(\{1\})} et {B=f^{-1}(\{2\})}, c’est-à-dire par un couple {(A,B)} de deux parties disjointes de {E}. On en déduit le résultat.

  1. Il y a {2^n\cdot2^n=4^n} couples {(A,B)} de parties quelconques de {E}.

    Compte tenu de la question précédente, le nombre de couples {(A,B)} tels que {A\cap B\ne\emptyset} est donc égal à {4^n-3^n}.

  2. Etant donné une partie {A} de {E}, une partie {B} de {E} contenant {A} est déterminée de manière unique par {B\setminus A}, c’est-à-dire par une partie de {E} disjointe de {A}.

    Il y a donc autant de solutions que dans la question (1), c’est-à-dire {3^n}.

Exercice 2.
Soit {E} un ensemble fini de cardinal {n}. Déterminer le nombre :

  • de partitions {(A,B)} de {E} ({A\cup B=E} et {A\cap B=\emptyset}).
  • de recouvrements {(A,B)} de {E} ({A\cup B=E}).

Cliquer ici pour voir (ou cacher) le corrigé

  • Se donner une partition {(A,B)} en deux parties {A,B} de {E} c’est en fait se donner une partie quelconque {A} de {E} (puisqu’on a nécessairement {B=\overline A}).

    Le nombre de solutions est donc {2^n}.

  • Soit {A} une partie de {E} ayant {k} éléments, avec {0\le k\le n}.

    Choisir une partie {B} de {E} telle que {A\cup B=E}, c’est en fait réunir {\overline A} et une partie quelconque de {A} (qui correspond à {B\setminus A}).

    Il y a {\dbinom{n}{k}} manières de choisir {A}, puis {2^k} manières de choisir {B}.

    On fait varier {k} de {0} à {n}.

    Le nombre de solutions est donc : { \displaystyle\sum_{k=0}^{n}\dbinom{n}{k}2^k=(1+2)^n=3^n}.

Exercice 3.
Soit {E} un ensemble fini de cardinal {n}. Calculer le nombre de triplets {(A,B,C)} de parties de E telles que {A\cup B\cup C=E}.
Cliquer ici pour voir (ou cacher) le corrigé
Il revient au même de résoudre {\begin{cases}A\cup B=X\cr X\cup C=E\end{cases}}, où {X\subset E}.

Si on suppose que {\text{card}(X)=k}, le nombre de couples {(A,B)} tels que {A\cup B=X} est égal à {3^k} (résultat de la deuxième question de l’exercice précédent).

Le nombre de {C\subset E} tels que {X\cup C=E} est {2^k} (on réunit {\overline X} à une partie quelconque de {X}).

De plus il y a {\dbinom{n}{k}} manières de choisir {X} tel que {\text{card}(X)=k}.

On fait varier {k} de {0} à {n}.

Le nombre de solutions est donc : { \displaystyle\sum_{k=0}^{n}\dbinom{n}{k}3^k2^k=(1+6)^n=7^n}.