Dénombrement

[tsinapah]

Bonjour,

Je cherche à dénombrer le nombre de façons de disposer t boules dans k urnes, sachant que chaque urne u_i a une capacité c_i maximale (nombre de boules maximal que l'urne u_i peut contenir).

Quelqu'un a une idée?

[Quidam]

Bonjour,

Je cherche à dénombrer le nombre de façons de disposer t boules dans k urnes, sachant que chaque urne u_i a une capacité c_i maximale (nombre de boules maximal que l'urne u_i peut contenir).

Quelqu'un a une idée?

Cela paraît assez compliqué car cela dépend des valeurs des . Trouver une formule générale est complexe. Par contre, si tous les sont égaux, cela peut se faire sans trop de difficlultés.

Dans un espace à k dimensions, cela revient à trouver le nombre de points de l'hyperplan défini par qui aient des coordonnées entières et qui soient intérieurs (y compris les bords) au parallélépipède défini par Cela visualise un peu le problème et sa complexité.

A deux dimensions (k=2) on est déjà obligé de faire trois cas distincts. Je suppose que
Le premier cas : , on a :
et
ou et
ou et
...
ou et
... ce qui fait façons différentes.

Le deuxième cas : , on a :
et
ou bien et
ou bien et
...
ou bien et
... ce qui fait façons différentes.

Le troisième cas : , on a :
et
ou bien et
...
ou bien et
... ce qui fait façons différentes.

C'est donc assez tordu à 2 dimensions. A trois dimensions c'est bien pire. En fait, pour revenir à l'espace à k dimensions auquel je faisais référence, à trois dimensions, tu peux imaginer un plan d'équation , perpendiculaire donc à la droite d'équations . Faire varier t revient donc à déplacer ce plan parallèlement à sa direction initiale. On comprend qu'à chaque fois que l'on traverse un coin, la formule donnant le nombre de façons change. Or il y a 8 coins dans un cube ! Cela veut dire qu'il y aurait 7 zones, avec 7 réponses différentes dans le pire des cas. Et en plus, on ne sait pas dans quel ordre seraient les valeurs limites, car si l'on sait que , on ne sait pas dans quel ordre seraient les limites internes , et

A quatre dimensions, il y aurait 15 (2^4-1) zones, et avec k urnes, 2^k-1 zones...

Tout cela peut sûrement se simplifier énormément si les sont tous égaux, mais il semble que ton problème est vraiment très très général !

P.S. Peut-être, en trouvant une super astuce quelqu'un d'autre pourrait... Mais moi, je ne vois pas comment faire simple !

[tsinapah]

Merci pour cette analyse détaillée du problème,

mais ouais çà ne m'a pas l'air simple de trouver une formule générale...