Nb de surjections

Forum d'archive d'entraide mathématique
Anonyme

nb de surjections

par Anonyme » 30 Avr 2005, 17:24

Je ne vois pas du tout comment trouver le nb de surjections d'un ensemble à
n+2 elts sur un ensemble à n elts ...
Merci



Anonyme

Re: nb de surjections

par Anonyme » 30 Avr 2005, 17:24

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" 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

Anonyme

Re: nb de surjections

par Anonyme » 30 Avr 2005, 17:24

un taupin" a écrit :[color=green]
> > Je ne vois pas du tout comment trouver le nb de surjections d'un
[/color]
ensemble
> à[color=green]
> > n+2 elts sur un ensemble à n elts ...
[/color]

"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é.

Anonyme

Re: nb de surjections

par Anonyme » 30 Avr 2005, 17:24

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" a écrit dans le message de news:
bj5uen$lc2$1@news-reader2.wanadoo.fr...
> un taupin" a écrit :[color=green][color=darkred]
> > > Je ne vois pas du tout comment trouver le nb de surjections d'un
[/color]
> ensemble
> > à[color=darkred]
> > > n+2 elts sur un ensemble à n elts ...
[/color]
>
> "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
[/color]
ça
> n[color=green]
> > 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[/color]
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é.
>
>
>

Anonyme

Re: nb de surjections

par Anonyme » 30 Avr 2005, 17:24

un taupin wrote in message news:...
> 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...

Anonyme

Re: nb de surjections

par Anonyme » 30 Avr 2005, 17:24

In article , un taupin
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

Anonyme

Re: nb de surjections

par Anonyme » 30 Avr 2005, 17:24

In article ,
"Hervé Chappe" 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

Anonyme

Re: nb de surjections

par Anonyme » 30 Avr 2005, 17:24

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" wrote in message news:...
> 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" a écrit dans le message de news:
> bj5uen$lc2$1@news-reader2.wanadoo.fr...[color=green]
> > un taupin" a écrit :[color=darkred]
> > > > Je ne vois pas du tout comment trouver le nb de surjections d'un
[/color]
> ensemble
> à[color=darkred]
> > > > 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
[/color]
> ça
> n[color=darkred]
> > > 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
[/color]
> encore[color=darkred]
> > > ((n+3)!)/2

> >
> > Je ne suis pas convaincu par ce raisonnement ,on a bien défini un[/color]
> 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é.
> >
> >
> >
[/color]

Anonyme

Re: nb de surjections

par Anonyme » 30 Avr 2005, 17:24

"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.

Anonyme

Re: nb de surjections

par Anonyme » 30 Avr 2005, 17:25

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.

--
Pierre
pierre-capdevila@wanadoo.fr

Anonyme

Re: nb de surjections

par Anonyme » 30 Avr 2005, 17:25

> 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

Anonyme

Re: nb de surjections

par Anonyme » 30 Avr 2005, 17:25

Merci à vos tous pour vos contributions.

Anonyme

Re: nb de surjections

par Anonyme » 30 Avr 2005, 17:25

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" a écrit dans le message de news:
bj7b3i$dtp$1@news-reader3.wanadoo.fr...
>
> "Hervé Chappe" a écrit :[color=green]
> > 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.
>
>
>[/color]

Anonyme

Re: nb de surjections

par Anonyme » 30 Avr 2005, 17:25

"Hervé Chappe" 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.

Anonyme

Re: nb de surjections

par Anonyme » 30 Avr 2005, 17:25

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.


Bien chef. Voilà :
http://monsite.wanadoo.fr/pierre_capdevila/

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.


--
Pierre
pierre-capdevila@wanadoo.fr

Anonyme

Re: nb de surjections

par Anonyme » 30 Avr 2005, 17:25

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

Anonyme

Re: nb de surjections

par Anonyme » 30 Avr 2005, 17:26

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)

Anonyme

Re: nb de surjections

par Anonyme » 30 Avr 2005, 17:26

In article , un taupin wrote:

> Camille a écrit :
>[color=green]
> > 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 ...[/color]

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.

Camille

Retourner vers ♲ Grenier mathématique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 4 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite