démonstration par récurrence ?
Je dois trouver une réponse à la question suivante :
"De combien de façons est il possible d'écrire un entier naturel N comme la somme de nombres entiers naturels non nuls?"
Je crois que la réponse est pour chaque N, 2 á la puissance (N - 1)
Mais je dois démontrer cette hypothèse !!!
Pouvez vous m'aider ?
Je suis pas sur regarde contre exemple 2=1+1 t'a qu'une seule façon de l'ecrire puisqu'ils doivent etre non nuls... et 2^(2-1)=2 dc pas bon. Apres pour ta demo ça m'a pas l'air de la tarte je vais reflechir
en plus est ce que 1+2 et 2+1 compte comme une seule combinaison ou 2? si c'est 1(au sens le plus logique) je dirai que la solution est N-1 valide sur les 3premiers termes...
j'ai une idée:
N= sum(i=1..N,1) lire somme de 1 à N de 1 en fait c'est la somme de N terme valant 1. mais c'est aussi égal à 1+sum(i=1..N-1,1) ...... N-2+sum(i=1..2,1) ce qui te donne en fait N-2 + 1=N-1 façons d'ecrire un nombre N entier
c'est plus du combinatoire que de la recurence.
la question est aussi de savoir s'il s'agit de quelle combinaison on parle.
est-ce que dans la question :
4=1+1+2
et 4=2+1+1 ou 1+2+1
trois reponses ou 1 reponse.
Re : démonstration par récurrence ?
Merci pour la réflexion ... en effet, dans mon devoir, il y a 2 parties.
Dans la première, l'ordre est important. Donc je prends des n-tuplets
(ex : pour N = 4, (4) ; (3,1) ; (1,3) ; (2,1,1) ; (1,2,1) ; (1,1,2) et (1,1,1,1) )
c'est la formule que je n'arrive pas à démontrer.
Dans la deuxième partie, l'ordre ne compte pas, c'est là que je prends les sous ensembles
une piste mais avant une description.
soit S(n) est le nombre de combinaison pour N
c'est bien S(n)=2^(n-1) pour les premiers termes.
1 : (1)
2 : (1,1),(2)
3 : (1,1,1),(1,2),(2,1),(3)
on essaye de compter à chaque fois les combinaisons qui commence par un chiffre croissant. ( 1,2,3 )
pour S(n) le nombre de combinaisons commencant par 1 est s(n-1).
en effet si on a 1 en premier terme, alors la somme du reste vaut n-1.
le nombre de combinaison commencant par 2 vaut S(n-2).
au total :
S(n) = S(n-1)+S(n-2)+S(n-3)+....+S(1)
et ...... +1 car se rajoute la solution du seul chriffre n.
par recurrence:
si S(k)=2^(K-1)
somme de 1 à n-1 des termes vaut sigma de 0 à n-2 de 2^K
soit (1-2^(n-1))/(1-2) = 2^(n-1) -1
auquel il faut rajouter le petit 1 vu plus haut.
cqfd
désolé, la prochaine fois je me met au TEX
je suis pas trop d'accord avec toi ansset pour moi il n'existe qu'une seule facon d'ecrire 2 selon les contraintes de l'énoncé et c'est 1+1. 2+0 n'est pas valable
ça depend ce qu'on appelle somme :
je pense que dans l'exercice :
2=2 est bien un terme.
ceci dit je veux bien reprendre ma demo et enlever à chaque fois 1 ( la solution unique ) à la fin.
ça ne changera rien.
tout sera pareil à 1 près pour chaque estimation.
mais pour le calcul suivant , on garde la solution unique, en combinatoire , et à la fin on ote 1
je ne sais pas pourquoi tu bloques sur ce detail qui ne change pas le calcul.
parce que pour moi (et ce n'est que mon humble impression) l'énoncé est telle que l'ordre n'a pas d'importance et que donc 2+1 ou 1+2 ne compte que pour 1 d'un coup pour moi ça change la formule de recurrence c'est tout. Apres c'est la façon dont je sens l'énoncé
ainsi 2=1+1
3=1+2=1+1+1 2 façons
4=1+3=2+2=1+1+1+1 3 façons
pour moi le nombre de façon c'est N-1
ben relis le mess#6 suite à ma question.
il est question de resoudre les deux combinatoires.
d'ailleurs celle que je trouve correspond elle à l'énoncé
rhooooo !!!Envoyé par zanz
et 4 = 2+1+1 il est parti ou ??????
sorry sorry tu as raison completement d'accord bonne demonstration j'avé pas lu le post en question.
bon, maintenant, il faut se coller à la deuxième demo/calcul.
en version ou l'ordre ne compte pas.
je viens d'essayer ça a l'air plus hard !
j'observe aussi que 29 n'est pas revenu et que je doute que ce soit un exercice de lycée.
mais bon, ça fait travailler les neurones.
