Soit $n\in\mathbb N^*$ et $E$ un ensemble à $n$ éléments.
- Combien y a-t-il de couples $(A,B)\in\mathcal P(E)^2$ ?
- On note $\mathcal I=\{(A,B)\in\mathcal P(E)^2\mid A\subset B\}$. Pour $(A,B)\in\mathcal I$, on pose $\varphi_{A,B}=\mathbf 1_A+\mathbf 1_B$. Montrer que $(A,B)\mapsto\varphi_{A,B}$ est une bijection de $\mathcal I$ sur $\{0,1,2\}^E$ et en déduire $\operatorname{Card}\mathcal I$.
- Calculer $\operatorname{Card}\mathcal I$ d'une seconde façon en regroupant selon le cardinal de $B$, et vérifier la concordance à l'aide de la formule du binôme.
- En déduire, par des bijections simples, le nombre de couples $(A,B)$ tels que $A\cap B=\varnothing$, puis le nombre de couples tels que $A\cup B=E$.
- On pose $S=\sum_{(A,B)\in\mathcal P(E)^2}\operatorname{Card}(A\cap B)$. En écrivant $\operatorname{Card}(A\cap B)=\sum_{x\in E}\mathbf 1_A(x)\mathbf 1_B(x)$, montrer que $S=n4^{n-1}$.
- En déduire $T=\sum_{(A,B)\in\mathcal P(E)^2}\operatorname{Card}(A\cup B)$. Vérifier les valeurs de $S$ et $T$ pour $n=1$.
Si $A\subset B$, la fonction $\mathbf 1_A+\mathbf 1_B$ vaut $2$ sur $A$, $1$ sur $B\setminus A$ et $0$ ailleurs.
$A\cap B=\varnothing$ équivaut à $A\subset E\setminus B$ ; passer aux complémentaires pour la réunion.
Pour $S$, intervertir les deux sommes et compter, pour $x$ fixé, les couples $(A,B)$ avec $x\in A\cap B$.
Pour $T$, utiliser la formule de la réunion et $\sum_{A\subset E}\operatorname{Card}A=n2^{n-1}$.
-
$\operatorname{Card}\big(\mathcal P(E)^2\big)=(2^n)^2=4^n$.
-
Soit $(A,B)\in\mathcal I$ et $x\in E$. Comme $A\subset B$ : si $x\in A$, $\varphi_{A,B}(x)=2$ ; si $x\in B\setminus A$, $\varphi_{A,B}(x)=1$ ; si $x\notin B$, $\varphi_{A,B}(x)=0$. Donc $\varphi_{A,B}\in\{0,1,2\}^E$ et $$A=\varphi_{A,B}^{-1}(\{2\}),\qquad B=\varphi_{A,B}^{-1}(\{1,2\}).$$ Injectivité : ces formules montrent que $(A,B)$ est déterminé par $\varphi_{A,B}$.
Surjectivité : pour $h\in\{0,1,2\}^E$, on pose $A=h^{-1}(\{2\})$ et $B=h^{-1}(\{1,2\})$. Alors $A\subset B$, et pour tout $x$, $\mathbf 1_A(x)+\mathbf 1_B(x)$ vaut $2$ si $h(x)=2$, $1$ si $h(x)=1$, $0$ si $h(x)=0$ : c'est $h(x)$. Donc $\varphi_{A,B}=h$.
Ainsi $\operatorname{Card}\mathcal I=\operatorname{Card}\{0,1,2\}^E=3^n$.
-
On découpe $\mathcal I$ selon $k=\operatorname{Card}B\in\llbracket0,n\rrbracket$ (cas disjoints et exhaustifs). Il y a $\binom nk$ parties $B$ à $k$ éléments, et pour chacune, $A$ est une partie quelconque de $B$ : $2^k$ choix. D'où $$\operatorname{Card}\mathcal I=\sum_{k=0}^n\binom nk2^k.$$ La formule du binôme donne $\sum_{k=0}^n\binom nk2^k1^{n-k}=(2+1)^n=3^n$ : les deux comptages concordent.
-
Pour $A,B\subset E$ : $A\cap B=\varnothing\iff A\subset E\setminus B$. L'application $(A,B)\mapsto(A,E\setminus B)$ est une bijection de $\mathcal P(E)^2$ sur lui-même (elle est sa propre réciproque), qui envoie l'ensemble des couples de parties disjointes exactement sur $\mathcal I$. Il y a donc $3^n$ couples $(A,B)$ avec $A\cap B=\varnothing$.
De même, $A\cup B=E\iff(E\setminus A)\cap(E\setminus B)=\varnothing$, et $(A,B)\mapsto(E\setminus A,E\setminus B)$ est une bijection involutive de $\mathcal P(E)^2$ qui envoie les couples vérifiant $A\cup B=E$ exactement sur les couples de parties disjointes : il y en a $3^n$.
-
On intervertit les sommes finies : $$S=\sum_{(A,B)}\sum_{x\in E}\mathbf 1_A(x)\mathbf 1_B(x)=\sum_{x\in E}\operatorname{Card}\{(A,B)\in\mathcal P(E)^2\mid x\in A\text{ et }x\in B\}.$$ Pour $x$ fixé, une partie contenant $x$ s'écrit de façon unique $\{x\}\cup A'$ avec $A'\subset E\setminus\{x\}$ : il y en a $2^{n-1}$. Le nombre de couples $(A,B)$ avec $x\in A\cap B$ vaut donc $2^{n-1}\times2^{n-1}=4^{n-1}$, et $S=n4^{n-1}$.
-
Avec $\operatorname{Card}(A\cup B)=\operatorname{Card}A+\operatorname{Card}B-\operatorname{Card}(A\cap B)$ : $$T=\sum_{(A,B)}\operatorname{Card}A+\sum_{(A,B)}\operatorname{Card}B-S.$$ Or, $B$ décrivant librement $\mathcal P(E)$, $\sum_{(A,B)}\operatorname{Card}A=2^n\sum_{A\subset E}\operatorname{Card}A=2^n\sum_{k=0}^nk\binom nk=2^n\cdot n2^{n-1}=2n4^{n-1}$ ; de même pour la somme des $\operatorname{Card}B$. Donc $$T=2n4^{n-1}+2n4^{n-1}-n4^{n-1}=3n4^{n-1}.$$ Pour $n=1$, $E=\{x\}$, les $4$ couples sont $(\varnothing,\varnothing)$, $(\varnothing,E)$, $(E,\varnothing)$, $(E,E)$. Les cardinaux des intersections valent $0,0,0,1$ : $S=1=1\times4^0$. Ceux des réunions valent $0,1,1,1$ : $T=3=3\times1\times4^0$.
$4^n$ ; $\operatorname{Card}\mathcal I=3^n$ ; $3^n$ et $3^n$ ; $S=n4^{n-1}$ ; $T=3n4^{n-1}$