Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 05-01-2008 15:11:48

cléopatre
Membre active
Inscription : 24-10-2006
Messages : 359

Problème surjections - combinaisons [Résolu]

Bonjour à tous les bibmatheux et bonne année !

Voilà, je suis en train de faire un problème. J'ai fait déjà quelques questions mas je bloque à la question 6).

Je vous donn l'énoncé en bref et ce que j'ai déjà démontré :

Pour tout n de N* on note En={1,2,3,...,n}.
On note S(n,p) le ombre de surjections de En sur Ep.

Mes calculs préliminaires : corrigez moi si je fais fausse route bien entendu...
1) Pour p>n, S(n,p)=0
2) S(n,n)=n!
    S(n,1)=n
    S(n,2)=n(n-1)
3)S(p+1,p)=S(p+1,p+1)=(p+1)!
4) J'ai démontré que [tex]\sum_0^p(-1)^k \begin{pmatrix} p \\ k\end{pmatrix}=0[/tex]
5)J'ai démontré que [tex]\begin{pmatrix} p \\ q\end{pmatrix}\begin{pmatrix} q \\ k\end{pmatrix}=\begin{pmatrix} p \\ k\end{pmatrix}\begin{pmatrix} p-k \\ q-k\end{pmatrix}[/tex]
6) j'ai démontré que : [tex]\sum_k^p(-1)^q \begin{pmatrix} p \\ q\end{pmatrix}\begin{pmatrix} q \\ k\end{pmatrix}=0[/tex]
Je précise que dans la somme c'est q qui varie...
7)Je ne parviens pas à montrer que pour tout entier q € {1,...,p} le nombre d'applications de En dans Ep ayant un ensemble image à q éléments est égal à [tex]\begin{pmatrix} p \\ q\end{pmatrix}S(n,p)[/tex]
Je pense que c'est plus un problme de compréhension...

Merci d'avance pour votre aide...
Bises de Cléo

Dernière modification par cléopatre (05-01-2008 15:24:52)


<-- cleopatre -- 19 ans -- débutante mais amoureuse des maths -->
Hommage à Yoshi : "la Roche Tarpéienne est près du Capitole" wink

Hors ligne

#2 05-01-2008 20:10:42

john
Membre actif
Inscription : 10-02-2007
Messages : 543

Re : Problème surjections - combinaisons [Résolu]

Salut Cléo,
Meilleurs voeux de réussite.
Tu devrais nous faire part de tes raisonnements...
Exemple pour S(n,1)
Si tout élément de En est lié ou non à l'élément de E1, on a 2^n graphes possibles.
Parmi ceux-ci, le seul qui ne soit pas une surjection est celui où aucun élément de En n'est lié à l'élément de E1.
d'où : S(n,1) = 2^n - 1
A+

Dernière modification par john (05-01-2008 20:13:11)

Hors ligne

#3 05-01-2008 21:38:55

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : Problème surjections - combinaisons [Résolu]

Salut,

  Je ne comprends pas bien ce que John a voulu dire,
je suis plutôt d'accord avec toi pour S(n,1) (toute application de En dans E1 est surjective).

Pour la question 7), es-tu sure que ce n'est pas S(n,q) plutôt que S(n,p).
En effet, pour obtenir une application dont l'image à q éléments :
*tu choisis d'abord q éléments parmi p.
*ces q éléments fixés, tu as ensuite le choix de n'importe quelle surjection de En sur un ensemble à q éléments, soit S(n,q).

Fred.

Hors ligne

#4 05-01-2008 22:47:09

john
Membre actif
Inscription : 10-02-2007
Messages : 543

Re : Problème surjections - combinaisons [Résolu]

Salut Fred et bonne année à tous,
Il est très possible que ce soit ma première de l'année 2008, mais j'ai pris ma définition d'une surjection sur le wiki :
http://fr.wikipedia.org/wiki/Surjection
Alors où est l'erreur ?
A+

Hors ligne

#5 05-01-2008 23:51:05

cléopatre
Membre active
Inscription : 24-10-2006
Messages : 359

Re : Problème surjections - combinaisons [Résolu]

Salut à vous ls bibmath !

Pour John, Fred va te répondre très vite je le pense..
Fred, tu as tout bon il est vrai que j'ai fait l'erreur et en plus j'ai bien compris le raisonnement...merci
Merci à vous deux et je ne ferme pas cette conversation car demain je vous demanderais de l'aide pour la suite...

Bises de Cléo

Dernière modification par cléopatre (05-01-2008 23:51:18)


<-- cleopatre -- 19 ans -- débutante mais amoureuse des maths -->
Hommage à Yoshi : "la Roche Tarpéienne est près du Capitole" wink

