Nombre de surjections

[jujudu597]

Bonjour,

je cherche à calculer le nombre de surjections de A à B ou card(A) = 10 et card (B)= 4

J'ai plusieurs idées mais je ne sais pas si elle sont bonne.

Je pensais que ce nombre étais

Mais je ne crois pas que ce soit ca car j'ai vu plusieurs fois des réponses avec une somme donc voila
jspr que vous pourrez m'éclairer!

Merci bcp d'avance

[Ben314]

Salut,
Déjà, sans même trop regarder, ça m'étonnerais pas mal que le résultat soit celui là (tu l'obtient par quel raisonnement ?)
Le calcul du nombre de surjection d'un ensemble de cardinal a dans un ensemble de cardinal b est un peu compliqué a obtenir donc ce que tu cherche c'est quoi :
- Un petit bricolage dans un cas particulier simple comme ici où b est très petit ?
- Un lien vers une preuve complète donnant une formule pour trouver le nombre de surjections ?
- Des indics. pour trouver toi même la formule en question ?

[jujudu597]

Alors pour trouver cette fausse formule xD
Jai dis que 4 élements obligatoirement devais avoir pour chacune des images différentes (c'est pas très francais Oo)
et que le reste avais pour image nimporte quelle élements de l'ensemble d'arrivé

[Ben314]

Oui, mais ça déconne de tout les cotés :
(Dans toute la suite, je considère que A={1,2,3,...,10} et B={1,2,3,4} ce qui ne coute pas un copec)

- Déjà (mais c'est un détail), ça serait plutôt le nombre d'arrangement de 4 pari 10 le premier coeff. vu qu'il ne suffit pas de choisir 4 éléments parmi les 10, il faut aussi choisir lequel des 4 s'envoie sur 1, lequel sur 2, etc...

- Ensuite, en procédant de la sorte, tu compte des tas de fois la même fonction. Par exemple, supposons que les 4 éléments "spéciaux" choisis soient 1,2,3,4 que tu envoie respectivement sur 1,2,3,4. Parmi les 4^6 possibilités que tu dénombre pour ce cas là, il y a en particulier celle où tu prend tout les autres f(x)=1.
Sauf que, dans le cas que tu as considéré comme différent où les 4 élément "spéciaux" choisis sont 2,3,4,5 que tu envoie respectivement sur 2,3,4,1, parmi les 4^6 possibilités pour les autres qui sont pris pris au pif, il y a le cas particulier où tu prend de nouveau tout les f(x)=1 (pour les x autres que 2,3,4,5) et cette fonction là, c'est la même que dans le cas précédent...

A mon avis, (a peu prés) la seule façon de procéder, c'est de calculer les un après les autres :
1) Le nombre D1 de surjection d'un ensemble à 10 éléments dans un ensemble à 1 élément (jusque là, ça va...)
2) Le nombre D2 de surjection d'un ensemble à 10 éléments dans un ensemble à 2 éléments en utilisant le fait qu'on sait combien il y a d'applications pas forcément surjectives et que celle qui ne sont pas surjective, c'est qu'elles n'atteignent qu'un élément sur les 2.
3) Le nombre D3 de surjection d'un ensemble à 10 éléments dans un ensemble à 3 éléments (idem)
4) Le nombre D4 de surjection d'un ensemble à 10 éléments dans un ensemble à 4 éléments (idem)

Et si tu veut être sûr de ne pas écrire de conneries, cherche les nombres D1(n), D2(n), D3(n) et D4(n) en considérant qu'il y a n éléments au départ (et pas forcément 10) et vérifie que ce que tu trouve est cohérent avec les "petites" valeurs de n (1,2,3,4) où on peut les "comptes sur les doigts".
Par exemple, au final, pour D4(n), tu devrait trouver un truc qui vaut évidement 0 pour n=1,2,3 et qui vaut 4!=24 pour n=4.

[beagle]

"- Un petit bricolage dans un cas particulier simple comme ici où b est très petit ?"

j'ai pas commencé pour voir si faisable,
mais en fixant ce qui arrive sur le premier élément d'arrivée:
-7
-6
-5
-4
-3
-2
-1

donc on calcule les
7-1-1-1
6-2-1-1
5-3-1-1 et 5-2-2-1
4-4-1-1 et 4-3-2-1 et 4-2-2-2
...
pour les 3,2,et 1 je sais pas si on peut repiquer ceux du dessus.

Euh, oui c'est long,
mais j'avais fait un truc pareil pour les n poissons dans k bocaux ...
en y allant pépère si t'es retraité ...

[beagle]

en fait en dormant je me suis souvenu que j'avais plutot fait:
on fixe le max, et pas on fixe un élément puis le max.

On fixe le 7
et le 7-1-1-1
ben il y en a 4
le 6-2-1-1
il y en aura 4 (le6)x3(le2)

et on va ainsi jusqu'au
3-3-3-1

pas besoin de se taper les 2 e les 1.

C'est moins bien que la proposition de Ben314.
Mais du lourdingue faisable car il y a peu d'éléments, c'est faisable.

[chan79]

Salut
Une tentative
A={1,2,3,4,5,6,7,8,9,10}
B={1,2,3,4}
Il y a applications de A dans B.
Il faut enlever celles qui n'atteignent pas 1; il y en a
Il faut enlever celles qui n'atteignent pas 2; il y en a
Il faut enlever celles qui n'atteignent pas 3; il y en a
Il faut enlever celles qui n'atteignent pas 4; il y en a
(merci le copier-coller ...)
Il faut donc en enlever
MAIS, on en a trop enlevé. Celles, par exemple, qui n'atteignent ni 1, ni 2 ont été enlevées deux fois.
Il faut rajouter
Quid des applications qui n'ont atteint par exemple ni 1, ni 2, ni 3 ?
Elles ont été enlevées 3 fois et remises 3 fois. Il faut donc les enlever et il y en a 4.
Finalement, on trouve

Pour en revenir au post initial, on peut généraliser avec une formule qu'on trouve facilement ici ou là et qui donne le nombre de surjections d'un ensemble à n éléments dans un ensemble à p éléments (p<=n)


Evidemment, dès que p est grand on ne peut pas utiliser cette formule.
Il vaut mieux procéder par récurrence.

[Ben314]

C'est exactement ça... :king2:
Si on fixe n>=1 (cardinal de l'ensemble de départ) et qu'on note d(p) le nombre de surjection de {1..n} dans {1..p} alors :

Pour tout p>=1, toute application f de {1..n} dans {1..p} (il y en a ) est entièrement (et univoquement décrite) décrite par
- Le nombre k d'éléments de f({1..n}) entre 1 et p.
- La partie Y=f({1..n}) à k élément de {1..p} -> il y en a .
- La surjection de {1..n} dans Y -> il y en a .
Donc si on pose
On peut alors, de proche en proche, en déduire la valeur des :
(hautement trivial...)




Si on veut démontrer la formule générale donnée par chan79, on peut évidement conjecturer le résultat et le démontrer par récurrence (chiant, mais faisable) ou bien comprendre que les équations forment un système linéaire d'inconnues dont la matrice associée est celle contenant les coeff. binomiaux qu'il faut donc inverser.
Il y a des tas de moyens plus ou moins jolis et rapide de le faire, dont un particulièrement direct consistant à écrire la matrice (dans la base canonique) de l'application linéaire ainsi que la matrice de la bijection réciproque .