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 :

Dénombrement - combinatoire

Posté par
Autodidacte33 13-12-20 à 14:20

Bonjour ,

J'ai trouvé un petit exercice que je n'arrive pas à résoudre , le voici :

Citation :
Soient E un ensemble non vide et t un élément de E et considérons l'application \begin{array} {rccl}\phi :& \mathcal{P}(E)&\rightarrow &\mathcal{P}(E) \\ &X&\mapsto &X\Delta\lbrace{ t \rbrace }\end{array}
où \Delta est la différence symétrique entre deux ensembles

Les deux questions ne sont pas indépendantes

1) Déterminer \phi \circ \phi. Qu'en résulte-t-il pour \phi ?

2) Soit n\in\N^{*}. Montrer combinatoirement que \sum_{\begin{matrix} _{q\in\N} \\ _{2q\leq n}\end{matrix}} ^{} \begin{pmatrix}n\\2q\end{pmatrix}=\sum_{\begin{matrix} _{q\in\N} \\ _{2q+1\leq n}\end{matrix}} ^{} \begin{pmatrix}n\\2q+1\end{pmatrix}


Mon travail :

1) Déterminons \phi\circ \phi

On sait que \Delta est associative et que pour toute partie X de E on a  X \Delta X=\emptyset et X\Delta \emptyset= X  ( démonstrations déjà faites auparavant dans le cours ensembles et applications )

Soit X\in\mathcal{P}(E)
Alors on a \phi\circ \phi (X)=\phi(X\Delta \lbrace{t\rbrace})=(X\Delta\lbrace{t\rbrace}) \Delta\lbrace{t\rbrace} = X\Delta (\lbrace{t\rbrace}\Delta\lbrace{t\rbrace} )=X\Delta \emptyset = X \\

Donc \phi \circ \phi =Id_{\mathcal{P}(E)} , il en résulte que \phi est une involution de \mathcal{P}(E) , et donc une permutation de \mathcal{P}(E) (bijection de \mathcal{P}(E) dans \mathcal{P}(E) )

Pouvez-vous s'il vous plaît me donner une piste pour répondre à la question 2) ? quelle relation avec la 1) ?

Merci beaucoup !

Je rappelle que je suis autodidacte et que les cours que j'ai étudié jusqu'à présent sont :
-  Ensembles et applications
-  Nombres entiers naturels, dénombrement, combinatoire
(Programme classes préparatoires MPSI)

Posté par
GBZMre : Dénombrement - combinatoire 13-12-20 à 14:49

Bonjour,

Peux-tu considérer ce que fait \phi sur les parties de cardinal pair et les parties de cardinal impair de E ?
Pour cela, il est bon de réaliser concrètement ce que fait \phi.

Posté par
Autodidacte33re : Dénombrement - combinatoire 14-12-20 à 16:43

Bonjour GBZM ,
Merci pour l'astuce ! Alors voilà ce que j'ai trouvé en cherchant :

Citation :
Soit X\in\mathcal{P}(E) , on distingue deux cas :

Cas 1 : t\in X , et dans ce cas \phi (X)=X\Delta \lbrace{t\rbrace}=(X\backslash \lbrace{t\rbrace } ) \cup (\lbrace{t\rbrace }\backslash X ) =X\backslash \lbrace{t\rbrace } \cup \emptyset = X\backslash \lbrace{t\rbrace }  

Cas 2 : t\notin X , et dans ce cas \phi (X)=X\Delta \lbrace{t\rbrace}=(X\backslash \lbrace{t\rbrace } ) \cup (\lbrace{t\rbrace }\backslash X ) =X \cup \lbrace{t\rbrace }  

On peut écrire  :

\begin{array}{rccl}\phi: & \mathcal{P}(E) & \longrightarrow& \mathcal{P}(E) \\  & X & \mapsto & \left \lbrace \begin{array}{ll} X\backslash \lbrace{t\rbrace }  & \text{si } t\in X\\ X \cup \lbrace{t\rbrace }  & \text{si } t\notin X \end{array} \right. \end{array}


A partir d'ici , je ne suis pas sûr si ce que j'écris est correcte , et je ne sais pas si ça passe comme preuve ...

Citation :
On a :

\text{Card } \phi (X)=\text{Card } X -1 \text{ si } t\in X puisqu'on omet de X exactement un élément qui est t

\text{Card } \phi (X)=\text{Card } X +1 \text{ si } t\notin X car dans ce cas on "ajoute" à X  un élément qui est t

Donc si \text{Card } X est pair (resp. impair) , alors \text{Card } \phi (X) est impair (resp. pair)


Mais je ne vois toujours pas comment passer à l'égalité demandée   \sum_{\begin{matrix} _{q\in\N} \\ _{2q\leq n}\end{matrix}} ^{} \begin{pmatrix}n\\2q\end{pmatrix}=\sum_{\begin{matrix} _{q\in\N} \\ _{2q+1\leq n}\end{matrix}} ^{} \begin{pmatrix}n\\2q+1\end{pmatrix}

