Je pense que ton erreur vient du fait que ce n'est pas choisir n boules parmis p mais c'est un arrangement de p parmis n. Par exemple D(2,2)=A(2,2)=2 D(3,2)= 6 etc...

A+

Donc tu fais comme si il y avait de l'ordre. Pourtant les cases sont indiscernables. Donc il n'y en a pas!
Non?

Oui mais les boules le sont. Remarque l'énoncé n'est pas terriblement clair.

Par exemple, on peut avoir, si n=3 et p=5, en notant 1,2,3,4,5 les boules :

1 3 2
1 2 3
2 5 4
...

Je dirais donc que D(n,p)=pⁿ, mais alors la formule D(p,n)= n D(p-1,n) + D(p-1,n-1) serait fausse donc je ne comprends pas...

Ou alors comme les cases sont indiscernables, ce serait ?

Non ce nombre n'est pas entier en général...

Euh mais oui c'est bien un arrangement de p parmi n !!!! (nombre d'injections d'un ensemble à p éléments dans un ensemble à n éléments)

Désolé...

Conclusion Stokastik?

En fait je n'ai pas pris en compte le fait que l'on puisse ranger deux boules dans une case par exemple. Est ce que toutes les boules doivent être rangés ou bien les cases doivent toutes etre remplis d'une seule case??

Je voulais dire d'une seule boule

allez, on reprend tous et on y va ^^


deja, je suis aps convaincu que sa soit un p parmi n (surtous que p> n quoi ^^ )


pour moi le probleme c'est : j'ai p boule numeroté, combien est-ce que j'ai de facon de faire n tas (non vide) avec, et la c'est coherent avec la formule de recurence donnez :



"Démontrer que D(p,n)= n D(p-1,n) + D(p-1,n-1)"

donc, on veux faire n tas avec p boule discernable.

et bien on peut commencer par faire n tas avec (p-1) boule indiscernable, et il reste donc n facon de rajouter la p-iemme boule (a partir du moment ou les tas contienne qqch ils ne sont plus indiscernables) soit n*D(p-1,n) possibilité, ou bien formez n-1 tas avec les p-1 boules et faire un tas avec la p-iemme boule D(n-1,p-1) possibilité.

d'ou la formule D(p,n)= n D(p-1,n) + D(p-1,n-1)




mais sa na rien a voir avec prendre n parmi p.

en gros le probleme c'est : j'ai p boule numeroté, combien est-ce que j'ai de facon de faire n tas (non vide) avec

Ok donc toi tu penses qu'il faut ranger toutes les n boules, et pas seulement p.

euh tu es sur qu'on parle du meme exo la ?

il y a p boule et n<p... je comprend pas...


enfin oui dans tous les cas je pense qu'il faut ranger toute les boules et qu'on peut en metre plusieur par tas.

Ah, ok...

Donc vous partez du principe qu'on peut mettre plusieurs boules dans une même case. C'est ça??

Au fait, le prof a dit que pour répondre à la question, on pouvait utiliser les suites...

Oui Ksilver tu as raison, hier soir ça n'allait vraiment pas fort pour moi...

Céline77, utiliser les suites pour quelle question ?

Je sais pas...

Peut-être pour le 2.
"2. Calculer : D(n,n), D(p,1), D(p,2), D(p,3) et D(p,p-1)"

Donc, si j'ai bien compris :

D(n,n) = 1 : je ne peux faire que n tas avec n boules (dans chaque tas, je n'ai qu'une boule)

D(p,1) :
- j'ai p possibilités si je mets 1 seule boule dans le tas.
- j'ai C(2,p) possibilités si je mets 2 boules dans le tas.
- j'ai C(3,p) ....................... 3 ...................
...
Donc D(p,1) = somme des C(k,p) pour k allant de 1 à p

J'ai bon pour l'instant??

Non, il faut mettre toutes les boules apparamment. Si n=1 il n'y a qu'une case donc on n'a pas le choix, on met toutes les p boules dans cette case.

Maintenant je sais pas s'il faut différencier les tas, auquel cas D(p,1)=p!

A priori non puisque les cases sont indiscernables...
Donc on obtient : D(p,1) = D(n,n) = 1??
Et pour
D(p,2)=somme des k avec k allant de 1 à p-1 car :
- on met le 1 ds la première case puis il reste p-1 possibilités pour la 2ème
Ou
- on met le 2 ................................. p-2 ..........................
Ou
- on met le 3 ................................. p-3 ..........................
etc...

C'est bon là ou pas???

