Somme de cardinaux - intersection
Bonsoir tout le monde,
en feuilletant un livre de maths, je tombe sur une proposition que je ne saisis pas très bien : c'est en relation avec les cardinaux.
Soit $E$ un ensemble fini de cardinal n.
Pour calculer $S = \sum\limits_{(X,Y) \in (P(E))^2} card (X \cap Y)$, on dit que la bijection qu'est le passage au complémentaire permet d'écrire $S=\sum\limits_{(X,Y) \in (P(E))^2} card (\bar X \cap Y)=\sum\limits_{(X,Y) \in (P(E))^2} card (X \cap \bar Y)=\sum\limits_{(X,Y) \in (P(E))^2} card (\bar X \cap \bar Y)$
et vu que $\bar X \cap Y$, $X \cap \bar Y$, $\bar X \cap \bar Y$ et $X \cap Y$ représentent une partition de $E$, on peut calculer la somme de leur cardinaux et en déduire S. Ce qui m'embête c'est cette bijection dont on parle. C'est une bijection, oui, mais pourquoi est ce qu'on à $S=\sum\limits_{(X,Y) \in (P(E))^2} card (\bar X \cap Y)=\sum\limits_{(X,Y) \in (P(E))^2} card (X \cap \bar Y)=\sum\limits_{(X,Y) \in (P(E))^2} card (\bar X \cap \bar Y)$ ???
en feuilletant un livre de maths, je tombe sur une proposition que je ne saisis pas très bien : c'est en relation avec les cardinaux.
Soit $E$ un ensemble fini de cardinal n.
Pour calculer $S = \sum\limits_{(X,Y) \in (P(E))^2} card (X \cap Y)$, on dit que la bijection qu'est le passage au complémentaire permet d'écrire $S=\sum\limits_{(X,Y) \in (P(E))^2} card (\bar X \cap Y)=\sum\limits_{(X,Y) \in (P(E))^2} card (X \cap \bar Y)=\sum\limits_{(X,Y) \in (P(E))^2} card (\bar X \cap \bar Y)$
et vu que $\bar X \cap Y$, $X \cap \bar Y$, $\bar X \cap \bar Y$ et $X \cap Y$ représentent une partition de $E$, on peut calculer la somme de leur cardinaux et en déduire S. Ce qui m'embête c'est cette bijection dont on parle. C'est une bijection, oui, mais pourquoi est ce qu'on à $S=\sum\limits_{(X,Y) \in (P(E))^2} card (\bar X \cap Y)=\sum\limits_{(X,Y) \in (P(E))^2} card (X \cap \bar Y)=\sum\limits_{(X,Y) \in (P(E))^2} card (\bar X \cap \bar Y)$ ???
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Quel résultat doit-on trouver pour un ensemble à deux éléments ? Je trouve $6$, mais j'aimerais confirmation.
A+
Effectivement, la formule générale est $n4^{n - 1}$ pour l'intersection et $3n4^{n - 1}$ pour la réunion.
La technique du complémentaire permet aussi de calculer la somme des cardinaux des parties d'un ensemble ($n2^{n - 1}$) autrement que par le polynôme $(X+1)^n$.
Sauf erreur de ma part, le cardinal moyen d'une partie est donc $n/2$, le cardinal moyen de l'intersection de deux parties est donc $n/4$, etc. Peut-on retrouver ces résultats par les probabilités pures ?
A+
Il y a autant de parties à $0$ élément que de parties à $n$ éléments : moyenne = $n/2$
Il y a autant de parties à $1$ élément que de parties à $n - 1$ éléments : moyenne = $n/2$
Il y a autant de parties à $2$ élément que de parties à $n - 2$ éléments: moyenne = $n/2$..
Etc.
Donc le cardinal moyen est $n/2$.
Si mon raisonnement est bon, alors on trouve la formule de la somme des cardinaux par
$2^n.n/2$.
Reste à prouver que le cardinal moyen de l'intersection est égal à $(n/2)/2$.
Peut-on alors écrire, en se basant sur la formule Card(union) = Somme(Card) - Card(intersection), que
le cardinal moyen de l'union est égal à $n/2 + n/2 - n/4 = 3n/4$ ?
A+
On obtient donc les moyennes que tu veux par linéarité de l'espérance.
Prenons l'exemple de la partie $(2, 3)$ de l'ensemble $(1, 2, 3)$ :
- elle a $0$ élément commun avec le vide et la partie $(1)$, et deux éléments communs avec elle-même et le plein, ce qui donne la moyenne $(0 + 0 + 2 + 2)/4 = 1$;
- elle a $1$ élément commun avec les quatre autres parties, ce qui donne la moyenne $(1 + 1 + 1 + 1)/4 = 1$;
- l'intersection moyenne de $(2, 3)$ avec une partie de $(1, 2, 3)$ est donc de cardinal $1 = 2/2$.
On doit pouvoir généraliser ce raisonnement à des parties quelconques d'un ensemble quelconque.
En outre, on a $moy(a_k + b_k - c_k) = moy(a_k) + moy(b_k) - moy(c_k)$ si je ne m'abuse.
A+
Soit $E_n$ un ensemble à $n$ éléments et $E_m$ une partie à $m$ éléments ($m \le n$).
Pour $0 \le k \le m$, $E_m$ coupe en $k$ points et en $m - k$ points $C(m, k).2^{n - m}$ parties de $E_n$, ce qui donne un cardinal total de $2.C(m, k).2^{n - m} + (m - 2).C(m, k).2^{n - m} = m.C(m, k).2^{n - m}$ et un cardinal moyen de $m.C(m, k).2^{n - m}/2.C(m, k).2^{n - m} = m/2$,
Par conséquent, le cardinal moyen de l'intersection d'une partie à $m$ éléments avec les parties de l'ensemble conteneur est $m/2$.
Dans le problème initial, le cardinal moyen d'une intersection est donc $(n/2)/2 = n/4$ et la somme des cardinaux de toutes les intersections vaut $(n/4).4^n = n4^{n - 1}$.
A+