Je ne vois pas du tout comment trouver le nb de surjections d'un ensemble à
n+2 elts sur un ensemble à n elts ...
Merci
Posted by: Hervé Chappe
C'est du dénombrement :
Tu choisis 1 élément de l'ensemble d'arrivée parmi n, il a n+2 origines
possibles. Le deuxième en a n+1, donc on a déjà (n+2)(n+1), et on fait ça n
fois. Pour le dernier il reste, sauf erreur de ma part 3 termes, et
finalement le résultat devrait ressembler à (n+2).(n+1)...5.4.3, soit encore
((n+3)!)/2
"un taupin" <t@t.tt> a écrit dans le message de news:
XnF93EBD194E111Etaup@213.228.0.133...
> Je ne vois pas du tout comment trouver le nb de surjections d'un ensemble
à
> n+2 elts sur un ensemble à n elts ...
> Merci
Posted by: jplag
un taupin" a écrit :
> > Je ne vois pas du tout comment trouver le nb de surjections d'un
ensemble
> à
> > n+2 elts sur un ensemble à n elts ...
"Hervé Chappe" a écrit dans le message news:
> C'est du dénombrement :
> Tu choisis 1 élément de l'ensemble d'arrivée parmi n, il a n+2 origines
> possibles. Le deuxième en a n+1, donc on a déjà (n+2)(n+1), et on fait ça
n
> fois. Pour le dernier il reste, sauf erreur de ma part 3 termes, et
> finalement le résultat devrait ressembler à (n+2).(n+1)...5.4.3, soit
encore
> ((n+3)!)/2
Je ne suis pas convaincu par ce raisonnement ,on a bien défini un antécédent
pour chaque élément du but mais on n'a pas défini complétement la
surjection. Il reste deux éléments de la source qui n'ont pas d'image. Et il
y a n candidats pour chacune de ces deux images.
Je pense que la solution doit être beaucoup plus compliquée mais je ne la
connais pas.
Il se fait très tard alors peut-être qu'il ya quelque chose qui m'a échappé.
Posted by: Hervé Chappe
Objection rejetée, votre Honneur. Je persiste et je signe :
Une surjection n'exige pas que tout élément de l'ensemble de départ ait une
image dans l'ensemble d'arrivée,
elle exige seulement que tout élément de l'ensemble d'arrivée ait un
antécédent dans l'ensemble de départ.
Ou alors c'est à moi quequelque chose a échappé :-)))
"jplag" <jplag@wanadoo.fr> a écrit dans le message de news:
bj5uen$lc2$1@news-reader2.wanadoo.fr...
> un taupin" a écrit :
> > > Je ne vois pas du tout comment trouver le nb de surjections d'un
> ensemble
> > à
> > > n+2 elts sur un ensemble à n elts ...
>
> "Hervé Chappe" a écrit dans le message news:
> > C'est du dénombrement :
> > Tu choisis 1 élément de l'ensemble d'arrivée parmi n, il a n+2 origines
> > possibles. Le deuxième en a n+1, donc on a déjà (n+2)(n+1), et on fait
ça
> n
> > fois. Pour le dernier il reste, sauf erreur de ma part 3 termes, et
> > finalement le résultat devrait ressembler à (n+2).(n+1)...5.4.3, soit
> encore
> > ((n+3)!)/2
>
> Je ne suis pas convaincu par ce raisonnement ,on a bien défini un
antécédent
> pour chaque élément du but mais on n'a pas défini complétement la
> surjection. Il reste deux éléments de la source qui n'ont pas d'image. Et
il
> y a n candidats pour chacune de ces deux images.
> Je pense que la solution doit être beaucoup plus compliquée mais je ne la
> connais pas.
> Il se fait très tard alors peut-être qu'il ya quelque chose qui m'a
échappé.
>
>
>
Posted by: Herve Chappe
un taupin <t@t.tt> wrote in message news:<XnF93EBD194E111Etaup@213.228.0.133>...
> Je ne vois pas du tout comment trouver le nb de surjections d'un ensemble à
> n+2 elts sur un ensemble à n elts ...
> Merci
Bon, j'ai tiré un peu vite...
Pour tout élément de l'ensemble d'arrivée, il y a n+2 antécédents
possibles - ça peut être les mêmes, car il n'y a pas d'obligation
d'injectivité, comme je le pensais dans mon premier mail. Donc au
total n.(n+2) possibilités. Maintenant, il reste effectivement 2
éléments sans image. Pour chacun, il y a n+1 possibilités : pas
d'image, ou une parmi les n de l'ensemble d'arrivée. donc au total
n+1. Finalement le tout fait n.(n+2).2.(n+1)=2.n.(n+1).(n+2)
J'ai fait ça très vite, c'est peut-être encore un peu erratique, à
voir...
Posted by: Camille
In article <XnF93EBD194E111Etaup@213.228.0.133>, un taupin <t@t.tt>
wrote:
> Je ne vois pas du tout comment trouver le nb de surjections d'un ensemble à
> n+2 elts sur un ensemble à n elts ...
Suposons n >1.
On va construire la surjection en permutant les (n+2) éléments, en
envoyant les n premiers éléments sur les n éléments de l'ensemble
d'arrivée. Ensuite, il reste les deux derniers éléments : soit leurs
images sont distinctes (premier type), et il y a C(n,2) possibilités ;
soit elles sont confondues (deuxième type) et il y a n possibilités.
Avec cette méthode, on compte 4 fois chaque surjection du premier type
(car on peut inverser chacun des deux couples d'éléments qui ont la même
image), et 6 fois chaque surjection du second type (car on peut permuter
les trois éléments qui ont la même image). Finalement, le nombre de
surjections est :
(n+2)! (C(n,2)/4 + n/6)
Camille
Posted by: Camille
In article <3f56d3a5$0$20631$79c14f64@nan-newsreader-02.noos.net>,
"Hervé Chappe" <herve.chappe@noos.fr> wrote:
> Objection rejetée, votre Honneur. Je persiste et je signe :
>
> Une surjection n'exige pas que tout élément de l'ensemble de départ ait une
> image dans l'ensemble d'arrivée,
> elle exige seulement que tout élément de l'ensemble d'arrivée ait un
> antécédent dans l'ensemble de départ.
>
> Ou alors c'est à moi quequelque chose a échappé :-)))
Je pense que la définition de surjection que supposait l'énoncé était
"une fonction dont il convient de définir l'image pour chacun des points
de l'ensemble de départ".
Cependant, même dans le cas où l'on ne suppose pas que tout élément a
une image (ce qui n'est pas très usuel), personne ne supposera que
chaque élément de l'ensemble d'arrivée doit avoir exactement un
antécédent. Car dans ce cas, on aurait simplement demandé le nombre
d'injections dans l'autre sens. C'est ce que vous avez calculé...
Camille
Posted by: Herve Chappe
Finalement l'objection n'était pas completement fausse,il faut
probablement raisonner comme ça :
Un élément de F (arrivée) est l'image d'au moins un élément de E
(départ), et un élément de départ est l'origine d'un émément au plus
de l'ensemble d'arrivée. donc il existe une bijection entre f^-1(F) et
E, et cette bijection a n! éléments. Il reste donc 2 éléments
"inaffectés" de E, ceux de E/f^-1(F), qui ont ou n'ont pas d'image
dans F, soit (n+1) possibilités pour chacun. Finalement le résultat
serait n!(n+1)^2
C'est ma troisième et dernière tentative, on va voir ce que les
professionnels de la liste vont dire...
"Hervé Chappe" <herve.chappe@noos.fr> wrote in message news:<3f56d3a5$0$20631$79c14f64@nan-newsreader-02.noos.net>...
> Objection rejetée, votre Honneur. Je persiste et je signe :
>
> Une surjection n'exige pas que tout élément de l'ensemble de départ ait une
> image dans l'ensemble d'arrivée,
> elle exige seulement que tout élément de l'ensemble d'arrivée ait un
> antécédent dans l'ensemble de départ.
>
> Ou alors c'est à moi quequelque chose a échappé :-)))
>
> "jplag" <jplag@wanadoo.fr> a écrit dans le message de news:
> bj5uen$lc2$1@news-reader2.wanadoo.fr...
> > un taupin" a écrit :
> > > > Je ne vois pas du tout comment trouver le nb de surjections d'un
> ensemble
> à
> > > > n+2 elts sur un ensemble à n elts ...
> >
> > "Hervé Chappe" a écrit dans le message news:
> > > C'est du dénombrement :
> > > Tu choisis 1 élément de l'ensemble d'arrivée parmi n, il a n+2 origines
> > > possibles. Le deuxième en a n+1, donc on a déjà (n+2)(n+1), et on fait
> ça
> n
> > > fois. Pour le dernier il reste, sauf erreur de ma part 3 termes, et
> > > finalement le résultat devrait ressembler à (n+2).(n+1)...5.4.3, soit
> encore
> > > ((n+3)!)/2
> >
> > Je ne suis pas convaincu par ce raisonnement ,on a bien défini un
> antécédent
> > pour chaque élément du but mais on n'a pas défini complétement la
> > surjection. Il reste deux éléments de la source qui n'ont pas d'image. Et
> il
> > y a n candidats pour chacune de ces deux images.
> > Je pense que la solution doit être beaucoup plus compliquée mais je ne la
> > connais pas.
> > Il se fait très tard alors peut-être qu'il ya quelque chose qui m'a
> échappé.
> >
> >
> >
Posted by: jplag
"Hervé Chappe" a écrit :
> Objection rejetée, votre Honneur. Je persiste et je signe :
>
> Une surjection n'exige pas que tout élément de l'ensemble de départ ait
une
> image dans l'ensemble d'arrivée,
> elle exige seulement que tout élément de l'ensemble d'arrivée ait un
> antécédent dans l'ensemble de départ.
Pas d'accord!
D'après le Monnier, on parle d'application surjective.
Or pour une application f de E dans F, par définition
pour tout x app E, il existe y app F tq f(x)= y.
Posted by: Pierre Capdevila
J'ai la solution générale dans un bouquin,
c'est à dire le nombre de surjections de
[1, n] sur [1, p]. Si tu veux je te la scanne.
> J'ai la solution générale dans un bouquin,
> c'est à dire le nombre de surjections de
> [1, n] sur [1, p]. Si tu veux je te la scanne.
Ca serait en effet intéressant.
Si tu peux la mettre qqpart sur Internet et poster le lien, ca serait
super, et, je suppose, ca intéressera d'autres personnes.
Merci
Posted by: un taupin
Merci à vos tous pour vos contributions.
Posted by: Hervé Chappe
Alors x -> 1/x ce n'est pas une application simplement parce que ce n'est
pas défini en 0 ???
Il faut faire la distinction entre ensemble de départ et domaine de
définition, qui peut être un sous-ensembe strict de l'ensemble de départ.
"jplag" <jplag@wanadoo.fr> a écrit dans le message de news:
bj7b3i$dtp$1@news-reader3.wanadoo.fr...
>
> "Hervé Chappe" a écrit :
> > Objection rejetée, votre Honneur. Je persiste et je signe :
> >
> > Une surjection n'exige pas que tout élément de l'ensemble de départ ait
> une
> > image dans l'ensemble d'arrivée,
> > elle exige seulement que tout élément de l'ensemble d'arrivée ait un
> > antécédent dans l'ensemble de départ.
>
> Pas d'accord!
> D'après le Monnier, on parle d'application surjective.
> Or pour une application f de E dans F, par définition
> pour tout x app E, il existe y app F tq f(x)= y.
>
>
>
Posted by: jplag
"Hervé Chappe" <herve.chappe@noos.fr> a écrit dans le message news:
3f579a04$0$26487$79c14f64@nan-newsreader-02.noos.net...
> Alors x -> 1/x ce n'est pas une application simplement parce que ce n'est
> pas défini en 0 ???
> Il faut faire la distinction entre ensemble de départ et domaine de
> définition, qui peut être un sous-ensembe strict de l'ensemble de départ.
>
Non pour moi c'est une fonction.
Une application c'est la restriction de la fonction à son domaine de
définition.
Posted by: Pierre Capdevila
un taupin a écrit
> Ca serait en effet intéressant.
> Si tu peux la mettre qqpart sur Internet et
> poster le lien, ca serait super, et, je suppose,
> ca intéressera d'autres personnes.
La qualité est pas terrible. C'est l'espace offert par
wanadoo. Je comprend pas pourquoi ils affichent les
images sur une surface aussi petite... Avec un clic droit
de la souris sur l'image on peut l'enregistrer.
Hervé Chappe wrote:
> Alors x -> 1/x ce n'est pas une application simplement parce que ce
> n'est pas défini en 0 ???
> Il faut faire la distinction entre ensemble de départ et domaine de
> définition, qui peut être un sous-ensembe strict de l'ensemble de
> départ.
>
------
Toute fonction devient application sur son domaine de définition.
JMH
Posted by: un taupin
Camille a écrit :
> on compte 4 fois chaque surjection du premier type
> (car on peut inverser chacun des deux couples d'éléments qui ont la
> même image)
je ne vois pas pourquoi 4. J'aurais plutot dit 2 ...
> (n+2)! (C(n,2)/4 + n/6)
Posted by: Camille
In article <XnF93EEA2A9C177taup@213.228.0.4>, un taupin <t@t.tt> wrote:
> Camille a écrit :
>
> > on compte 4 fois chaque surjection du premier type
> > (car on peut inverser chacun des deux couples d'éléments qui ont la
> > même image)
>
> je ne vois pas pourquoi 4. J'aurais plutot dit 2 ...
Voici un exemple :
on considère l'application
x -> x (pour x = 1..n)
n+1 -> 1
n+2 -> 2
elle est obtenue en "choisissant" 1 et 2 comme points ayant deux
antécédents (d'où le C(n,2)). Ensuite, les quatre permutations suivantes
vont convenir :
1 2 3 4 ... n (n+1) (n+2)
(n+1) 2 3 4 ... n 1 (n+2)
1 (n+2) 3 4 ... n (n+1) 2
(n+1) (n+2) 3 4 ... n 1 2
d'où le facteur (n+2)!/4.
J'ai vérifier la formule pour n = 2 et 3, ça a l'air de marcher.