Nombre de surjections entre ensembles finis

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
mehdi-128
Membre Complexe
Messages: 2838
Enregistré le: 10 Déc 2006, 15:57

Nombre de surjections entre ensembles finis

par mehdi-128 » 11 Juil 2018, 20:46

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
Membre Irrationnel
Messages: 1071
Enregistré le: 20 Avr 2017, 19:45

Re: Nombre de surjections entre ensembles finis

par infernaleur » 11 Juil 2018, 21:05

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
Membre Complexe
Messages: 2838
Enregistré le: 10 Déc 2006, 15:57

Re: Nombre de surjections entre ensembles finis

par mehdi-128 » 11 Juil 2018, 22:05

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
Membre Irrationnel
Messages: 1071
Enregistré le: 20 Avr 2017, 19:45

Re: Nombre de surjections entre ensembles finis

par infernaleur » 11 Juil 2018, 22:54

Oui

mehdi-128
Membre Complexe
Messages: 2838
Enregistré le: 10 Déc 2006, 15:57

Re: Nombre de surjections entre ensembles finis

par mehdi-128 » 11 Juil 2018, 23:59

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
Membre Irrationnel
Messages: 1071
Enregistré le: 20 Avr 2017, 19:45

Re: Nombre de surjections entre ensembles finis

par infernaleur » 12 Juil 2018, 02:40

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
Membre Complexe
Messages: 2838
Enregistré le: 10 Déc 2006, 15:57

Re: Nombre de surjections entre ensembles finis

par mehdi-128 » 12 Juil 2018, 13:28

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 :oops:
Modifié en dernier par mehdi-128 le 12 Juil 2018, 13:48, modifié 1 fois.

hdci
Membre Irrationnel
Messages: 1962
Enregistré le: 23 Juin 2018, 18:13

Re: Nombre de surjections entre ensembles finis

par hdci » 12 Juil 2018, 13:37

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 :

Il n'y a que 10 types de personne au monde : ceux qui comprennent le binaire et ceux qui ne le comprennent pas.

mehdi-128
Membre Complexe
Messages: 2838
Enregistré le: 10 Déc 2006, 15:57

Re: Nombre de surjections entre ensembles finis

par mehdi-128 » 12 Juil 2018, 13:52

Merci beaucoup ! J'étais pas loin :D

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
Membre Complexe
Messages: 2838
Enregistré le: 10 Déc 2006, 15:57

Re: Nombre de surjections entre ensembles finis

par mehdi-128 » 12 Juil 2018, 14:41

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
Membre Irrationnel
Messages: 1962
Enregistré le: 23 Juin 2018, 18:13

Re: Nombre de surjections entre ensembles finis

par hdci » 12 Juil 2018, 14:46

mehdi-128 a écrit:Merci beaucoup ! J'étais pas loin :D

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.
hdci a écrit:


donc ici ce sera si
Il n'y a que 10 types de personne au monde : ceux qui comprennent le binaire et ceux qui ne le comprennent pas.

mehdi-128
Membre Complexe
Messages: 2838
Enregistré le: 10 Déc 2006, 15:57

Re: Nombre de surjections entre ensembles finis

par mehdi-128 » 12 Juil 2018, 18:16

Vous avez une idée pour la question 9 ?

infernaleur
Membre Irrationnel
Messages: 1071
Enregistré le: 20 Avr 2017, 19:45

Re: Nombre de surjections entre ensembles finis

par infernaleur » 12 Juil 2018, 23:20

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
Membre Complexe
Messages: 2838
Enregistré le: 10 Déc 2006, 15:57

Re: Nombre de surjections entre ensembles finis

par mehdi-128 » 13 Juil 2018, 03:32

On cherche à simplifier :

Or :

On en déduit :



Or :

D'où :

Mais :

Soit

Et là je suis bloqué :?

mehdi-128
Membre Complexe
Messages: 2838
Enregistré le: 10 Déc 2006, 15:57

Re: Nombre de surjections entre ensembles finis

par mehdi-128 » 13 Juil 2018, 19:46

Pas d'idées ?

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 42 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