Décomposer 38 en somme de 4 nombres

Mr_Propre_

Bonjour
Je tiens à informer dès le début du post que j'ai à peine le niveau terminale en mathématiques.

J'essaye de trouver en combien de possibilités on pourrait décomposer le nombre 38 en somme de 4 nombres (Ces nombres vont de 1 à 19).
Si possible aussi pour 5 nombres.

J'ai déja essayé avec 3 chiffres j'ai trouvé 30 combinaisons (j'ai fait à la main alors peut-être qu'il en manque il faudrait que je me relise).
Je veux simplement savoir si c'est possible de toutes les écrire à la main ou si c'est peine perdue (au delà de 100 combinaisons je pense que ça va être très fastidieux).
Si c'est trop important j’essaierai de construire un algorithme permettant de toutes me les lister. Je vous avoue que j'ai beaucoup de mal avec cela et je vous remercie pour les éventuels pistes que vous pourriez me donner. Bonne soirée.

YvesM

Bonjour,

Acceptes-tu $1+1+1+35=38$, $1+2+3+32=38$, $0+0+0+38=38$ ?

Quelles sont les contraintes précises ?

marsup

La question est un peu ambigüe car les deux écritures : $
\begin{aligned}[t]
38 & = 10 + 14 + 15 \\
& = 14 + 15 + 10\\
\end{aligned}
$
ça compte pour une ou bien pour deux ?

Dans le cas où l'ordre des termes compte,
je trouve :
207 écritures pour trois termes,
4506 pour quatre,
50475 pour cinq

Je l'ai fait en Scilab à la va-vite.

dixNeuf = 19

function [n,s] = somme(A,t)
  if (t==1)
    if (A>0 && A<=dixNeuf)
      n = 1
      s = [A]
    else
      n = 0
      s = []
    end
  else
    n = 0
    s = []
    for k=1:dixNeuf
      [nn,ss] = somme(A-k,t-1)
      n = n + nn
      if (nn>0)
        s = [ s; (k * ones(nn,1)),ss]
      end
    end
  end
endfunction

[n,s] = somme(38,4)
disp(n)
//disp(s)

michael

YvesM : il a précisé que les quatre nombres sont entre $1$ et $19$.

Fin de partie

Il y a $7770$ façon d'obtenir $38$ comme une somme de $4$ entiers naturels non nuls.

Attention: $1+2+3+32=38$ et $32+3+2+1=38$ sont comptés, par exemple, comme deux façons différentes d'écrire $38$ comme une somme de $4$ nombres entiers naturels non nuls.

Avec la contrainte que les quatre nombres doivent être compris entre $1$ et $19$ alors il y a $4506$ sommes possibles.

PS:
petit script pour GP PARI qui permet de vérifier ce nombre:

polcoeff(sum(n=1,19,x^n)^4,x,38);

Ou si vous préférez un programme pour GP PARI qui est plus facile à comprendre:

s=0;for(a=1,19,for(b=1,19,for(c=1,19,for(d=1,19,if(a+b+c+d==38,s++)))));print(s);

PS:
Avec la même contrainte mais si on s'intéresse aux sommes de trois nombres qui font $38$ on obtient exactement $207$ telles sommes.

YvesM

Bonjour,

On cherche le nombre de solutions de l’équation $x_1+x_2+...x_n=S$ avec les contraintes sur chaque nombre $0\leq x_k\leq L_k$. On sait démontrer une formule et un algorithme assez simple.

rosab

Bonjour,

Les esclaves numériques font ça très facilement (ici Mathematica, disponible sur Wolfram Alpha) :

