n*2^(n-1).
Il suffit d'isoler un élément au hasard et de compter le nombre de fois qu'il intervient dans un groupe.

Salut,
Il s'agit donc d'analyser combien de fois le même élément sera compté.
Un élément se trouve dans 2^(n-1)sous ensemble différents.
Donc n*2^(n-1) nous donne la somme des cardinaux de toutes les parties.

Je propose deux solutions (la deuxième est mieux):


I)

Soit [latex]S(n)[/latex] la somme des cardinaux des parties d'un ensemble à [latex]n[/latex] éléments.

Soit [latex]n[/latex] entier positif. Soit [latex]E[/latex] un ensemble à [latex]n+1[/latex] éléments. Soit [latex]e[/latex] un élément de [latex]E[/latex].
Je sépare les parties de [latex]E[/latex] en deux groupes: celles qui ne contiennent pas [latex]e[/latex] et celles qui contiennent [latex]e[/latex].
La somme des cardinaux des parties qui ne contiennent pas [latex]e[/latex] est tout simplement [latex]S(n)[/latex].
La somme des cardinaux des parties qui contiennent [latex]e[/latex] est [latex]S(n)+2^n[/latex] car le nombre de parties qui contiennent [latex]e[/latex] est [latex]2^n[/latex].

Donc [latex]S(n+1)=2.S(n)+2^n[/latex].

On a S(0)=0.
On en déduit que [latex]S(n)=n.2^{n-1}[/latex].


II)

Soit [latex]n[/latex] entier positif. Soit [latex]E[/latex] un ensemble à [latex]n[/latex] éléments.
Soit [latex]e[/latex] un élément de [latex]E[/latex].
[latex]e[/latex] apparait dans [latex]2^{n-1}[/latex] parties. Sa contribution pour la somme des cardinaux des parties de [latex]E[/latex] s'élève donc à [latex]2^{n-1}[/latex].
Je somme les contributions de chaque élément de [latex]E[/latex], il y en a [latex]n[/latex], donc la somme des cardinaux des parties de [latex]E[/latex] est [latex]n.2^{n-1}[/latex].

Alors, tout d'abord, pour un ensemble [latex]E[/latex] à [latex]n[/latex] éléments, il y à [latex]\binom{n}{k}[/latex] ensembles à [latex]k[/latex] éléments dans les parties de [latex]E[/latex]. La somme recherché est donc:
[TeX]\sum_{k=1}^n k*{\binom{n}{k}}
= \sum_{k=1}^n k*{\frac{n!}{k!*(n-k)!}}
= \sum_{k=1}^n {\frac{n!}{(k-1)!*(n-k)!}}
= \sum_{k=1}^n {\frac{n*(n-1)!}{(k-1)!*((n-1)-(k-1))!}}
= n*{\sum_{k=0}^{n-1} {\binom{n-1}{k}}}
=n*2^{n-1}[/TeX]
Jolie problème

Il n'y a pas besoin de coefficients binomiaux!

Instinctivement, [latex]n2^{n-1}[/latex].



Bon, maintenant, soyons un peu futé... Il y a [latex]2^n[/latex] sous-ensembles, ça se démontre très facilement (on crée un sous-ensemble en choisissant de prendre ou pas chaque élément, donc deux choix possibles pour chacun des éléments, et hop).

Sans même faire les calculs de combinatoire, on sait qu'il y a autant de sous-ensembles a [latex]k[/latex] éléments que de sous ensembles a [latex]n-k[/latex] éléments. Pourquoi ? Parce qu'un sous-ensemble a [latex]k[/latex] éléments est inévitablement le complémentaire d'un et un seul sous-ensemble a [latex]n-k[/latex] éléments. Donc, si on a [latex]M_k[/latex] sous-ensembles a [latex]k[/latex] éléments, on a aussi [latex]M_k[/latex] sous-ensembles a [latex]n-k[/latex] éléments (autrement dit, [latex]M_{n-k} = M_k[/latex] : on obtiendrait la même chose avec la combinatoire, mais bon, pas la peine...).

