ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

Partitions d'un entier naturel          programme JavaScript       » Décomposition d'en entier en somme de carrés ou de cubes

Objectif :    

On recherche le nombre de décompositions, appelées partitions, d'un entier naturel non nul n en tant que sommes d'entiers non nuls qui lui sont inférieurs, indépendamment de l'ordre d'écriture.

 ➔   Les entiers entrant dans la décomposition, qualifiés de parties, sont non nuls car on pourrait écrire 4 = 4 + 0 mais aussi 4 = 1 + 0 + 0 + 2 + 0 + 1 + 0 + 0..., etc. : on convient donc de ne pas utiliser de zéro dans la décomposition.

En dehors du cas trivial ci-dessus, l'entier se décompose en partitions de 2, 3, ..., n éléments. En considérant n = 4, la partition 3 + 1 sera dite d'ordre 2 et la partition 2 + 1 + 1 est dite d'ordre 3.

  Eu égard à notre remarque préliminaire, n lui-même s'interprétera comme l'unique partition d'ordre 1.

L'objectif est de dénombrer toutes les partitions. Notons Part(n) ce nombre. On a pour n ≤ 10 :

•  1    ordre 1

•  2    ordre 1
      = 1 + 1    ordre 2

•  3   ordre 1
          = 2 + 1    ordre 2
      = 1 + 1 + 1    ordre 3

•  4    ordre 1
      = 3 + 1 = 2 + 2    ordre 2
      = 2 + 1 + 1   ordre 3
      = 1 + 1 + 1 + 1    ordre 4

•  5    ordre 1
           5=4+1=3+2
          =3+1+1=2+2+1
          =2+1+1+1
          =1+1+1+1+1

•  6    ordre 1
          = 5 + 1 = 4 + 2 = 3 + 3    ordre 2
      = 4 + 1 + 1 = 3 + 2 + 1 = 2 + 2 + 2    ordre 3
      = 3 + 1 + 1 + 1 = 2 + 2 + 1 + 1    ordre 4
      = 2 + 1 + 1 + 1 + 1    ordre 5
      = 1 + 1 + 1 + 1 + 1 + 1    ordre 6

•7    ordre 1
          = 6 + 1 = 5 + 2 = 4 + 3    ordre 2
      = 5 + 1 + 1 = 4 + 2 + 1 = 3 + 3 + 1 = 3 + 2 + 2   ordre 3
      = 4 + 1 + 1 + 1 = 3 + 2 + 1 + 1 = 2 + 2 + 2 + 1   ordre 4
      = 3 + 1 + 1 + 1 + 1 = 2 + 2 + 1 + 1 + 1    ordre 5
      = 2 + 1 + 1 + 1 + 1 + 1    ordre 6
          = 1 + 1 + 1 + 1 + 1 + 1 + 1    ordre 7

•  8     ordre 1
          = 7 + 1 = 6 + 2 = 5 + 3 = 4 + 4    ordre 2
      = 6 + 1 + 1 = 5 + 2 + 1 = 4 + 3 + 1 = 4 + 2 + 2 = 3 + 3 + 2    ordre 3
      = 5 + 1 + 1 + 1 = 4 + 2 + 1 + 1 = 3 + 3 + 1 + 1 = 3 + 2 + 2 + 1 = 2 + 2 + 2 + 2    ordre 4
      = 4 + 1 + 1 + 1 + 1 = 3 + 2 + 1 + 1 + 1 = 2 + 2 + 2 + 1 + 1    ordre 5
      = 3 + 1 + 1 + 1 + 1 + 1 = 2 + 2 + 1 + 1 + 1 + 1    ordre 6
      = 2 + 1 + 1 + 1 + 1 + 1 + 1    ordre 7
      = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1    ordre 8

Étude :   

Notons p_k(n) le nombre de décompositions de n en k éléments. On voit, par exemple, ci-dessus que p₃(5) = 2 et  p₃(8) = 5. Le nombre de partitions est alors :

Nous choisissons un algorithme récursif :  l'algorithme de calcul de la fonction p_k fait appel à elle-même dans sa programmation. Il nous faut trouver une formule de récurrence pour le calcul des p_k(n).

Considérons d'une part les partitions de n d'ordre k contenant au moins un 1 (nombre A_k) et, d'autre part, celles ne contenant aucun 1 (nombre B_k). On aura p_k(n) = A_k + B_k.

Expression de A_k :

Connaissant les partitions de n - 1 (n ≥ 2), nous obtiendrons une partition de n contenant au moins un 1 en ajoutant + 1 à la suite de toutes les partitions de n - 1 d'ordre k - 1.

• Pour n = 8, k = 3, le nombre A₃ = p₂(7) = 3 est visualisé en orange ci-dessus.

 ➔    Il nous faudra ici  k - 1 non nul, c'est à dire k ≠ 1. Si k = 1, le programme retournera p₁(n) = 1 : c'est le cas de l'ordre 1 étudié en début de page.

 A_k = p_k-1(n - 1) si k > 1, sinon A₁ = 1

Expression de B_k :

Afin d'obtenir toutes les partitions de n d'ordre k ne contenant aucun 1, on passe au rang n - k (si cela se peut) et on ajoute 1 à chaque élément des partitions de n - k d'ordre k.

• Pour le cas n = 8, k = 3, le nombre B₃ = p₃(5) = 2 est visualisé en bleu ci-dessus.

 ➔    Il nous faudra ici  n - k ≥ k, c'est à dire n ≥ 2k. Supposons qu'il n'en soit pas ainsi, alors k > n/2. Si les partitions d'ordre k ne contiennent aucun 1, alors on n'y rencontrera que des entiers ≥ 2 dont la somme n vérifiera n ≥ 2k > n : ce n'est pas possible ! En conclusion si n - k < k, les partitions contiennent au moins un 1 et on doit poser B_k = 0.

B_k = p_k(n - k) si n - k < k et B_k = 0 sinon

Finalement, le programme se fondera sur l'appel récursif :

∀ n ≥ 1, n > k : p_k(n) = p_k-1(n - 1) + p_k(n - k)

L'étude a montré que les conditions d'arrêt du programme sont :

a) n = k : c'est la partition ne contenant que des 1,  p_n(n) renvoie 1 → la récurrence ne s'applique pas.
b) k = 1 : décomposition triviale évoquée ci-dessus p₁(n) renvoie 1 → la récurrence ne s'applique pas.
b) n < k : c'est à dire n - k < 0, p_k(n - k) renvoie 0 → la récurrence ne s'applique pas.