In[1]:= Select[IntegerPartitions[38, {3}], #1 <= 19 &]
Out[1]= {{19, 18, 1}, {19, 17, 2}, {19, 16, 3}, {19, 15, 4}, {19, 14,
5}, {19, 13, 6}, {19, 12, 7}, {19, 11, 8}, {19, 10, 9}, {18, 18,
2}, {18, 17, 3}, {18, 16, 4}, {18, 15, 5}, {18, 14, 6}, {18, 13,
7}, {18, 12, 8}, {18, 11, 9}, {18, 10, 10}, {17, 17, 4}, {17, 16,
5}, {17, 15, 6}, {17, 14, 7}, {17, 13, 8}, {17, 12, 9}, {17, 11,
10}, {16, 16, 6}, {16, 15, 7}, {16, 14, 8}, {16, 13, 9}, {16, 12,
10}, {16, 11, 11}, {15, 15, 8}, {15, 14, 9}, {15, 13, 10}, {15, 12,
11}, {14, 14, 10}, {14, 13, 11}, {14, 12, 12}, {13, 13, 12}}

Pour les partitions en 4 ou 5 nombres, je donne juste le compte, mais on pourrait les lister de la même manière :

In[2]:= Length[Select[IntegerPartitions[38, {4}], #1 <= 19 &]]
Out[2]= 237

In[3]:= Length[Select[IntegerPartitions[38, {5}], #1 <= 19 &]]
Out[3]= 677

marsup

Et sinon, si on veut compter comme une seule solution deux écritures qui ont les mêmes termes dans un ordre différent,

je trouve :
39 décompositions pour trois termes
237 pour quatre
677 pour cinq

Les décompositions à trois termes :

38 = 13 + 13 + 12     (1)
   = 14 + 12 + 12     (2)
   = 14 + 13 + 11     (3)
   = 14 + 14 + 10     (4)
   = 15 + 12 + 11     (5)
   = 15 + 13 + 10     (6)
   = 15 + 14 + 9      (7)
   = 15 + 15 + 8      (8)
   = 16 + 11 + 11     (9)
   = 16 + 12 + 10     (10)
   = 16 + 13 + 9      (11)
   = 16 + 14 + 8      (12)
   = 16 + 15 + 7      (13)
   = 16 + 16 + 6      (14)
   = 17 + 11 + 10     (15)
   = 17 + 12 + 9      (16)
   = 17 + 13 + 8      (17)
   = 17 + 14 + 7      (18)
   = 17 + 15 + 6      (19)
   = 17 + 16 + 5      (20)
   = 17 + 17 + 4      (21)
   = 18 + 10 + 10     (22)
   = 18 + 11 + 9      (23)
   = 18 + 12 + 8      (24)
   = 18 + 13 + 7      (25)
   = 18 + 14 + 6      (26)
   = 18 + 15 + 5      (27)
   = 18 + 16 + 4      (28)
   = 18 + 17 + 3      (29)
   = 18 + 18 + 2      (30)
   = 19 + 10 + 9      (31)
   = 19 + 11 + 8      (32)
   = 19 + 12 + 7      (33)
   = 19 + 13 + 6      (34)
   = 19 + 14 + 5      (35)
   = 19 + 15 + 4      (36)
   = 19 + 16 + 3      (37)
   = 19 + 17 + 2      (38)
   = 19 + 18 + 1      (39)

Scilab :

dixNeuf = 19

function [n,s] = somme(A,t,dixNeuf)
  if (t==1)
    if (A>0 && A<=dixNeuf)
      n = 1
      s = [A]
    else
      n = 0
      s = []
    end
  else
    n = 0
    s = []
    for k=1:dixNeuf
      [nn,ss] = somme(A-k,t-1,k)
      n = n + nn
      if (nn>0)
        s = [ s; (k * ones(nn,1)),ss]
      end
    end
  end
endfunction

[n,s] = somme(38,3)
disp(n)
disp(s)

Fin de partie

Rosab:

Probablement que dans ton calcul tu fais un compte d'ensembles.

Par exemple: les sommes $1+2+3+32$ et $32+3+2+1$ ne sont pas considérées comme différentes.

Mr_Propre_

Effectivement deux écritures dans un ordre différent sont considérés comme identiques je m'excuse de ce manque de clarté.
Je tiens à vous remercier j'ai beaucoup de piste et beaucoup d'algorithme permettant de continuer mes recherches. Ce forum est une mine d'or.
Bonne journée !