CultureMath

Vous pouvez retrouver cette question au format pdf.

Question du jeudi #52 : Soit $\Omega$ un ensemble à $n$ éléments. Combien y a-t-il de couples $(A,B)$ de parties de $\Omega$ telles que $A \cup B = \Omega$ ?

Si $A \cup B = \Omega$, les éléments de $\Omega$ sont de trois types :

• les éléments appartenant à $A$ mais pas à $B$ ; nous dirons qu'un tel élément est bleu ;
• les éléments appartenant à $B$ mais pas à $A$ ; nous dirons qu'un tel élément est rouge ;
• les éléments appartenant à la fois $A$ et $B$ ; nous dirons (logiquement) qu'un tel élément est magenta.

Remarquons que rien n'oblige toutes les couleurs à être représentées. Par exemple, si $A = B = \Omega$, tous les éléments sont magenta.

Réciproquement, si nous colorons arbitrairement tous les éléments de $\Omega$ en bleu, rouge et magenta, il est facile de construire des parties $A$ et $B$ qui redonneront ce coloriage. En effet, il suffit de prendre pour $A$ l'ensemble des éléments bleus ou magenta et pour $B$ l'ensemble des éléments rouges ou magenta.

Ainsi, il y a autant de couples de parties $(A,B)$ telles que $A \cup B = \Omega$ que de coloriages des éléments de $\Omega$ en trois couleurs. Un tel coloriage n'étant rien d'autre qu'une fonction $\Omega \to$ {bleu, rouge, magenta} il y en a exactement $3^n$.