Somme de cardinaux - intersection — Les-mathematiques.net The most powerful custom community solution in the world

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

Réponses

  • Il suffit de faire les changements de variables évidents, ce qui ne change pas la somme.
  • En quelque sorte, cela revient à "réordonner" la somme...
  • 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
  • Bonjour,

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

    A+
  • Non ça fait $1+1+1+1+1+1+2=8$.
  • 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+
  • Bah les probabilités uniformes sur un ensemble fini c'est de la combinatoire au final, tu vas tourner en rond !
  • 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+
  • 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.
  • 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+
  • 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+
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!