Hello,
J'ai vu en cours une formule récurrente pour le calcul du nombre de surjections d'un ensemble E dans un ensemble F.
Je viens de tomber sur le net sur un autre formule, non récurrente, que j'aimerais bien comprendre :
Soit e le cardinal de E, et f le cardinal de F
Si vous avez une démonstration, un début de démonstration ou même rien qu'une piste, ça m'intéresse !
Merci !
Salut g_h,Envoyé par g_h
Soit e le cardinal de E, et f le cardinal de F
j'ai vu cette formule et sa démo en cours - et j'ai du la démontrer en khôlle (mais avant de l'avoir vue.......)
la démo fait trois pages chez moi ...
d'abord il faut connaitre une formule d'inversion qui est indispensable, et sa démo est plutôt longue...
cette formule te dit :
b_n= la somme de k=0 à n, de (k parmi n) des a_k
<=>
a_n = la somme de k=0 à n de (-1)^(n-k) x (k parmi n) x b_k
je te fais pas la démo, c'est horrible : mon khôlleur ne la connaissait même pas ...
Tu considères A,
A = les applications de E vers F
A_k = {f € A / card(f(E) = k}
A= union disjointe de k=1 à n des A_k
Clairement (ruse triviale dirait mon prof),
card(A_k)=la somme de k=0 à n de (k parmie q) x S_p,k
avec S_p,k, les surjections de E_p vers E_k
(ah oui, p est le card de E, et q est le card de F)
donc quelque soit n € IN, b_n=la somme de k=0 à n de (k parmi n) x a_k,
tu utilises la formule d'inversion et c'est fini...
il faut faire un dessin pour comprendre clairement.
précision : k, c'est le cardinal d'un ensemble de F qui ne reçoit pas de surjection de E. F ne reçoit pas tout entier les surjections de E, il n'y en a qu'une partie (de cardinal q).
j'espère avoir été clair
si tu as un problème...
Romain
Merci pour ta réponse !
Seulement je ne comprends pas... c'est quoi E_p et E_k ?
en fait, j'ai mélangé les notations
E_p, c'est l'ensemble E de card p, et idem pour E_k (resp card k).
Voilà voilà !
PS : ça fait plaisir de pouvoir aider quelqu'un,
Romain
Il y a plusieurs ensembles E ou quelque chose m'a échappé ?en fait, j'ai mélangé les notations
E_p, c'est l'ensemble E de card p, et idem pour E_k (resp card k).
Voilà voilà !
PS : ça fait plaisir de pouvoir aider quelqu'un,
Romain
E est de cardinal p, il n'est pas de cardinal k... ? (oui il y a sûrement quelque chose qui m'échappe)
(et ça fait plaisir de se faire aider aussi !)
EDIT : tentative : E_k est peut-être l'ensemble des parties de E à k éléments ?
Non non non,
toi tu as appelé tes deux ensembles E et F
moi je les appelle tous les deux E, mais en indice je mets leur cardinal pour les différencier : je sais c'est pas très clair, surtout que j'ai pas respecté tes notations.
j'espère que tu vas t'en sortir...
je te démontre pas la formule d'inversion : j'en ai pas le courage
mais il parait que c'est une formule extraordinaire.
HS : je sais pas vous, mais nous - en khôlle - on nous demande de démontrer les formules comme si on ne les savait pas. c'est à dire que tu n'as pas droit à la récurrence et tu n'as pas le droit de partir de la formule à démontrer. Il faut partir de quelque chose de basique et remonter jusqu'à la formule (vive les khôlles !)
Arf ok, donc mon F c'est ton E_kNon non non,
toi tu as appelé tes deux ensembles E et F
moi je les appelle tous les deux E, mais en indice je mets leur cardinal pour les différencier : je sais c'est pas très clair, surtout que j'ai pas respecté tes notations.
j'espère que tu vas t'en sortir...
je te démontre pas la formule d'inversion : j'en ai pas le courage
mais il parait que c'est une formule extraordinaire.
HS : je sais pas vous, mais nous - en khôlle - on nous demande de démontrer les formules comme si on ne les savait pas. c'est à dire que tu n'as pas droit à la récurrence et tu n'as pas le droit de partir de la formule à démontrer. Il faut partir de quelque chose de basique et remonter jusqu'à la formule (vive les khôlles !)
Mais tu écris que F est de cardinal ... q et non pas k !
Tu voudrais bien me la refaire avec tes notations ? Je pense que ça serait mieux
Sinon j'ai pas encore éprouvé le besoin de faire une récurrence en colle, mais en tous cas ça ne doit pas être interdit (faudra que j'essaye
D'ailleurs si tu as une démo de la formule de Taylor (avec reste intégral) qui ne passe pas par la récurrence, ça m'intéresse ! (mais je doute que ça existe, enfin qui sait !)
PS : est-ce que la formule d'inversion en question à un nom particulier ? Je ne la trouve nulle part !
Je me permets de faire remonter ce fil... c'est mon programme de colle de la semaine prochaine et je n'aurai plus le net !
Donc si quelqu'un pouvait me filer un coup de pouce (Romain29 si tu passes par là ...
Et si quelqu'un a un lien concernant la "formule d'inversion" qui est utilisée ici, ça m'intéresse plus que fortement aussi !
Merci encore
Argh ! excuse moi !
...
la formule d'inversion (que je te démontre pas : mais pas de soucis à ce niveau là : je ne crois pas que ce soit au programme : en tous cas, nous, ça ne l'était pas)
b_n= la somme de k=0 à n, de (k parmi n) des a_k
<=>
a_n = la somme de k=0 à n de (-1)^(n-k) x (k parmi n) x b_k
on cherche le nombre de surj de E vers F avec e le card de E et f le card de F.
Tu considères A,
A = les applications de E vers F
A_k = {f € A / card(f(E) = k}
A= union disjointe de k=1 à n des A_k
Clairement : avec un dessin
card(A_k) = la somme de k=0 à n de (k parmie f) x S_e,f
quelque soit n appartient à IN,
b_n=la somme de k=0 à n de (k parmi n) x a_k,
tu utilises la formule d'inversion et c'est fini...
J'ai repris exactement ce que j'avais écrit hier en changeant les notations.
Pour être vraiment clair, il faut le faire sur un dessin.
Je ne vois pas comment je pourrais t'aider...
bon courage
PS : pour nous, les khôlleurs n'ont pas été méchants à ce sujet.
Ok, merci beaucoup pour ton aide !!
J'espère pouvoir m'en tirer
Mon prof a donné l'année dernière un DM dont une partie traitait le nombre de surjection d'un ensemble E dans un ensemble F. Il est disponible sur internet, je vais essayer de retrouver l'adresse.
Plutôt la somme de k=0 à f de (k parmie f) x S_e,k
Non ?
Sinon, ça m'intéresse aussi indian58
Dans l'exercice que je suis en train de faire, on parle d'une inversion de matrice pour la formule d'inversion ; mais j'avoue avoir du mal à voir ce que vient faire une matrice là-dedans... Peut-être une histoire de déterminant ?
