Somme de cardinaux - intersection

Souki · January 2012

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)$ ???

GreginGre · January 2012

Il suffit de faire les changements de variables évidents, ce qui ne change pas la somme.

skysurf3000 · January 2012

En quelque sorte, cela revient à "réordonner" la somme...

Souki · January 2012

oui, je vois, au lieu d'ordonner les parties de E, en commençant par exemple par la partie vide, les singletons, les doublets ... E, on commence par E, les parties à $n-1$ éléments ... jusqu'à les doublets, singletons, et la partie vide

Piteux_gore · June 2020

Bonjour,

Quel résultat doit-on trouver pour un ensemble à deux éléments ? Je trouve $6$, mais j'aimerais confirmation.

A+

Poirot · June 2020

Non ça fait $1+1+1+1+1+1+2=8$.

Piteux_gore · June 2020

RE

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+

Poirot · June 2020

Bah les probabilités uniformes sur un ensemble fini c'est de la combinatoire au final, tu vas tourner en rond !

Piteux_gore · June 2020

RE

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+

bisam · June 2020

Le plus simple est d'utiliser des variables aléatoires de Bernoulli attestant de la présence ou non d'un élément donné dans un ensemble. Ces variables seront alors mutuellement indépendantes.
On obtient donc les moyennes que tu veux par linéarité de l'espérance.

Piteux_gore · June 2020

RE

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+

Piteux_gore · June 2020

RE

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+

Somme de cardinaux - intersection

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 9