Décomposition de 2008 en 3 sommes

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





Posted by: nodgim

Combien de façons différentes peut on décomposer le nombre 2008 en une somme de 3 entiers naturels non nuls ?


Posted by: _-Gaara-_

Salut,

arf je ne sais pas mais voilà mon raisonnement :

de 1 à 2006 il y a 1 + 2006 -1 cad 2006 nombres

Si on fait des permutations (je sait pas pourquoi je dis çà)
donc

2006 nPr 3 = 8060148120 possibilités

Si c'est faux, pas besoin d'en faire un drame ^^ lol

Juste m'expliquer car c'est la première idée qui m'est venue xD

Ou sinon 2006^3 ce qui donne 8072216216 xD


Posted by: Hyp

Voici ma petite idée (qui pourrait s'appliquer à partir de N>5):

Commençons par méditer sur un problème plus simple, et calculons les différentes compositions d'un entier N n'appartenant pas à {0,1} en une somme de deux entiers, non nuls. Après quelques essais on se ramène très facilement à cette formule:

N/2 pour un entier pair (pour des raisons de "symétrie") , (N-1)/2 pour un entier pair .

Il me semble que pour une décomposition en 3 entiers, il suffirait de décomposer en deux puis d'appliquer ces deux formules sur le 1er terme de chaque décomposition, puis sur le 2ème (les deux étapes sont indépendantes). i.e: S= (1er fixé ET 2ème décomposé) OU (1er décomposé ET 2ème fixé)


On peut être sûrs de ne pas avoir une redondance de termes (ou presque), car on l'a déjà évitée dans la 1ère somme (en éliminant la partie symétrique).

Il faudrait bien sûr éviter de prendre en compte la décomposition de la forme 1+(N-1) pour tout N, et si N est pair alors il faut décomposer soit le 1er, soit le 2ème terme de la dernière somme (de la forme N/2 + N/2), vu qu'ils seraient identiques. On aura donc une parfaite assymétrie.

Maintenant il est question de calculer la "densité" des nombres pairs et impairs dans chaque somme. On s'intéressera particulièrement au 1er terme de la somme, en supposant que notre décomposition soit croissante (1+(N-1), 2+(N-2)..)

Si N est pair, alors N se décompose en N/2 sommes de deux termes, dont N/4
1ers termes pairs et N/4 termes impairs, dans le cas où N/2 est pair. Si N/2 est impair alors N se décompose en N/2 sommes de deux termes, dont E(N/4)+1 sont impairs et N/2 -E(N/4)-1 sont pairs. On raisonne de la même manière pour les 2nd termes.
Si N est impair, on se ramène au 1er cas à N-1 près.

Je m'arrête ici pour l'instant parce que je commence à avoir la tête qui tourne . J'ai essayé de cerner tous les cas particuliers qui me sont passés par la tête, mais j'ai l'impression de toucher à une notion assez délicate, et (forcément) déjà bien étudiée.


Posted by: Hyp

Etant très incertain de l'idée précédente, voici quelque chose de bien moins compliqué, quoique restreint à N=2008.

Voici comment on peut parcourir les différentes sommes sans tomber dans la redondance :

1+1+2006, ,1+2+2005,....,1+1003+1004 (STOP)
2+1+2005(redondant!) ,2+2+2004,....,2+1003+1003 (STOP)
3+1+2004(redondant!), 3+2+2004(redondant!),3+3+2003,....,3+1002+1003 (STOP)

En commençant par 4, on se ramène à 4+1002+1002
En commençant par 5, on se ramène à 5+1001+1002
En commençant par 6, on se ramène à 6+1001+1001

Donc ce nombre de fois vaut : 1003+(1003-1)+(1002-2)+(1002-3)+(1001-4)+(1001-5)+...+ ?

Maintenant vérifions la condition d'arrêt:
En fait, l'ittération s'arrête dès qu'il est impossible d'écrire 2008 sous la forme n+n+1, soit 2n<2007 (n entier), soit n=1003.

Finalement: S= 1003+1002+1000+999+997+...
= (1003-k)-501 (k de 0 à 1003)
=1003*1004-(1004*1003/2)-501
=1004*1003/2-501=503005.


Posted by: bruce.ml

Une question imporante qui n'a pas encore été posée :

est-ce qu'on considère les décompositions 2005 + 2 + 1 et 1 + 2005 + 2 comme étant les mêmes ?


Posted by: nodgim

Hip a bien démarré mais son analyse n'est pas assez poussée.
Bien sûr, la décomposition ne doit pas fait apparaitre 2 fois la même combinaison dans le désordre.

Précision: le résultat est une formule simple. Le chemin pour le trouver est plus compliqué, mais ne fait pas appel à des connaissances particulières. Il faut juste un peu de patience.

Bon courage à tous


Posted by: scelerat

Citation:
Posté par Hyp
Finalement: S= 1003+1002+1000+999+997+...
= (1003-k)-501 (k de 0 à 1003)
=1003*1004-(1004*1003/2)-501
=1004*1003/2-501=503005.

J'ai fait autrement, et je trouve 336005. Je range tous les triples possibles de maniere a ce que les 3 nombres y apparaissent croissants, puis je les trie sur le premier nombre comme cle principale et le deuxieme comme cle secondaire. Ca commence donc a {1, 1, 2006} et ca se termine a {669, 669, 670}.
Quand mon premier nombre est i, le second peut prendre les valeurs de i a [(2008-i)/2], soit[\frac{2010-3i}{2}] valeurs, le troisieme est evidemment determine une fois qu'on a les deux premiers. En regroupant i=2k et i=2k-1, j'ai
1 (pour {669, 669, 670} ) + \sum_{k=1}^{k=334} [\frac{2010-6k}{2}]+[\frac{2010-6k+3}{2}]
= 1 + 334*2011 - 6*334*335/2 = 1 + 334*1006 = 336005


Posted by: nodgim

Oui, scélérat c'est la bonne réponse.
Pour un n quelconque, peux tu définir la formule la plus simple possible?


Posted by: lapras

salut,
la formule pour écrire un nombre n en somme de p nombres c'est :
(n + p - 1 ; p-1) (donc p-1 parmis n+p-1)


Posted by: nodgim




Posted by: lapras

Oups j'ai dit une bêtise ?


Posted by: Skullkid

Salut lapras, il me semble que la formule que tu as donnée correspond au nombre de p-uplets d'entiers naturels tels que leur somme soit égale à n : tu tiens compte de l'ordre et pas nodgim.


Posted by: lapras

Ok
dans ce cas il suffit de supprimer les permutations, donc diviser par p!
non ?


Posted by: scelerat

Citation:
Posté par nodgim
Oui, scélérat c'est la bonne réponse.
Pour un n quelconque, peux tu définir la formule la plus simple possible?

C'est assez taupinal, et je me demande si je ne me suis pas trompe, je divise N+2 par 6, ce qui me donne N+2=6p+q, et j'obtiens alors p(3p+2\left[{\frac{q}{2}}\right]-\left[{\frac{q}{3}}\right])


Posted by: nodgim

Scélérat,
Ton résultat était bon, il te reste à synthétiser ta réponse. La formule définitive est très simple.


Posted by: Skullkid

Citation:
Posté par lapras
Ok
dans ce cas il suffit de supprimer les permutations, donc diviser par p!
non ?


Je pense pas que ça marche, parce que les combinaisons de type 8 + 1000 + 1000, où 2 des entiers sont indentiques, ne sont comptées que 3 fois dans \begin{pmatrix} 2010 \\ 2\end{pmatrix}(triplets (8,1000,1000) (1000,8,1000) et (1000,1000,8)). Donc il faut séparer ces cas des autres.

Ici, il y a 3*1005 de ces combinaisons quand on tient compte de l'ordre. Donc si on prend en compte les entiers naturels (pas forcément non nuls) et qu'on ne tient plus compte de l'ordre, on a 3$\frac16\left(\begin{pmatrix} 2010 \\ 2\end{pmatrix}-3\times 1005\right)+\frac13 3\times 1005 = 337010 combinaisons.

Ensuite, comme nodgim demande uniquement les combinaisons avec des entiers naturels non nuls, on retire les 1005 combinaisons qui contiennent 0 et ça fait 336005, résultat trouvé par scelerat, donc je suppose que c'est bon...

M'enfin pour ma part j'ai jamais compris grand-chose aux histoires de dénombrement xD










-