Dénombrement

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: Skullkid

Bonsoir, il faut que je fasse mon deuil sur une question de dénombrement :

A_{k,n} désigne l'ensemble des applications de |[1,k]| dans |[1,n]|, B_{k,n} celui des applications surjectives de |[1,k]| dans |[1,n]|, son cardinal est noté s_{k,n}.
C_{k,n} est l'ensemble des applications f de |[1,n]| dans \mathbb{N} telles que \displaystyle \sum_{i=1}^n f(i)=k.
D_{k,n} est le sous-ensemble de C_{k,n} formé des f telles que f(i)\ge 1 pour tout i de |[1,n]|.

Pour n, k entiers naturels et x_1,x_2,\cdots,x_n réels on a :

3$ \displaystyle (x_1+\cdots+x_n)^k=\sum_{f \in C_{k,n}}\frac{k!}{f(1)! \cdots f(n)!}x_1^{f(1)}\cdots x_n^{f(n)}=\sum_{\varphi \in A_{k,n}}x_{\varphi (1)}\cdots x_{\varphi (k)}

La question est : montrer que pour 0 < n \le k on a 3$ \displaystyle s_{k,n}=\sum_{f \in D_{k,n}}\frac{k!}{f(1)! \cdots f(n)!}

Je me doute qu'il faut appliquer le lemme des bergers avec une application bien choisie de B_{k,n} dans D_{k,n} mais je vois pas trop laquelle...(je suis pas très doué là-dedans)

Cette question provient de l'épreuve de Maths II MP de l'X de cet après-midi... j'en tremble encore xD

Merci d'avance aux bonnes âmes qui pourront m'éclairer :)


Posted by: ThSQ

Ca avait l'air sympa :)

J'aurais fait comme ça :

On prend une permutation de 1..k (y'en a k! oeuf corse). Ensuite on "regroupe" des éléments consécutifs qu'on "envoie" vers 1,2, .., n.
On obtient bien toutes les surjections et il faut diviser par f(1)!.. car les éléments dans un même groupe compte pareil.
Et à chaque f correspond un ensemble de surjections.

Par exemple :
1,3,2 -> |1,3|,|2| -> 1,2 dans le cas s-{3,2} pareil que
1,3,2 -> |3,1|,|2| -> 1,2


Posted by: Skullkid

Citation:
Posté par ThSQ
Ca avait l'air sympa :)

Ah ça, si t'aimes compter les surjections (ça change des moutons...), le sujet est fait pour toi :)

Je crois que je saisis à peu près ton idée, je vais encore y réfléchir un peu. Mais ce qui me gêne c'est que je pense qu'il faut se servir des identités que j'ai données au-dessus, parce que le \frac{k!}{f(1)! \cdots f(n)!} y apparaît également. Merci pour ta réponse rapide en tout cas, je vais pouvoir dormir ce soir xD


Posted by: ThSQ

Citation:
Posté par Skullkid
Ah ça, si t'aimes compter les surjections (ça change des moutons...), le sujet est fait pour toi :)


J'aime bien la combinatoire (plus que les equa diff en tout cas ....... ;-) )










-