Dénombrement

par **Ben314** » 02 Fév 2010, 14:31

Salut,
Suite au post de bobo696 (le zoo), une question (de dénombrement) me vient à l'esprit :

On se donne des nombres entiers naturels L1,L2,...,Ln, C1,C2,...Cm tels que L1+L2+...+Ln=C1+C2+...+Cm.

On cherche alors le nombre de "rectangles" de n lignes et m colonnes contenant des entiers naturels tels que, pour tout i,j la somme des entiers de la ligne i soit Li et la somme des entiers de la colonne j soit Cj...

P.S. bien entendu, je n'ais pas la réponse...

par **gungan** » 02 Fév 2010, 14:48

Ben314 a écrit:P.S. bien entendu, je n'ais pas la réponse...

alors comment tu fait pour savoir si c'est juste ce qu'on dit? :hum:

par **Ben314** » 02 Fév 2010, 14:51

gungan a écrit:alors comment tu fait pour savoir si c'est juste ce qu'on dit? :hum:

Ce que vous (tu ?) dit(es) où ?
Ici (énigme 'dénombrement') je pose une question, je cherche moi même une soluce (s'il en existe une) et je regarde si d'autres ont des idées.

P.S. si ta question concerne le "petit problème de logique, urgent" du primaire, je suis formel : seule émilie dit la vérité.

par **nodgim** » 02 Fév 2010, 18:44

Ben314 a écrit:Salut,
Suite au post de bobo696 (le zoo), une question (de dénombrement) me vient à l'esprit :

On se donne des nombres entiers naturels L1,L2,...,Ln, C1,C2,...Cm tels que L1+L2+...+Ln=C1+C2+...+Cm.

On cherche alors le nombre de "rectangles" de n lignes et m colonnes contenant des entiers naturels tels que, pour tout i,j la somme des entiers de la ligne i soit Li et la somme des entiers de la colonne j soit Cj...

P.S. bien entendu, je n'ais pas la réponse...

Je ne saisis pas encore bien l'intérêt que la somme des Ci et celle des Li soit identique...

par **Ben314** » 02 Fév 2010, 18:50

nodgim a écrit:Je ne saisis pas encore bien l'intérêt que la somme des Ci et celle des Li soit identique...

Ben, la somme de Li et la sommedes Cj, représentent deux façons de calculer la somme de tout les entiers du rectangle, donc si ces somme sont distinctes, y'a pas de solutions....

par **nodgim** » 02 Fév 2010, 19:00

Ben314 a écrit:Ben, la somme de Li et la sommedes Cj, représentent deux façons de calculer la somme de tout les entiers du rectangle, donc si ces somme sont distinctes, y'a pas de solutions....

Oui, j'ai compris juste après avoir posé la question. Tourner la souris 7 fois avant d'écrire...

par **Doraki** » 02 Fév 2010, 19:09

Ca m'étonnerait qu'on trouve une formule simple =|

par **nodgim** » 02 Fév 2010, 19:10

On peut déja dire que si min(Li)CV=Somme des (Li-card C) et (Ci-card L) pour tous les Li
C'est une première approche.

par **Ben314** » 02 Fév 2010, 19:42

Doraki a écrit:Ca m'étonnerait qu'on trouve une formule simple =|

Comme je suis pas un grand expert en dénomprement, on va dire que "je pose la question..."

En fait, j'arrive même pas à écrire une récurence "simple" (i.e. un algo. pas trop moche pour faire le calcul...)

P.S. si j'y pense faudra que je regarde dans les deux livres de Comtet s'il y a quelque chose...

par **nodgim** » 03 Fév 2010, 10:51

La quantité de cases vides est variable, car on peut trouver plusieurs solutions pour un rectangle et une somme donnée, il suffit pour s'en convaincre d'établir un rectangle 2*3 avec des sommes minimales.
Il est cependant assez facile de déterminer le minimum de cases vides auquel on ne peut échapper.

par **ffpower** » 03 Fév 2010, 18:26

Une idée pour démarrer : utiliser des séries génératrices. Pour éviter trop de sigma, disons m=n=2, Alors le nombre cherché et le coefficent devant

de la série

Cela se généralise bien en m x n, la fonction à regarder étant alors

i allant de 1 à n, j allant de 1 à m. Bon apres faut le calculer ce coeff, par exemple en intégrant sur le cercle, ou en regardant les dérivées en 0. J ai pas encore essayé mais p-e que c est pas évident. En tout cas, je pense qu il y a au moins moyen de trouver un développement assymptotique..

par **ffpower** » 03 Fév 2010, 20:07

Bon, je comfirme, un calcul direct semble compliqué. J ai même pas réussi à prouver que si L1+L2 diff de C1+C2, alors le coeff est nul ( a part en "remontant" le calcul bien sur )
Mais j'ai confiance, les séries génératrices ont souvent fait leurs preuves dans ce genre d exos.. Faut p-e faire un bon changement de variable ou un truc du genre..

par **Doraki** » 03 Fév 2010, 21:03

Si on a 2 lignes et 2 colonnes, ça reste simple :
il y a 1 + min(L1,L2,C1,C2) manières de remplir le tableau

par **nodgim** » 04 Fév 2010, 17:54

Le tout est de savoir ce qu'on veut maintenant. Si le nombre de cases vides est variable, si le nombre mini est assez facile à trouver, reste à trouver le max. Entre les 2, que chercher de plus ?

par **Ben314** » 04 Fév 2010, 18:45

Au départ, je me demandais s'il y avait une "formule assez simple" pour dénombrer le nombre de tel rectangles.
Pour uniquement une ligne de k éléments dont la somme doit valoir un nombre fixé S, on sait qu'il y a

(coeff binomial) façons de remplir cette ligne.

Par contre, en regardant d'un peu plus prés, je pense que Doraki a raison : pas de formule simple !!!
En particulier, le cas d'un rectangle de deux lignes et n colonnes équivaut à chercher des entiers de somme fixé MAIS en ayant des contraintes de taille maxi pour chacun d'eux et ça, il me semble que déjà, c'est la m...

A la limite, un truc qui peut être (vaguement) rigolo, c'est celui qui trouve la preuve la plus courte montrant qu'il y a au moins une solution (j'en ait une mais pas "super courte")

On peut aussi chercher l'algo. informatique le plus rapide donnant le nombre de solutions (là, ce sait pas trop par quel bout m'y prendre...)

Dénombrement

Dénombrement

Qui est en ligne