Cette symétrie particulière nous permet d'arriver au résultat annoncé de deux façons.

--> La première consiste a dire qu'un sous-ensemble contient en moyenne [latex]\frac{n}{2}[/latex] éléments, puisque chaque sous-ensemble a son "symétrique", c'est-a-dire un sous-ensemble qui forme avec lui une partition de l'ensemble de départ. On multiplie ce cardinal moyen d'un sous-ensemble par le nombre de sous-ensembles, on simplifie par 2 la fraction obtenue, et hop.

--> La deuxième, plus "rigoureuse", consisterait en le calcul direct du nombre [latex]S[/latex] que l'on cherche en regroupant les sous-ensembles selon leur nombre [latex]k[/latex] d'éléments (qu'on n'a même pas besoin d'exprimer en fonction de [latex]n[/latex] et de [latex]k[/latex], adieu la combinatoire) :
[TeX]S = 0 \times M_0 + 1 \times M_1 + \dots + (n-1) \times M_{n-1} + n \times M_n[/TeX]
Ensuite, on rassemble les "anti-jumeaux" :
[TeX]S = \left( 0 \times M_0 + n \times M_n \right) + \left( 1 \times M_1 + (n-1) \times M_{n-1} \right) + \dots + P[/TeX]
Le terme "du milieu" [latex]P[/latex] diffèrera selon que [latex]n[/latex] est pair ou impair ; dans le premier cas, il vaudra :
[TeX]P = \frac{n}{2} \times M_{\frac{n}{2}}[/TeX]
Dans le second :
[TeX]P = \frac{n-1}{2} \times M_{\frac{n-1}{2}} + \frac{n+1}{2} \times M_{\frac{n+1}{2}}[/TeX]
On utilise ensuite les égalités [latex]M_0 = M_n[/latex], [latex]M_1 = M_{n-1}[/latex], etc. pour faire un petit passe-passe, illustré ici pour le premier terme :
[TeX]0 \times M_0 + n \times M_n = 0 \times \left( \frac{M_0 + M_n}{2} \right) + n \times \left( \frac{M_0 + M_n}{2} \right) = \frac{n}{2} \left( M_0 + M_n \right)[/TeX]
Idem avec tous les autres, pour finalement obtenir, dans les deux cas :
[TeX]S = \frac{n}{2} \sum_{k=0}^n M_k[/TeX]
La somme est le nombre total de sous-ensembles, soit [latex]2^n[/latex], et hop.



Intéressant... Et, pour moi qui suis une quiche en géométrie, reposant

Ce n'est pas grosso modo ce que Rivas a déjà fait ?

MthS-MlndN a écrit:

Ce n'est pas grosso modo ce que Rivas a déjà fait ?

Ben, quand j'ai posté ça, je ne savais pas encore ce que Rivas avait fait; mais cette méthode est indubitablement différente et plus directe que la première méthode postée par mes soins un peu avant

To-do list des choses à faire dans ma vie:
Caser le mot indubitablement dans un forum => Done
Prochain mot: Phtisiologie


Edit: et j'ai regardé ce qu'a fait Rivas, et c'est légèrement différent. On sait tous comment Gauss aurait fait la somme des 100 premiers entiers : en calculant son double, et en groupant les termes 2 par 2. Ici, on peut faire un peu pareil, comme Mathias le faisait remarquer dans sont post en fait. Du coup, on calcule 2S comme étant n*2^n et c'est tout bon

scarta a écrit:

MthS-MlndN a écrit:

Ce n'est pas grosso modo ce que Rivas a déjà fait ?

Ben, quand j'ai posté ça, je ne savais pas encore ce que Rivas avait fait; mais cette méthode est indubitablement différente et plus directe que la première méthode postée par mes soins un peu avant

OK, mea culpa