Mais dans le cas où il n'y a qu'une case et disons 3 boules numérotées 1, 2, 3, on peut faire un tas 1-2-3, un tas 3-2-1, un tas 2-1-3, etc... non ? C'est cela que je voulais dire.

"2. Calculer : D(n,n), D(p,1), D(p,2), D(p,3) et D(p,p-1)"


bon D(n,n) = 1 puisque fait n tas avec n boule il y a qu'une seul facon ^^


D(p,1) = 1 puisque fait 1 tas avec p boule, il y a qu'une seul facon.

D(p,p-1) = 2 parmi p car la seul "inconu" est : qu'elles sont les 2 boules qui seront regroupé entre elles (j'ai un tres leger doute sur celle ci...)



D(p,2) = 2*D(p-1,2) + D(p-1,1) = 2*D(p-1) +1

on a une recurence du tupe Up =  2*Up-1 +1, avec U2=1

on trouve donc que pour tous p> 2 D(p,2)=2^(p-1)-1



D(p,3) = 3*D(p-1,3)+(2^(p-1) -1 ) et D(3,3) = 1

la c'est un peu plus compliqué... on a une recurence lineair avec un second membre, il faut donc chercher "une sollution particulière" au probleme de l'equation avec second membre (par superposition, puisqu'on a deux therme dans le second membre) et y ajouter la solution general de l'equation sans second membre, ici k*3^n

la sollutino particuliere de Up = 3*Up-1 -1 est 1/2

celle de Up = 3 Up-1 + 2^(p-1) est... on va chercher Up de la forme k*2^p,
et on trouve 2k=3k + 1, d'ou k = -1

donc a priori D(p,3) = k*3^p -2^p +1/2 et comme D(3,3) = 1

on trouve k=17/54 ...

bon je vais faire quelque verification numerique quand meme parceque je suis pas trop sur de moi ...

donc apres verification, j'ai un peu cafouiller sur D(p,3)

on trouve D(p,3) = (3^(p-1)+1)/2 - 2^(p-1)

je vois pas l'erreur dans mon calcule, mais la methode est bonne... doit y avoir un pti cafouillage dans les identifications...

Bon alors si cette fois j'ai bien compris, D(p,n) est le nombre de surjections d'un ensemble à p éléments dans un ensemble à n élements.

euh la en revanche je sais pas :S



sa serait pas mettre p boule diferenciable, dans n urne differenciable avec aucune vide, le nombre de surjection ?

et dans ce cas, est ce que le rappport entre les deux c'est n! ?

Par exemple la surjection f : {1, 2, 3, 4} -> {A, B, C} définie par f(1)=f(2)=A, f(3)=B, f(4)=C correspondrait aux trois tas {1, 2}, {3}, {4}.

Ca m'a l'air d'être ça. Mais franchement l'enoncé de cet exercice n'est pas clair comme de l'eau de roche.



et dans ce cas, est ce que le rappport entre les deux c'est n! ?

? je ne comprends pas.

Ksilver, je crois que ta formule pour D(p,2) est fausse.

euh non j'ai rien dit, sorry

et dans ce cas, est ce que le rappport entre les deux c'est n! ?

je crois que j'ai compris ce que tu veux dire : je me suis planté et D(n,p) serait le nombre de surjections divisé par n!, c'est ça ?

Ca doit être ça, D(p,n) est le nombre de partitions d'un ensemble à p éléments en n parties non vides.

Si S(n,p) désigne  le nombre de surjections d'un ensemble à p éléments dans un ensemble à n éléments, on a la relation S(p,n)=n!D(p,n).

oui la je pense que suis d'accord avec toi.

le n! a l'air logique, mais d'un autre coté, sa voudrai dire que le nombre de surjection sur un ensemble a n element est toujour divisible par n! ce qui na en sois meme rien d'evident non ?

Salut Céline,


le problème consiste à remplir n cases (aucune vide, 1 ou plusieurs boules par case) en utilisant la totalité des p boules.

Soit D(p-1,n) le nombre de possibilités de remplir n cases avec p-1 boules

Si on prend 1 boule supplémentaire, les possibilités sont :
  1) rajouter cette boule dans chacune des n cases et ceci pour les D(p-1,n) solutions vues ci-dessus
     soit n D(p-1,n) possibilités
  2) poser cette boule dans une case et reste alors D(p-1,n-1) possibilités de disposer les p-1 boules restantes dans les n-1 cases restantes.

donc CQFD       D(p,n) = n D(p-1,n) + D(p-1,n-1)

Bisous

Jean-Marc