Merci

Posté par
GBZMre : Dénombrement - combinatoire 14-12-20 à 16:54

Vrai, tu ne vois pas ?

Si E a n éléments, quel est le nombres de parties de E de cardinal pair ?

Posté par
Autodidacte33re : Dénombrement - combinatoire 16-12-20 à 12:42

Salut!

Je suis votre piste GBZM  

Citation :
Si E a n éléments, alors \text{ Card }\mathcal{P}(E)=2^{n}

Posons :

* \mathcal{P}_{P}(E) l'ensemble des parties de E de cardinal pair

* \mathcal{P}_{I}(E) l'ensemble des parties de E de cardinal impair

Puisque le cardinal ne peut être que pair ou impair , alors \mathcal{P}_{P}(E)\cup \mathcal{P}_{I}(E)=\mathcal{P}(E)

De plus , le cardinal ne peut être à la fois pair et impair , alors \mathcal{P}_{P}(E) et \mathcal{P}_{I}(E) sont bien évidemment disjoints , alors \text{Card }\mathcal{P}_{P}(E) + \text{Card }\mathcal{P}_{I}(E)=\text{ Card }\mathcal{P}(E) \Rightarrow  \text{Card }\mathcal{P}_{P}(E) + \text{Card }\mathcal{P}_{I}(E)=2^{n}


Si seulement j'avais \phi: \mathcal{P}_{P}(E)\to \mathcal{P}_{I}(E) à la place de \phi: \mathcal{P}(E)\to \mathcal{P}(E) , j'aurais pû dire que

\text{Card }\mathcal{P}_{P}(E) = \text{Card }\mathcal{P}_{I}(E)

Et je ne vois toujours pas comment passer à l'expression demandée avec les sommes ...

Merci !

Posté par
GBZMre : Dénombrement - combinatoire 16-12-20 à 13:36

Tu n'as pas répondu à ma question, que je répète :

Citation :

Si E a n éléments, quel est le nombres de parties de E de cardinal pair ?


Si je te demande le nombre de parties de cardinal 0, ou 2, ou 4, ou 6, je pense que tu saurais répondre. Alors, pourquoi n'ai-je pas de réponse quand je te demande le nombre de parties de cardinal pair ?

Posté par
Autodidacte33re : Dénombrement - combinatoire 17-12-20 à 17:59

Salut,

C'est ce que je voulais trouver justement, mon but était de trouver le cardinal de l'ensemble des parties de E de cardinal pair que j'avais noté  \mathcal{P}_{P}(E).

Bon, d'accord,  je prend deux petits exemples :

Exple 1 : Je pose  E=\lbrace{ a,b,c \rbrace} donc \text{ Card } E=3

Les parties de E de cardinal pair sont :  \emptyset \text{ , }\lbrace {a,b\rbrace } \text{ , }\lbrace {a,c\rbrace}\text{ , } \lbrace b,c\rbrace

Il y en a donc 4=2^{3-1}

Exple 2 : Si Je pose E=\lbrace{ a,b,c,d \rbrace} donc \text{ Card } E=4

Les parties de E de cardinal pair sont :  \emptyset \text{ , }\lbrace {a,b\rbrace } \text{ , }\lbrace {a,c\rbrace}\text{ , } \lbrace a,d\rbrace \text{ , } \lbrace b,c\rbrace\text{ , } \lbrace b,d\rbrace \text{ , } \lbrace c,d\rbrace\text{ , } E

Il y en a 8=2^{4-1}

En généralisant , Je crois que ça donne :

Citation :
si \text{ Card } E= n\in\mathbb{N} , alors \text{ Card }\mathcal{P}_{P}(E)= 2^{n-1}


Ceci n'est bien sûr pas une démonstration !

C'est cela que vous me demandez GBZM ?  

Merci

Posté par
GBZMre : Dénombrement - combinatoire 17-12-20 à 19:22

Non, ce n'est pas cela.  Le résultat est juste, mais il n'est pas démontré.
Et ce n'est pas ce qui est demandé à la question 2.
Mais pourquoi diable t'obstines-tu à ne pas répondre ?
Bon, spécifions un peu plus. Soit E un ensemble à 8 éléments.
Quel est le nombre de partie de E à 0 éléments ?
Quel est le nombre de partie de E à 2 éléments ?
Quel est le nombre de partie de E à 4 éléments ?
Quel est le nombre de partie de E à 6 éléments ?
Quel est le nombre de partie de E à 8 éléments ?
Quel est le nombre total de parties de E de cardinal pair.
Essaie de penser à ces questions en rapport avec la question 2 du problème !!

Posté par
Autodidacte33re : Dénombrement - combinatoire 18-12-20 à 16:28

Bonjour GBZM

Je vous remercie pour votre patience   

C'est évident !

