Des billes et des sacs
Une question qui devrait être facile mais dont je n'arrive pas à retrouver le résultat ( vous pouvez me huer):
Soit p billes à distribuer dans n sacs, combien ai-je de distributions possibles? Les billes comme les sacs sont indiscernables.
Merci
Bonjour,
il s'agit du nombre d'applications d'un ensemble àéléments (les billes) vers un ensemble à
Pour le trouver :
tu prends la première bille, tu as
tu prends la deuxième bille, tu as encore
...
tu prends la
j'ai aussi du mal a repondre
je dirais que pour D(n,p) = somme pour m de 0 a p des D(n-1,p-m)
avec D(1,p) = 1
D(2,p) = p+1
D(3,p) = ((p+1)+1)*(p+1) /2 = 1/2 * (p² + 3p + 2)
ca me semble juste mais j'ai un peu de mal a trouver la solution comme ca...
mais a premiere vue, ca sera une solution avec des factorielles
dans ce cas c'est le nombre de partages (P,N)Les billes comme les sacs sont indiscernables
partages de 7 en 3:
7+0+0
6+1+0
5+2+0
5+1+1
4+3+0
4+2+1
3+3+1
3+2+2
donc # partages (7,3) = 8
il n'y a pas de formule autre que "le dénombrement à la main" à ce que je sache sauf pour des cas triviaux genre N ou P = 1 ou 2
Ca n'est pas le nombre d'application de 1..p dans 1..n puisque si je prend f tq, f(1)=1 et f(2)=1 et 2 pour tous le reste donne la même solution que f(1)=1, f(3)=1 et 2pour tout le reste.
Segatasan, si je regarde les possibilité pour 2,3 j'ai seulement(3,0) et (2,1). Par contre ça marche (pour ce terme) si tu rend les sacs discernable, alors il faudrait juste diviser par n!
Mais je ne comprend pas comment tu trouve ta formule?
acx01b, oui je suis arrivé à la même conclusion.Il n'y a vraiment pas de formule ou vous ne la connaissez pas? Il me semble vraiment avoir déjà été confronté au même problème...
Merci à vous tous
Euh, est-ce que ce raisonnement est juste?
Si je discerne les billes et les sacs j'ai effectivement n^p possibilités.
Comme toute permutation des billes donnent le même resultat si je rend les billes indiscernables j'ai n^p/p! possibilités.De même en rendant les sacs indiscernables il me reste n^p/(n!p!).
J'obtient donc une jolie formule absurde en faisant un ou deux essais(et qui tend vers 0 en plus) la question est donc: où est-ce faux?
En faisant une petite recherche, il n'y a effectivement pas de formule pour le partage d'un entier. On a simplement une fonction recurisve forte relativement sympathique pour une recursivité non resoluble...
Merci à tous.
Desolé pour le triple post et merci à tous.
exact, j'ai discerné les différents sacs (erreur de ma part)
pour trouver cette formule, j'ai simplement dit :
pour N sacs, en mettant un sac a part, on a 0 billes "a part" et toutes les repartitions possibles pour p billes dans N-1 sacs + 1 bille a part et p-1 billes dans N-1 sacs, puis 2 billes a part et p-2 billes dans N-1 sacs, etc...
cependant, je refuse categoriquement l'idée qu'il n'y a aucune formule ^^
il y en a forcement une : c'est pas comme la suite des nombres premiers ou autre suite de nombres ayant des propritétés particulieres
ma methode, c'est de trouver les formules en fixant N
et de voir si les resultats ont une relation qui les relie entre elles
ca m'interesse, je chercherai la reponse ^^
ca ressemble a un probleme de "k parmi n" mais c'est pas aussi simple ici car il ne s'agit pas d'un nombre de combinaisons mais d'une repartition
d'ailleurs, en disant ca, ca me donne une idée...
ça serait pas
je viens de me rendre compte d'un truc
en fixant 2 sacs, la solution est E(p/2)+1
et j'ai comprit du meme coup que c'etait finalement un probleme similaire a la recherche des nombres premiers, taxicab, etc
il n'y a donc peut etre pas de formule generale
mais... pourtant je sens qu'il y en a une ^^
il y a une formule pour "k parmi n"
il doit donc y en avoir une aussi pour ca !
J'admet que c'est très énervant, mais d'après wikipédia on n'en connait pas. Quoique en résolvant une recurrence planaire de type triangle de pascal ça se fait(y a plus qu'à...)
wikipedia se plante parfois...
bon, j'admet que je suis du genre obstiné, tenace et surtout TETU
cependant, le fait que l'on puisse trouver une solution pour N fixé me fait dire qu'il n'est pas impossible de trouver une formule generale
ca y est, j'ai pas encore trouvé la solution mais a force d'y penser, j'ai comprit un truc interessant :
etant donné que le nombre de billes est fixe, on cherche le nombre de vecteurs de type (a1,b2,...,aN) tel que a1+a2+...+aN=p
on cherche simplement les solutions positives sur cet hyperplan
on peut donc, quel que soit la dimension, calculer la longueur, surface, volume (selon la dimension) et eliminer les resultats redondants par symetrie sur ce plan
donc je n'ai pour le moment pas de resultat concret a donner, mais maintenant que j'ai comprit ca, je sais que je pourrais au moins determiner une formule approchée qui donnera un premier resultat
ca correspondrait grosso modo a la solution qui j'ai proposé plus haut en discernant les sacs (on obtient toutes les combinaisons de a1+a2+...+aN=p)
pour eliminer les resultats par symetrie, il faudrait diviser par N(N-1)
cependant, comme certains points sont symetriques d'eux memes, ce n'est pas tout a fait vrai (par exemple, pour N=2 et p=8, on a le couple (5,3) symetrique de (3,5), mais (4,4) est son propre symetrique)
on a donc une certaine erreur (mais "y'a qu'a la comprendre")
Je poursuis cette idée:Envoyé par segatasan
On a
On pose
Donc
Ce qui donne avec
Donc
Quel est le l'adresse du lien?
Voilà le lien...mais oui c'est wikipédia... http://fr.wikipedia.org/wiki/Fonctio..._d%27un_entier
Dans l'idée de "on discerne et on retire ce qui est pareil" on peut peut-être tirer quelquechose d'un truc algorithmique du genre:
Je fait un tableau à n ligne et p colonnes (on peut mettre au plus p billes dans un sac, sinon y en a plus) Je dispose p éléments sur ce tableau , ça fait p parmi pn. il reste à retirer les solutions identiques...ce qui devrait revenir à l'étude d'une partie bizarre du groupe symétrique.
je ne suis pas d'accord avec
on pose plutôt D(n,p,m) : nombre de partages de l'entier p en n sacs avec au maximum m billes par sac
on pose D(n,p) : nombre de partages de l'entier p en n sac sans nombre maximum de billes par sac (le nombre qui nous intéresse)
on a D(n,p) = D(n,p,p)
et
D(n,p,m) = 0 si n.m < p
D(1,p,m) = 1 si m >= p
D(n,1,m) = 1 si m >= 1
si dans le PREMIER sac (premier => un ordre dans les sacs) on met k boules alors dans les autres sacs on ne peut mettre plus de k boules
ce qui assure que le nombre de billes par sac est décroissant et donc qu'on n'a pas d'ordre dans les sacs (voir mon post plus haut le nombre de billes par sac est toujours décroissant)
le nombre de vecteurs d'entiers de dimension n où la somme des composantes = p c'est le nombre de sélections ou combinaisons avec répétitions
= C(n+p-1,p)
