Démonstration - nombre de surjections ?

g_h · 30/09/2005, 23h25

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

$Card(Surj(E, F)) = \sum_{k=0}^{f} \left(\left(\begin{array}{c} f \\ k \end{array}\right)(-1)^{k}(f-k)^e \right)$

Si vous avez une démonstration, un début de démonstration ou même rien qu'une piste, ça m'intéresse !

Merci !

**Romain-des-Bois** · 01/10/2005, 09h43

Citation:

Posté par g_h

Soit e le cardinal de E, et f le cardinal de F

$Card(Surj(E, F)) = \sum_{k=0}^{f} \left(\left(\begin{array}{c} f \\ k \end{array}\right)(-1)^{k}(f-k)^e \right)$

Salut g_h,

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

g_h · 01/10/2005, 10h06

Merci pour ta réponse !
Seulement je ne comprends pas... c'est quoi E_p et E_k ?

Citation:

Posté par Romain29

avec S_p,k, les surjections de E_p vers E_k

**Romain-des-Bois** · 01/10/2005, 10h09

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

g_h · 01/10/2005, 10h25

Citation:

Posté par Romain29

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é ?
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 ?

**Romain-des-Bois** · 01/10/2005, 10h31

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 !)

g_h · 01/10/2005, 10h50

Citation:

Posté par Romain29

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_k
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 !

g_h · 02/10/2005, 16h28

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

**Romain-des-Bois** · 02/10/2005, 16h42

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.

g_h · 02/10/2005, 16h53

Ok, merci beaucoup pour ton aide !!
J'espère pouvoir m'en tirer

indian58 · 02/10/2005, 18h20

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.

g_h · 02/10/2005, 18h42

Citation:

Posté par Romain29

Clairement : avec un dessin

card(A_k) = la somme de k=0 à n de (k parmie f) x S_e,f

Plutôt la somme de k=0 à f de (k parmie f) x S_e,k
Non ?

Sinon, ça m'intéresse aussi indian58