Hors ligne

#6 06-01-2008 11:30:05

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : Problème surjections - combinaisons [Résolu]

Salut John, et bonne année à toi.

On s'est sans doute trompé tous les deux!
Il n'y a qu'une seule application d'un ensemble à n éléments dans un ensemble à un élément
(on n'a pas le choix, on doit envoyer tous les éléments sur le seul élément possible).
On a donc S(n,1)=1 et non n ou 2^n-1
(rappel : quand on parle d'application ici, tout élément a une image).
Pour S(n,2), on a 2^n applications. Il faut retirer toutes les applications qui ont pour image
un seul élément, c'est-à-dire les 2 applications constantes.
Donc S(n,2)=2^n-2 (sauf nouvelle erreur de ma part bien sûr!).

Message en passant : dis-moi Cleopatre, depuis le temps que tu as 17 ans, t'es sure de ne pas
en avoir 18 maintenant?

Fred.

Hors ligne

#7 06-01-2008 16:41:43

john
Membre actif
Inscription : 10-02-2007
Messages : 543

Re : Problème surjections - combinaisons [Résolu]

Ok merci Fred. On s'est trompé tous les TROIS ! L'important étant de converger...

Je note donc que le schéma d'une surjection donné par le wiki
http://fr.wikipedia.org/wiki/Surjection
est faux et qu'il faut s'en tenir à celui de notre Dico :
http://www.bibmath.net/dico/index.php3? … ction.html
ce qui donne effectivement une seule surjection qui est l'application constante.
Ceci pose donc un pb. plus général : A qui faire confiance sur www ?
A+

Hors ligne

#8 06-01-2008 17:28:04

cléopatre
Membre active
Inscription : 24-10-2006
Messages : 359

Re : Problème surjections - combinaisons [Résolu]

Bonsoir !

Effectivement je dois avouer avoir fais la bétise... Et oui, j'ai bien 18 ans je vais changer cela tout de suite. J'y est pensé déjà l'autre jour mais bon surement un manque d'envie de modifier.

Je me trompé sur le raisonnement. Je pensais que c'était le 1 qui allait vers les n et donc qui avait n possibilités. En réalité c'est le contraire. Donc effectivement pour Sn,1, il y a qu'une possibilité et pour Sn,2 il y a 2^n possibilité ("2 possibilités pour chaque nombre").

Sinon le raisonnement de la suite est bon. Je continue donc par mon bon élan pour vous poser une autre question:
Je dois démontrer [tex]p^n=\sum_{q=1}^p\begin{pmatrix} p \\ q \end{pmatrix}\times Sn,q[/tex]

Déjà, p^n dois être vu comme p à la puissance n ou comme l'ensemble des applications de n dans p?

Merci à vous
Bises de Cléo


<-- cleopatre -- 19 ans -- débutante mais amoureuse des maths -->
Hommage à Yoshi : "la Roche Tarpéienne est près du Capitole" wink

Hors ligne

#9 06-01-2008 18:54:08

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : Problème surjections - combinaisons [Résolu]

Bonsoir,

  Je dirais que le schéma de Wiki est faux pour une définition moderne de fonction,
celle que l'on utilise maintenant à tous les étages. Bien sûr qu'il faut faire confiance
au dico (même si les schémas de la page que citent John sont horribles! Qui s'y colle pour
m'en faire de jolis (ou me disent avec quel logiciel je peux faire comme sur wiki?).

  Pour la question de Cléopatre, il faut voir p^n comme le nombre d'applications
d'un ensemble à n éléments dans un ensemble à q éléments.
Le q de la somme désigne le nombre d'éléments dans l'image de l'application
(qui peut être compris entre 1 et p). Le terme à l'intérieur de la somme
désigne le nombre d'applications dont l'image a exactement q éléments
(je te laisse nous expliquer pourquoi).

Fred.

Hors ligne

#10 06-01-2008 18:59:52

cléopatre
Membre active
Inscription : 24-10-2006
Messages : 359

Re : Problème surjections - combinaisons [Résolu]

Bonsoir Fred !

Oui, j'ai compris. Il suffit jsute de sommer comme on l'a vu dans la question précédente le nombre d'applications dont l'image a exactemnet q éléments et on obtient le nombre d'applications d'un ensemble à n éléments dans un ensemble à q éléments.

Est ce juste ?

Bises de Cléo


<-- cleopatre -- 19 ans -- débutante mais amoureuse des maths -->
Hommage à Yoshi : "la Roche Tarpéienne est près du Capitole" wink

Hors ligne

#11 06-01-2008 20:39:18

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : Problème surjections - combinaisons [Résolu]

C'est juste.

F.

Hors ligne

#12 08-01-2008 16:14:25

Barbichu
Membre actif
Inscription : 15-12-2007
Messages : 405

Re : Problème surjections - combinaisons [Résolu]

Hello,
pour ce qui est de la définition de fonction, il me semble que (en tout cas d'après Algèbre 1 de J.M. Monier, éditions Dunod et je jetterais un oeil au Bourbaki dès qu'il me tombera sous la main,) tout point du domaine ne départ ne possède pas forcement une image. Les applications sont les fonctions qui vérifient cette propriété. Ce qui fait que wikipédia a raison.
Cependant, étant donné qu'on utilise en réalité qu'extremement rarement les fonctions, il est passé dans les moeurs de commettre l'abus de langage "fonction = application". Ainsi, quand l'énoncé de Cléopâtre parle de surjection, il s'agit en fait d'une application surjective.

Quant au logiciel à utiliser : en wysiwyg et opensource, il ya xfig qui est tout simplement excellent.
(sinon en pas wysiwyg, il y a le package tikz pour latex)
++


Barbichu

Hors ligne

#13 08-01-2008 20:51:46

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : Problème surjections - combinaisons [Résolu]

Salut,

  Sur cette page
du dictionnaire, j'explique (je crois clairement) la distinction qu'il y a entre application et fonction
au sens "bourbakiste".
Maintenant je ne connais aucun mathématicien raisonnable (et pourtant, j'en connais beaucoup!) qui fasse la distinction entre fonction et application.

Pour les puristes, j'ai vérifié que dans le DicoMath, je définissais une surjection comme une application particulière,
et Wikipedia définit une surjection comme une fonction particulière.
Il n'empêche que ici, qd on cherche des fonctions de En dans Ep, on entend bien que tous les éléments de En ont une image.

Bon, je vais essayer tikz car je n'ai jamais aimé xfig (à moins que les versions récentes soient mieux...).

Fred.

Hors ligne

#14 09-01-2008 00:59:55

Barbichu
Membre actif
Inscription : 15-12-2007
Messages : 405

Re : Problème surjections - combinaisons [Résolu]

Salut,
nous sommes donc parfaitement d'accord sur tout, sauf sur le fait que xfig c'est bien :-)
++


Barbichu

Hors ligne

#15 13-01-2008 00:06:43

john
Membre actif
Inscription : 10-02-2007
Messages : 543

Re : Problème surjections - combinaisons [Résolu]

Bonsoir,
... encore faut-il le prouver ! Et le piètre dessinateur que je suis va tenter cet exploit sous vos yeux (pour le fun évidemment) :

applxfigrr1.png

injxfigst3.png

surjxfigqe3.png

bijxfixes6.png


Fred, à toi de juger sur pièce.
Bye

Modif. : Séparation des fig. pour la lisibilité.

Dernière modification par john (13-01-2008 10:53:33)

Hors ligne

#16 13-01-2008 21:31:47

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : Problème surjections - combinaisons [Résolu]

Excellent John!
Et donc c'est fait avec Xfig???
Il y a un outil facile pour faire des flèches????
C'est parfait, à l' "aliasing" des droites près!

Fred.

Hors ligne

#17 13-01-2008 23:44:13

john
Membre actif
Inscription : 10-02-2007
Messages : 543

Re : Problème surjections - combinaisons [Résolu]

Bonsoir Fred,
Effectivement c'est Xfig.
L'aliasing est probablement dû à mon paramétrage de Xfig (je n'ai pas choisi la haute résolution).
Tu vois exactement ce que je vois dans ma fenêtre Xfig. La conversion en format PNG pour exporter l'image n'a absolument rien changé à l'aspect.

Pour les flèches, rien de plus simple : outil "Polyline" + choix de paramètres (couleur épaisseur...) + mode "Arrow" + choix de paramètres des flèches.
A+

Hors ligne

#18 18-01-2008 21:37:57

cléopatre
Membre active
Inscription : 24-10-2006
Messages : 359

Re : Problème surjections - combinaisons [Résolu]

Bonsoir !

J'ai loupé cette semaine un grand débat pertinent. On en est même arrivé à faire des dessins... Alala !! Ces bibmatheux... Je peux clore ce sujet car j'ai tout compris... En plus, après je suis arrivé à faire pas mal de choses assez interressante avec les fractions continues. Je ferais un article dessus si tu le souhaite pendant les vacances de février Fred.

En tout les cas merci à vous et....parlons de polynômes irréductible dans un nouveau message

Bises de Cléo


<-- cleopatre -- 19 ans -- débutante mais amoureuse des maths -->
Hommage à Yoshi : "la Roche Tarpéienne est près du Capitole" wink

Hors ligne

Pied de page des forums