Citation :
Soit E un ensemble à 8 éléments
Le nombre de partie de E à 0 éléments est \begin{pmatrix}8\\0\end{pmatrix}
le nombre de partie de E à 2 éléments est \begin{pmatrix}8\\2\end{pmatrix}
le nombre de partie de E à 4 éléments  est \begin{pmatrix}8\\4\end{pmatrix}
le nombre de partie de E à 6 éléments est  \begin{pmatrix}8\\6\end{pmatrix}
le nombre de partie de E à 8 éléments est \begin{pmatrix}8\\8\end{pmatrix}
le nombre total de parties de E de cardinal pair est \displaystyle  \sum_{k=0} ^{4} \begin{pmatrix}8\\2k\end{pmatrix}=\sum_{\begin{matrix} _{k\in\N} \\ _{2k\leq 8}\end{matrix}} ^{} \begin{pmatrix}8\\2k\end{pmatrix}


En généralisant, dans le cas \text{ Card } E=n \text{ avec }n\in\N
Le nombre total de parties de E de cardinal pair est bien \text{Card }\mathcal{P}_{P}(E)=   \sum_{\begin{matrix} _{q\in\N} \\ _{2q\leq n}\end{matrix}} ^{} \begin{pmatrix}n\\2q\end{pmatrix}

De la même manière, le nombre total de parties de E de cardinal impair est  \text{Card } \mathcal{P}_{I}(E)=   \sum_{\begin{matrix} _{q\in\N} \\ _{2q+1\leq n}\end{matrix}} ^{} \begin{pmatrix}n\\2q+1\end{pmatrix}

Il me reste à prouver qu'il y a égalité .... Je sais que je dois utiliser les résultats trouvés autour de l'application \phi

J'avais trouvé que \begin{array}{rccl}\phi: & \mathcal{P}(E) & \rightarrow& \mathcal{P}(E) \\  & X & \mapsto & \left \lbrace \begin{array}{ll} X\backslash \lbrace{t\rbrace }  & \text{si } t\in X\\ X \cup \lbrace{t\rbrace }  & \text{si } t\notin X \end{array} \right. \end{array} est bijective

Pusique \forall X\in\mathcal{P}(E) \text{ / } \text{Card }X \text{ est pair } \text{ : } \text{ Card }\phi(X) \text{ est impair }

Est-ce-que je peux restreindre l'application à \red\begin{array}{rccl}\tilde{\phi}: & \mathcal{P}_{P}(E) & \rightarrow& \mathcal{P}_{I}(E) \\  & X & \mapsto & \phi(X)\end{array} est dire que \red \tilde{\phi} est bijective , pour conclure ?

Merci !

Posté par
GBZMre : Dénombrement - combinatoire 18-12-20 à 16:34

Tu peux faire tout raisonnement valide, et présentant les arguments idoines.

Posté par
Autodidacte33re : Dénombrement - combinatoire 18-12-20 à 16:48

GBZM @ 18-12-2020 à 16:34

Tu peux faire tout raisonnement valide, et présentant les arguments idoines.
Oui je sais , je demande justement si c'est le cas ?

Puisque \tilde{\phi} est bijective : \text{Card } \mathcal{P}_P(E)=\text{Card } \mathcal{P}_I(E)

D'où le résultat .

Posté par
GBZMre : Dénombrement - combinatoire 18-12-20 à 17:30

Oui, \phi échange pairs et impairs (c'est une bijection, et l'image d'un pair (resp. impair) est un impair (resp. pair)).

Posté par
matheuxmatoure : Dénombrement - combinatoire 18-12-20 à 18:07

bonsoir

maintenant que le problème est résolu, je veux juste signaler pour Autodidacte33 qu'il y a aussi une façon non combinatoire de montrer cette relation qui consiste à développer avec le binôme de Newton :

0 = (1-1)n = ...

Posté par
Autodidacte33re : Dénombrement - combinatoire 19-12-20 à 00:22

@GBZM : Merci beaucoup !

@matheuxmatou : Merci pour le complément

En effet , pour tout n\in\N :

(1-1)^n=0\iff \displaystyle \sum_{k=0}^{n}\begin{pmatrix} n \\ k\end{pmatrix} (-1)^k   =0\iff   \sum_{\begin{matrix} _{k\in\N} \\ _{2k\leq n}\end{matrix}} ^{} \begin{pmatrix}n\\2k\end{pmatrix}-\sum_{\begin{matrix} _{k\in\N} \\ _{2k+1\leq n}\end{matrix}} ^{} \begin{pmatrix}n\\2k+1\end{pmatrix}=0\iff \sum_{\begin{matrix} _{k\in\N} \\ _{2k\leq n}\end{matrix}} ^{} \begin{pmatrix}n\\2k\end{pmatrix}=\sum_{\begin{matrix} _{k\in\N} \\ _{2k+1\leq n}\end{matrix}} ^{} \begin{pmatrix}n\\2k+1\end{pmatrix}

Cordialement


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 !