Nombre de surjections

[Aylward]

Bonjour à tous !

Voila j'ai un problème d'ensemble et j'ai DU mal à le résoudre :

Nous avons 2 ensembles E et F ayant chacun respectivement n et p elts. p>n

et il faut calculer le nombre d'applications surjectives de E sur F.

J'ai dit que :

Il y a plus elt a l'arrivé qu'au départ ( p>n ) : il a forcement 2 elts de E qui auront 2 imgs ce qui est impossible. Il n'y a donc aucune applications surjective dans le cas où p>n. Je pense que c'est bon.

Mais apres, on nous demande de calculer le nombre de surjections de E ( p+1 elts ) et F ( p elts ). On nous donne une aide : on peut utiliser l'elts "r" de F qui a 2 antécédants apres avoir justifier son existence.

Et je bloque à ce niveau.

Merci d'avance pour votre aide !!

[Aylward]

En fait j'ai trouvé la solution,

mais je suis bloqué à la question d'après :


Il faut démontrer que :

Quelque soit k € {0,...,p-1},

Sigma de [ q=k à p ] [ (-1)^q * ( q parmi p ) * (k parmi q ) ] = 0


merci d'avance

Aylward

[Aylward]

je pense qu'en séparant la somme en 2 on peut arriver à qqch mais j'ai du mal :


si on met d'un côté les q pairs le (-1)^q = 1

et de l'autre côté

les q impair : (-1)^q = -1 que l'on peut retirer sur sigma.
Je vois bien que les 2 membres vont finir par s'annuler mais neanmoins je n'arrive pas à bien comprendre comment fonctionne le sigma pour résoudre l'exo

Help !!

Aylward

[watashi wa]

salut tu devrais essayer encore en transformant les coeff du binome : ( q parmi p ) * (k parmi q ) = (k parmi p) * (k-q parmi k-p). De sorte que le facteur (k parmi p) peut etre factorise dans le sigma puis chgt d'indice puis formule du binome (1-1)=0 ... cela devrait le faire !

[Aylward]

merci bcp je vais essayer ça tout de suite !

[Aylward]

Merci bcp watashi wa j'ai reussi !!!


mais j'ai juste dit :


q parmi p ) * (k parmi q ) = (k parmi p) * (q-k parmi p-k)

et non

q parmi p ) * (k parmi q ) = (k parmi p) * (k-q parmi k-p)



MERCIIIIIIIIIIIIIIIIIIIIIII

[watashi wa]

bravo ! et la suite de l'exo ???

[Aylward]

Dans la suite de l'exo,

Soit Sn,p le nombre d'applications surjectives de En ( à n éléments ) dans Ep ( à p élements ).


Il faut établir que

p^n = sigma (de k=0 à p) (q parmi p) * Sn,p


Le nombre d'application de En dans Ep est card(Ep)^card(En) = p^n
d'où le résultat.

Il faut donc calculer toutes les applications de En dans Ep.

Je sais que Sn,p est le nombre de surjection de n,p.
Supposons que Sn,p a q élements. On a donc le choix entre (q parmi p ) surjections.

Mais je ne sais pas comment prouver qu'en les sommants, on a bien toutes les applications.


2/ E n déduire la formule :

Sn,p = (-1)^p * sigma (de k=0 à p) (-1)^k * ( k parmi p ) k^n



et là je n'ai vraiment pas d'idée ! je ne vois pas d'où viennent les élements



Merci watashi wa ! ( et les autres )

[watashi wa]

salut
dans le 1. il ya une erreur dans ce que tu écris : la formule a demontrer est fausse!! En effet :
p^n = sigma (de k=0 à p) (k parmi p) * Sn,k
tu as vu que p^n est le nb d'applc de En dans Ep. Ensuite tu recalcules le nb d'applic de En dans Ep en discutant suivant l'ensemble des images. Choisis une partie a k elements de Ep (il y a dc (k parmi p) possibltes) le nombre d'applications surjectives de En vers cette partie est Sn,k. En sommant pour k variant de 0 a p tu obtiens toutes les applications de En dans Ep.
Pour le 2. c'est un calcul de somme qui utilise les propriétés des coefficients du binôme. C'est dans ce calcul que tu dois te servir de ce que tu as prouvé hier : la première question de la discussion.

Bon courage !

[Aylward]

effetivement dans le 1/ c'est plutot :


p^n = sigma (de q=0 à p) (q parmi p) * Sn,p


merci bien je vais essayer cela !!

[Aylward]

merci bcp watashi wa tu m'a bcp aidé pour ce DM !!

j'ai bien compris les questions et réussi la 2 ( en utilisant la question du début de la discution )


puis-je encore te poser une derniere question ?

nous avons toujours :

En : l'ensemble des entier naturel strictement positifs et inférieur ou égaux à n.

Sn,p : le nombre d'application surjective de En dans Ep

An,p : le nombre de partition de En en p parties non vides


Il faut trouver la relation entre An,p et Sn,p

je ne vois pas vraiment comment je pourrais commencer. Et comme c'est la 1ère question au problème ....
mais apres bcp d'exemples, je pense que la relation pourrait être :

An,p =Sn,p/p!


En te remerciant encore de toute ton aide !!!!!

[watashi wa]

Voici le lien entre Sn,p et An,p : Considère une application surjective f de En vers {1,..,p}. Alors pour tout considère l'ensemble des antécédents de k par f : les (Fk) forment une partition de E_n. Ainsi, a chaque application surjective f correspondent p! partitions de E_n. Tu peux alors conclure en utilisant le théorème des Bergers que



A bientot !

[watashi wa]

Desole ! ce message annule le precedent!


Voici le lien entre Sn,p et An,p : Considère une application surjective f de En vers {1,..,p}. Alors pour tout considère l'ensemble des antécédents de k par f : les (Fk) forment une partition ORDONNEE de E_n. C'est-a-dire une liste (F1,..,Fp) de parties non vides de En telles que :



Il y a donc autant de partitions ordonnées que d'applications surjectives. Ainsi, a chaque partition non ordonnée correspondent p! applications surjectives de de E_n sur {1..p}. Tu peux alors conclure en utilisant le théorème des Bergers que



L'enonce - ou ton cours- doit preciser si l'on entend par partition une liste (l'ordre compte) ou simplement la donnée de p parties disjointes de reunion E_n (partition non ordonnée). D'après ce que tu dis, il semble qu'il faille considérer des partitions non ordonnées, auquel cas le resultat que tu donnes est juste !!


A bientot!

[Aylward]

je te remercie bcp de toute l'aide que tu m'a apporté !

et je te souhaite un très bon réveillon et une bonne année !!!


A bientôt !

[watashi wa]

pareillement !! Aylward ! Je te souhaite la sante et le succes dans tes etudes !!

Bonne année !