Formule de Poincaré

Jota · September 2019

Salut
J'ai commencé à démontrer la formule de Poincaré, mais je me suis buté à un niveau.
En utilisant le raisonnement par récurrence, c'est au niveau de l'hérédité que je bloque. Voici ce que j'ai fait :
$Card(\bigcup_{k=1}^{n+1}{E_{k}})= Card((\bigcup_{k=1}^{n}{E_{k}})\bigcup{E_{n+1}})$
$= Card(\bigcup_{k=1}^{n}{E_{k}})+Card(E_{n+1})- Card((\bigcup_{k=1}^{n}{E_{k}})\bigcap{E_{n+1}})$
$=\sum_{k=1}^{n}{(-1)^{k+1}S_{n,k}} + Card(E_{n+1}) - Card(\bigcup_{k=1}^{n}{(E_{k}}\bigcap{E_{n+1})})$
$=\sum_{k=1}^{n}{(-1)^{k+1}S_{n,k}} + Card(E_{n+1}) - \sum_{k=1}^{n}{(-1)^{k+1}S'_{n,k}}$
où $S'_{n,k} = \sum_{1 \leq i_{1} <\cdots< i_{k} \le n}{Card[(E_{i_{1}}\bigcap{E_{n+1}})\bigcap\cdots\bigcap{(E_{i_{1}}\bigcap{E_{n+1}})}]}$

Merci d'avance pour toute votre aide.

Math Coss · September 2019

Peut-être devrais-tu expliciter ces égalités pour $n=2$ ?

La formule du crible exprime le cardinal de la réunion comme une somme alternée des cardinaux des intersections $\bigcap_{K}E_K$, où $K$ parcourt les parties non vides $\{i_1<\cdots<i_k\}$ de $\{1,\dots,n\}$ et $E_K=E_{i_1}\cap\cdots\cap E_{i_k}$.

En gros, tu vois apparaître trois type de parties de $\{1,\dots,n+1\}$ :

dans la somme des $S_{n,k}$ apparaissent les parties qui ne contiennent pas $n+1$ ;
dans la somme des $S'_{n,k}$ apparaissent les parties qui contiennent $n+1$ et au moins un élément de $\{1,\dots,n\}$ ;
le terme esseulé $\mathrm{Card}(E_{n+1})$ correspond à la partie $\{n+1\}$.

Ces trois types de parties sont distincts et toute partie non vide de $\{1,\dots,n+1\}$ est de l'un (et un seul) de ces types. Reste à vérifier que tout va bien avec les signes.

Jota · September 2019

Salut Math Coss, désolé mais je n'arrive pas à te suivre.

Homo Topi · September 2019

Ouvre ce lien.

Tu vois trois ensembles qui s'intersectent deux par deux, et tous les trois en même temps. C'est le cas $n=3$.

Pour compter les éléments de $A \cup B \cup C$, tu vas compter ceux de $A$, ceux de $B$, et ceux de $C$ pour commencer. Mais en faisant ça, tu en as compté un paquet en double : quand tu comptes ceux de $A$, puis ceux de $B$, tu comptes deux fois ceux dans $A \cap B$ ! Donc il faut retirer ça une fois. MAIS en faisant ça, tu as retiré les éléments de $A \cap B \cap C$, que tu avais compté trois fois (une fois pour $A$, une fois pour $B$, une fois pour $C$), trois fois (une fois pour $A \cap B$, une fois pour $A \cap C$, une fois pour $B \cap C$) donc il faut les recompter encore une fois pour ne pas les oublier.

Ça donne : $\#(A \cup B \cup C) = \bigg[ \#A + \#B + \#C \bigg] - \bigg[ \#(A \cap

+ \#(A \cap C) + \#(B \cap C) \bigg] + \#(A \cap B \cap C)$

La formule du crible s'établit par récurrence une fois qu'on a compris comment écrire ce principe avec une somme qui change de signe à chaque indice.

Math Coss · September 2019

Commençons par expliciter cette égalité pour $n=2$. (Peut-être aurais-tu pu faire ça à ma place.) Je note $|X|$ le cardinal d'un ensemble $X$, c'est plus court que $\mathrm{card}(X)$. On a donc : \begin{align*}
|E_1\cup E_2\cup E_3|&=\bigl|(E_1\cup E_2)\cup E_3\bigr|\\
&=|E_1\cup E_2|+|E_3|-\bigl|(E_1\cup E_2)\cap E_3\bigr|\\
&=|E_1\cup E_2|+|E_3|-\bigl|(E_1\cap E_3)\cup (E_2\cap E_3)\bigr|\\
&=\underbrace{|E_1|+|E_2|-|E_1\cap E_2|}_{\text{parties de }\{1,2\}}+\underbrace{|E_3|}_{\{3\}}-\Bigl[\underbrace{|E_1\cap E_3|+|E_2\cap E_3|-|E_1\cap E_2\cap E_3|}_{\text{parties de }\{1,2,3\}\ \text{contenant $3$ et au moins un autre}}\Bigr].
\end{align*}Pour comprendre ce qui est indiqué « parties de... », il faut regarder la liste des indices $i$ des $E_i$ qui apparaissent. Sous la première accolade, c'est la somme que tu as notée $S_{n,k}$ (pas trop précisément) ; sous la troisième, $S'_{n,k}$.

Ce qui te bloque, c'est peut-être la formulation-même du théorème. Constate que si $k\ge1$, se donner une $k$-liste $1\le i_1<i_2<\cdots<i_k\le n$, c'est exactement se donner une partie à $k$ éléments de $\{1,\dots,n\}$ – la partie $\{i_1,\dots,i_k\}$. En effet, il n'y a qu'une seule façon de numéroter les entiers d'une partie $K$ de façon strictement croissante. On peut récrire la formule en compactant la somme sur $k$ et la somme sur les $k$-listes croissantes $i_1<\cdots<i_k$ en une seule somme sur $K$ : \[\bigl|E_1\cup\cdots \cup E_n\bigr|=
\sum_{K\ne\emptyset}(-1)^{|K|-1}\bigl|E_K\bigr|\] où la somme porte sur les parties non vides de $\{1,\dots,n\}$ et où,
\[\text{pour}\ K=\{i_1,\dots,i_k\},\quad E_K=E_{i_1}\cap \cdots\cap E_{i_k}.\]

GaBuZoMeu · September 2019

Bonjour,

Ce qui te bloque peut-être, c'est que tu ne remarques pas que
$$\sum_{1\leq i_1<\ldots<i_k<n}\left|(E_{i_{1}}\cap{E_{n+1}})\cap\cdots\cap{(E_{i_{k}}\cap{E_{n+1}})}\right|=\sum_{1\leq i_1<\ldots<i_k<i_{k+1}=n+1} \left|E_{i_1}\cap\cdots\cap E_{i_k}\cap E_{i_{k+1}}\right|\;.$$