Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Reprise d'études [tout]Lister tous les topics de mathématiques
Niveau Reprise d'études
Partager :

Un exercice sur le dénombrement

Posté par
Autodidacte33 19-12-20 à 00:50

Bonjour ,

Voici un autre exercice sur le dénombrement qui me pose problème à la 2ème question :

Citation :
Les deux questions ne sont pas indépendantes

1) Soit n un entier naturel, montrer que \displaystyle \sum_{k=0}^{n} \begin{pmatrix} n \\k \end{pmatrix} 3^{n-k}k=n4^{n-1}

2) Soit E un ensemble quelconque  et notons n = \text{Card } E . Calculer

                             S=\displaystyle \sum_{X,Y\subset E} \text{ Card }X\cap Y ~~~~~~\text{ et }~~~~~~ T=\displaystyle \sum_{X,Y\subset E} \text{ Card }X\cup Y


J'ai réussi à faire la 1) par récurrence . Je ne vais pas présenter la résolution ici car elle est bien longue

Par contre, pour la 2) , je n'ai vraiment aucune idée !



J'ai tenté ceci , mais ça n'aboutit pas à grand chose :

On sait que \forall X,Y\in \mathcal{P}(E) \text{ : } \text{ Card } (X\cup Y) =\text{ Card } X +\text{ Card } Y -\text{ Card } (X\cap Y)

Donc \displaystyle \sum_{X,Y\subset E} \text{ Card }(X\cup Y)=\displaystyle \sum_{X,Y\subset E} \text{ Card } X +\text{ Card } Y -\text{ Card } (X\cap Y)

Ou encore S+T= \displaystyle \sum_{X\subset E} \text{ Card } X + \sum_{Y\subset E}\text{ Card } Y


J'ai besoin de vos astuces encore une fois   

Merci !

Posté par
ty59847re : Un exercice sur le dénombrement 19-12-20 à 01:28

Il n'y a rien qui saute aux yeux. Pas simple du tout.
Je cherche à voix haute, je n'ai aucune idée de la réponse.

On a fait la 1ère question, et l'énoncé nous dit qu'il y a un lien entre les 2 questions. C'est très important. Dès qu'on voit une piste qui nous rapproche de la 1ère question, il faudra s'accrocher à cette piste.

