Bonjour à tous,
J'ai besoin de votre aide pour ce problème. Soient N, J deux entiers naturels non nuls tel que J =< N. On voudrait déterminer de combien de façons on pourrait écrire le nombre N comme la somme de J entiers positifs non nuls.
Par exemple (N= 10 et J=3):
On a huit possibilités :
(1,1,8) ; (1,2,7) ; (1,3,6) ; (1,4,5) ; (2,2,6) ; (2,3,5) ; (2,4,4); (3,3,4)
Merci d'avance
bonjour,
en introduisant la notation f(n,j,k) pour le nombre de façons d'écrire n comme la somme de j nombres supérieurs ou égaux à k de manière croissante au sens large (ou sans tenir compte de l'ordre si tu préfères), ce que tu cherches est f(n,j,1)
tu as la relation de récurrence f(n,j,1)=f(n-1,j-1,1)+f(n-2,j-1,2)+...+f(n-k,j-1,k) où k est le plus grand nombre tel que k*(j-1)<= n-k. On a donc une sorte de "pyramide de Pascal" par référence au triangle du même métal. Mais est-ce que ça aide vraiment?
Bonjour,
Une récurrence plus simple est possible :
On peut découper l'ensemble E(n, j) des solutions en deux sous-ensembles disjoints
A(n, j) = Ensemble des solutions dans lesquelles il y a au moins une fois le nombre 1
B(n, j) = Ensemble des solutions où tous les nombres sont plus grand que 1.
En notant p(n, j), le nombre d'ensemble de j nombres dont la somme est n :
Pour fabriquer A(n, j), il faut et il suffit de fabriquer E(n-1, j-1) (dont le cardinal est p(n-1, j-1)), et d'ajouter 1.
Pour fabriquer B(n, j), il faut et il suffit de fabriquer E(n - j, j) (dont le cardinal est p(n-j, j)) et d'ajouter 1 à chaque nombre
On obtient la relation : p(n, j) = p(n-1, j-1) + p(n-j, j)
On peut remarquer que p(n, 1) = p(n,n) = 1
Dernière modification par Médiat ; 24/09/2010 à 05h24. Motif: Orthographe/grammaire
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
