Nombre de surjections entre ensembles finis

[mehdi-128]

Bonjour,

J'essaie de faire un problème. Je n'ai pas le corrigé. J'aimerais juste quelques indications, j'aimerais trouver la solution seul.

Je mets les premières questions, mais il y en a d'autres que je mettrai au fur et à mesure que je recherche l'exercice.



On note le nombre de surjections de sur .

1/ Calculer si .



2/ Calculer , et .
on a une bijection en fait.
l'application constante égale à 1.
Il a application de dans
Il a que 2 applications non surjectives : les applications constantes égales à 1 ou 2.


3/ Calculer
Ici j'ai quelques difficultés.
Pour qu'on construise une bijection, il faut qu'un seul élément de l'image ait 2 antécédents et tous les autres un seul antécédent.
Mais je n'arrive pas à le traduire en langage mathématique.

[infernaleur]

Bonjour,
Pour les questions 1 et 2 c'est ok.


Pour la 3) comme tu l'as dit il faut que deux éléments de l'ensemble de départ ) aient la même image, combien a t'on de possibilité pour choisir ses deux éléments dans ?
Mais aussi combien a t'on de possibilité pour choisir l'élément de qui admet deux antécédents ?

Une fois que tu as dénombré cela il ne reste plus que éléments dans ton ensemble de départ et dans ton ensemble d'arrivé, combien reste t'il donc de possibilité pour construire ta surjection ?

[mehdi-128]

Nombre de possibilités de choisir 2 éléments dans


Nombre de possibilités de choisir l'élément de qui admet 2 antécédents :
p

A la fin fin il reste p-1 éléments dans les ensembles d'arrivée et et départ donc il y a : surjections.

J'ai donc :

Finalement :



C'est correct ?

[infernaleur]

Oui

[mehdi-128]

La suite...

On suppose désormais que

4/ Montrer que

D'après la formule du binôme de Newton :

5/ Montrer que

En développant les 2 coefficients binomiaux :



6/ En déduire que, si alors :
Et si ?

J'arrive pas cette question, j'ai pas d'idées.

[infernaleur]

La variable muette dans ta somme c’est q donc tout les truc qui dépendent pas de q tu peux les sortir de la somme.

[mehdi-128]

Si alors :

D'où :

Là j'arrive pas à me ramener à une somme qui ressemble à celle de la question 4 , j'ai essayé le changement d'indice sans succès

[hdci]

En changeant l'indice , la somme devient



On peut sortir et cela donne



Ré-écrivons cela en faisant apparaître qui vaut bien sûr 1



Et la somme est exactement le développement de

pour rappel :

[mehdi-128]

Merci beaucoup ! J'étais pas loin

Pour le cas : ça donne d'après la formule du binôme de Newton :



La somme est nulle sauf pour où elle vaut 1.
C'est correct ?

[mehdi-128]

7/ Déterminer, le nombre d'applications de dans ayant un ensemble image à q éléments.

Toute application de dans est une surjection de dans . Il suffit alors de dénombrer les surjections.
Notons :

Possibilités de choisir un ensemble à q éléments dans :


Possibilités de construire une surjection à partir de cet ensemble à q éléments choisi:


Le nombre d'applications recherché est donc :

8/ En déduire que

D'après le cours, le nombre d'applications de dans est :


Ensuite, quand on choisit nos q éléments dans pour construire notre surjection, on peut en choisir 1 élément, 2 éléments, jusqu'à p éléments d'où :



9/ En utilisant ce qui précède, montrer que :

Je suis bloqué à cette question.

[hdci]

Merci beaucoup ! J'étais pas loin

Pour le cas : ça donne d'après la formule du binôme de Newton :



La somme est nulle sauf pour où elle vaut 1.
C'est correct ?

Il manque juste le facteur , cf.

donc ici ce sera si

[mehdi-128]

Vous avez une idée pour la question 9 ?

[infernaleur]

Il faut seulement utiliser les questions précédentes.
Tu as une expression pour k^n tu remplaces donc k^n dans la somme et tu utilises la 6)

[mehdi-128]

On cherche à simplifier :

Or :

On en déduit :



Or :

D'où :

Mais :

Soit

Et là je suis bloqué

[mehdi-128]

Pas d'idées ?