Dans le calcul de S,  (ou de T, c'est pareil), c'est une somme de plein de nombres.
Combien de nombres y-a-t-il dans cette somme ?  Ca me paraît une première étape assez essentielle.
Entre S et T, c'est parfaitement symétrique. Si S est une somme de p nombres qui valent en moyenne a, alors T sera une somme de p nombres, qui valent en moyenne n-a.
Je ne sais pas si ça va nous aider pour le calcul de S.
Mais une fois qu'on aura trouvé S, T sera normalement assez simple à calculer.
Ensuite, je pense que je me lancerais dans le calcul de S, pour n=3 par exemple, avec un recensement systématique de tous les couples d'ensembles X et Y, pour essayer de dégager une logique.

Posté par
mousse42re : Un exercice sur le dénombrement 19-12-20 à 01:51

Salut

Pour la première question tu n'as pas besoin de récurrence...et ça demande  maximum  2 lignes de calculs (tu fais passer le n du membre de gauche à droite et tu simplifies.

Pour la seconde aucune idée...

Posté par
flightre : Un exercice sur le dénombrement 19-12-20 à 07:12

salut

sans savoir ce que représente X et Y on peut rien calculer

Posté par
matheuxmatoure : Un exercice sur le dénombrement 19-12-20 à 11:03

Autodidacte33

l'idée est sympa mais ta conclusion est fausse :

S+T= \displaystyle \sum_{X,Y\subset E} \text{ Card } X + \sum_{X,Y\subset E}\text{ Card } Y = 2^n (\sum_{X\subset E} \text{ Card } X + \sum_{Y\subset E}\text{ Card } Y ) = 2^{n+1} \sum_{X\subset E} \text{ Card } X

et

\sum_{X\subset E} \text{ Card } X = \sum_{k=0}^{k=n} k {n \choose k} = n 2^{n-1}

d'où

S+T=n \; 2^{2n}

sauf erreur de ma part

Posté par
matheuxmatoure : Un exercice sur le dénombrement 19-12-20 à 11:29

ensuite je dirais qu'on peut calculer
S=\sum_{X,Y\subset E} \text{ Card } (X \cap Y) = \sum_{X\subset E} \left(\sum_ {Y\subset E}\text{ Card }  (X \cap Y) \right)

pour une partie X fixée à k éléments (et il y en n \choose k)

comptabilisons les parties Y qui ont i éléments en communs avec X (0ik)

pour cela on choisit i éléments de X et on complète avec p éléments qui ne sont pas dans X

le nombre de parties ayant i éléments en commun avec X est donc : {k \choose i} \; \sum_{p=0}^{p=n-k}{{n-k} \choose p}={k \choose i} \; 2^{n-k}

et donc, pour cet élément X,

\sum_ {Y\subset E}\text{ Card }  (X \cap Y)=\sum_{i=0}^{i=k} i \;{k \choose i} \; 2^{n-k} =  2^{n-k}  \times  k \; 2{k-1} = k \; 2^{n-1}

et comme il y a n \choose k partie à k éléments, en faisant varie k de 0 à n :

S=\sum_{X,Y\subset E} \text{ Card } (X \cap Y)=\sum_{k=0}^{k=n} \left( {n \choose k} k 2^{n-1} = 2^{n-1} \times n \; 2^{n-1} = n \; 2^{2n-2}

d'où

S= n \; 2^{2n-2}

T= 3\; n \; 2^{2n-2}

sauf erreur de ma part

Posté par
matheuxmatoure : Un exercice sur le dénombrement 19-12-20 à 11:35

(j'ai testé "à la main" pour n=3 et cela a l'air de fonctionner (je sais c'est pas une preuve ) )

Posté par
matheuxmatoure : Un exercice sur le dénombrement 19-12-20 à 11:36

flight

X et Y décrivent toutes les parties de E !

Posté par
matheuxmatoure : Un exercice sur le dénombrement 19-12-20 à 11:46

on remarquera que S = n \; 4^{n-1}

ce qui fait un lien avec la première question et laisse supposer que pour calculer S il y a peut-être une astuce se ramenant à la somme proposée en question 1, mais je ne vois pas !

ma démo est un peu "bourrin" mais pour l'instant je ne vois pas mieux

Posté par
GBZMre : Un exercice sur le dénombrement 19-12-20 à 12:02

Deux méthodes pour calculer S (T s'en déduit par passage aux complémentaires).

La première est celle de l'exercice.
On fixe une partie I de E à k éléments. Combien y a-t-il de parties X, Y de E telles que XY=I ? Ça revient à compter le nombres d'application de E\I dans {1,2,3} : on envoie aE\I sur 1 s'il appartient à X, sur 2 s'il appartient à Y et sur 3 s'il n'appartient ni à l'un ni à l'autre (les trois cas s'excluent l'un l'autre). Je pense que cette indication suffit.

La deuxième me semble plus directe. S est le cardinal de
{ (a,X,Y)ExP(E)xP(E)  | aX et aY}
C'est la somme pour a parcourant E des cardinaux de
{ (X,Y)P(E)xP(E) | aX et aY}
et se donner une partie de E contenant a revient à se donner une partie de E\{a}.
Je pense que ça suffit pour voir le  n x 2n-1 x 2n-1.

Posté par
matheuxmatoure : Un exercice sur le dénombrement 19-12-20 à 14:40

GBZM bien vu

je pense que celle attendue est ta première où on trouve directement
S=\sum_{k=0}^{k=n} {n \choose k} 3^{n-k}

Posté par
GBZMre : Un exercice sur le dénombrement 19-12-20 à 15:53

Tu as oublié un k (le nombre d'éléments de I).
Oui, comme je l'ai écrit, la première méthode est celle de l'exercice.

Posté par
matheuxmatoure : Un exercice sur le dénombrement 19-12-20 à 18:11

ah oui mince... merci GBZM

Posté par
matheuxmatoure : Un exercice sur le dénombrement 19-12-20 à 18:12

mais bon, je garde la mienne aussi ...

ça en fait 3


Rechercher
Menu
Espace membre
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1675 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !