Problème d'arithmétique

[alexis6]

Bonjour,

Voici un problème:

Si on prends un entier naturel, on peut l'écrire sous la forme de différentes sommes, par exemple, 5 peut s'écrire 1+1+1+1+1; 2+1+1+1; 2+2+1; 3+1+1; 3+2; 4+1, 5). J'essaye de trouver une fonction F qui donnerait en fonction de n le nombre d'écritures possibles.

Bon j'ai quelques éléments de résolution:

1) F(0)=1, F(1)=1 F(2)=2 F(3)=3 F(4)=5. Bon déjà on observe que cela commence comme une suite Fibonacci.

2) J'ai un petit raisonnement avec la division euclidienne mais bon pour l'instant c'est pas très concluant.

Si on part d'un entier naturel n, on peut toujours l'écrire: 1+1+...+1, c'est à dire en utilisant n fois le chiffre 1. On peut regrouper les deux premiers 1: 1+1+...+1 = 2+1+...+1. On peut faire la même chose une seconde fois 2+1+...+1= 2+2+...+1. On peut répéter cette opération un nombre q de fois, où q représente le quotient de la division euclidienne de n par 2. On obtient ainsi q écritures du nombre n considéré. On peut refaire ces opérations pour 3, 4, ..., jusqu'à n. On obtient finalement q2+q3+..+qn écritures du nombre considéré.

Le problème c'est que même si avec cette technique on obtient la majorité des écritures, on a par exemple: 5=3+2.

[WillyCagnes]

bjr

voir ces liens pour t'aider
http://www.prise2tete.fr/forum/viewtopic.php?id=8929

http://openclassrooms.com/forum/sujet/nombre-de-facon-d-ecrire-une-somme-44967

http://www.developpez.net/forums/d655365/general-developpement/algorithme-mathematiques/algorithmes/nombre-facon-d-ecrire-somme-recursivite-complexe/

[nodjim]

Il y a aussi un article sur wiki:
http://fr.wikipedia.org/wiki/Partition_d%27un_entier
Ce n'est pas un problème simple, sauf si on veut une partition ordonnée (221 et 212 comptent pour 2 partitions différentes).

[zygomatique]

salut

par contre tu peux toujours te simplifier le pb en étudiant déjà simplement les partitions en 1 et 2 (ordonnée et non ordonnée)

....

[Pseuda]

Une piste (je n'ai pas approfondi) : par exemple 5 peut s'écrire en une somme de 5, 4, 3, 2 ou 1 chiffres. A chaque fois, par exemple en une somme de 3 chiffres, combien de possibilités.

[alexis6]

salut

par contre tu peux toujours te simplifier le pb en étudiant déjà simplement les partitions en 1 et 2 (ordonnée et non ordonnée)

....

Pour les partitions ou on a que 1 et un autre type de chiffre ( soit une minoration du nombre final ):
Une approximation serait 1 + n/2 + n/3 + ... + n/n
Par exemple
pour n=2: 1+2/2=2
pour n=3:1+3/2+3/3=3.5
pour n=4: 1+4/2+4/3+4/4=5.33
pour n=5 1+5/2+5/3+5/4+5/5=7.41

La différence avec le vrai résultat étant donné par la somme de tous les restes des divisions successives. Et pour avoir le vrai résultat, il faudrait remplacer toutes les divisions par les quotients des divisions euclidiennes correspondantes.

Merci également pour les liens, je viens de jeter un coup d'oeil, ça a l'air bien compliqué, surtout si on tient compte de l'ordre.

[zygomatique]

n'importe quoi !!!

je te parle de partitionner un entier en somme de 1 et de 2 !!

1 = 1

2 = 1 + 1 = 2

3 = 1 + 1 + 1 = 1 + 2 = 2 + 1

(et même (peut-être) ne pas considérer les sommes identiques à permutation près : à voir)

4 = 1 + 1 + 1 + 1 = 1 + 1 + 2 = 2 + 2

5 = 1 + 1 + 1 + 1 + 1 = 1 + 1 + 1 + 2 = 1 + 2 + 2

....

[alexis6]

n'importe quoi !!!

je te parle de partitionner un entier en somme de 1 et de 2 !!

1 = 1

2 = 1 + 1 = 2

3 = 1 + 1 + 1 = 1 + 2 = 2 + 1

(et même (peut-être) ne pas considérer les sommes identiques à permutation près : à voir)

4 = 1 + 1 + 1 + 1 = 1 + 1 + 2 = 2 + 2

5 = 1 + 1 + 1 + 1 + 1 = 1 + 1 + 1 + 2 = 1 + 2 + 2

....

Oui en effet je me suis trompé, mais c'est plus une erreur de compréhension que de raisonnement ( si vous voyez ce que je veux dire ).

Erreur de compréhension: mal lu la question
Erreur de raisonnement: erreur logique dans le raisonnement

Mon message est juste mais ne réponds pas à la même question.
Mais sinon la réponse au problème est assez simple: c'est la division euclidienne de n par 2 + 1 ( en fait ma réponse précédente est une généralisation de ta question ).

On peut faire une disjonction de cas:

Si on prend n pair c'est facile: c'est 1+n/2. Si on prend la sous suite des pairs, bah cette suite est la suite U0= 1 et Un+1= Un + 1... En effet Un+1 = 1+(n+2)/2=2+n/2= Un + 1. Autrement dit Un=n.
Pour les impairs, une approximation est donnée par 1 + n/2.

[nodjim]

alexis,
Sauf erreur, la 1ere formule trouvée pour le nb de partitions d'un entier est due à Ramanujan. Je n'ai plus la formule en tête, mais c'est à coucher dehors. Ensuite, elle a été simplifiée, mais elle reste compliquée. Que cela ne t'empêche pas de persévérer si tu penses pouvoir faire encore plus simple.
Sinon, il y a une formule propre pour une partition en somme de 3 nombres max. Au dela, ce n'est plus possible.