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... Licence Maths 1e ann AlgèbreTopics traitant de algèbre [tout]Lister tous les topics de mathématiques
Niveau Licence Maths 1e ann
Partager :

Dénombrement

Posté par
jsvdb 02-07-18 à 12:22

Bonjour à tous
J'ai vu que certains d'entre vous étaient sur des problèmes de cardinalité et de dénombrement.

Je vous propose de résoudre celui-là :

Citation :
Pour tout n entier strictement positif, calculer :

\Large C_n = \sum_{X\in \mathfrak P([\![1;n]\!])}{{\sum_{k\in X}{k}}


Indication :

Poser, pour k\in [\![1;n]\!] et X \in \mathfrak P([\![1;n]\!]), la quantité suivante :

\mathbf 1_X(k) = \begin{cases}1 & \text{ si } k\in X \\ 0 & \text{ si } k \notin X  \end{cases}

qui permet une interversion de sommes.

Posté par
Zrunre : Dénombrement 02-07-18 à 12:49

On peut remarquer que pour un certain k \in [\![1,n]\!] fixé , il y a 2^{n-1} parties de E qui le contient donc chaque k apparaît 2^{n-1} fois d?où le résultat immédiatement ... (je ne le met pas pour ceux qui veulent le trouver par eux même)

Posté par
Alishisapre : Dénombrement 02-07-18 à 13:02

Bonjour, rien à voir (j'essaierai de le résoudre cependant),

le code 

[\![
donne : [\![

pour info. J'avais vu ça et j'ai trouvé ça sympa.

Posté par
jsvdbre : Dénombrement 02-07-18 à 13:54

Résultat immédiat, certes, ce n'est pas la mer à boire, mais il faut quand même l'ecrire ...

Posté par
Jezebethre : Dénombrement 02-07-18 à 13:56

Bonjour

Alishisap @ 02-07-2018 à 13:02

Bonjour, rien à voir (j'essaierai de le résoudre cependant),

le code 
[\![
donne : [\![

pour info. J'avais vu ça et j'ai trouvé ça sympa.

Merci beaucoup, très utile.


Quant à l'exercice j'aboutis aussi avec la même méthode que Zrun.

Posté par
jsvdbre : Dénombrement 02-07-18 à 13:58

Ceci dit, l'idée intuitive est bien vue.

Posté par
Alishisapre : Dénombrement 02-07-18 à 19:58

Je conjecture :

C_n=(n+1)(1+2+3+...+n)=\dfrac{n(n+1)^2}{2}

Cohérent avec C_3=24 à la main.

Je démontrerai ça plus tard.

Posté par
Jezebethre : Dénombrement 02-07-18 à 20:16

Hélas… c'est faux !

Posté par
Alishisapre : Dénombrement 02-07-18 à 20:55

Il y a alors quelque chose qui m'échappe dans cette double sommation.

Si n=2 alors on a 2^2=4 sommes à calculer :

X = {} : 0
X = {1} : 1
X= {2} : 2
X = {1 2} : 3

Et si on somme le tout ça fait 1+2+3 = 6.

Non ?

Posté par
Alishisapre : Dénombrement 02-07-18 à 21:31

Ok, ça serait plutôt C_n=n(n+1)2^{n-2}

Marrant que n=3 soit l'unique rang non nul où ma formule et la bonne réponse coïncident.

Démo à venir.

Posté par
Jezebethre : Dénombrement 02-07-18 à 21:55

Alishisap @ 02-07-2018 à 21:31

Ok, ça serait plutôt C_n=n(n+1)2^{n-2}



j'ai ça aussi

Posté par
Zrunre : Dénombrement 02-07-18 à 22:10

jsvdb @ 02-07-2018 à 13:54

Résultat immédiat, certes, ce n'est pas la mer à boire, mais il faut quand même l'ecrire ...


Je ne sais pas comment blanker ... mais avec ce que j'avais écrit le calcul restant était une trivialité ...

Posté par
jsvdbre : Dénombrement 02-07-18 à 22:23

Ce qui est trivial pour toi ne l'est pas forcément pour tes voisins 😉
Certes l'idee Intuitive est bien celle que tu dis et c'est la clé de la démonstration, mais il faut le rédiger.

Posté par
Jezebethre : Dénombrement 02-07-18 à 22:24

En particulier c'est fait avec ou sans l'interversion que préconisait jsvdb ?

Posté par
Alishisapre : Dénombrement 02-07-18 à 22:25

Voici ma démo.

Soit \Omega:n\mapsto \mathfrak P([\![1;n]\!]), n naturel non nul.
Pour tout n naturel non nul, |\Omega (n)|=2^n
Soit k\in[\![1;n]\!].
Parmi les sous-ensembles de \Omega (n) de cardinal 1, k n'apparaît qu'une fois.
Parmi ceux de cardinal 2, k apparaît n fois.
Et ainsi de suite.
On peut ainsi établir que parmi les sous ensembles de \Omega (n) de cardinal s\in[\![1;n]\!], k apparaît C_{s-1}^{n-1} fois.

Donc k apparaît dans \sum\limits_{s=1}^n C_{s-1}^{n-1}=\sum\limits_{s=0}^{n-1} C_{s}^{n-1}=2^{n-1} sous-ensembles de \Omega (n).

Et par conséquent C_n=2^{n-1}(1+2+...+n)=n(n+1)2^{n-2} en simplifiant.

Posté par
Alishisapre : Dénombrement 02-07-18 à 22:29

A noter que le passage

Citation :
On peut ainsi établir que parmi les sous ensembles de \Omega (n) de cardinal s\in[\![1;n]\!], k apparaît C_{s-1}^{n-1} fois.

mériterait certainement des justifications, mais c'est lourd à faire.

Posté par
jsvdbre : Dénombrement 02-07-18 à 22:31

@Alishisap : c'est le bon résultat avec le développement de l'idée préconisée. Néanmoins cette présentation reste trop sur le côté intuitif...

Posté par
Jezebethre : Dénombrement 02-07-18 à 22:50

Oui, je vois difficilement comment on peut se passer de l'interversion.

Posté par
Zrunre : Dénombrement 02-07-18 à 22:53

Jezebeth @ 02-07-2018 à 22:50

Oui, je vois difficilement comment on peut se passer de l'interversion.

L'intervertion semble essentielle pour avoir une démonstration propre du résultat ...

Posté par
jsvdbre : Dénombrement 02-07-18 à 22:53

Je reprends mes notations initiales et note \mathfrak P([[1;n]]) = \mathfrak P_n


\begin{aligned} \sum_{X\in \mathfrak P_n}{\sum_{k\in X}{k}} & = \sum_{X \in \mathfrak P_n}{\sum_{k=1}^{n}}k.\mathbf 1_X(k) \\ & =\sum_{k=1}^{n}\sum_{X \in \mathfrak P_n}k.\mathbf 1_X(k) \\ & = \sum_{k=1}^{n}k\sum_{X \in \mathfrak P_n}\mathbf 1_X(k) \\ & = \sum_{k=1}^{n}k\textbf{Card}\{X \in \mathfrak P_n~/~k\in X\} \end{aligned}

Or, pour k fixé dans [[1;n]], il y a exactement 2^{n-1} parties de [[1;n]] qui contiennent k, et autant qui ne contiennent pas k : c'est un résultat connu ou bien, si pas évident, considérer la bijection suivante :

f_k : \begin{cases}\{X\in \mathfrak P_n~/k\notin X\}\rightarrow \{X\in \mathfrak P_n~/k\in X\}  \\ A \mapsto A \cup \{k\}  \end{cases}

Ceci permet de conclure car  \textbf{Card }(\mathfrak P_n) = 2^n. Il vient :


\blue \boxed{\begin{aligned} \sum_{X\in \mathfrak P_n}{\sum_{k\in X}{k}} & = \sum_{k=1}^{n}k2^{n-1} \\ & = 2^{n-1}\dfrac{n(n+1)}{2} \end{aligned}}


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 1674 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 !