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

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 :

n 1 2 3 4 5 6 7 8 9 10
Part(n) 1 2 3 5 7 11 15 22 30 42

  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 pk(n) le nombre de décompositions de n en k éléments. On voit, par exemple, ci-dessus que p3(5) = 2 et  p3(8) = 5. Le nombre de partitions est alors :

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

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

Expression de Ak :

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.

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

 Ak = pk-1(n - 1) si k > 1, sinon A1 = 1

Expression de Bk :

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.

  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 Bk = 0.

Bk = pk(n - k) si n - k < k et Bk = 0 sinon

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

n 1, n > k : pk(n) = pk-1(n - 1) + pk(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,  pn(n) renvoie 1 la récurrence ne s'applique pas.
b) k = 1 : décomposition triviale évoquée ci-dessus p
1(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.

Programme JavaScript :

Dans ce programme, très simple grâce à la récursivité, on a créé la fonction part(n,k) pour désigner pk(n). L'appel récursif est zk = part(n,k). Vu que n et k sont modifiés dans le sous-programme récursif, on a créé les variables locales p et q pour désigner respectivement n et k en entrée.

Pour n = 100, Google Chrome trouve 190569292 en moins de 5 secondes, I.E. 10 est beaucoup plus lent. Part(120) 1844349560 est calculé en 45 secondes.

Au-delà, le programme s'enfonce dans les méandres temporels des appels récursifs et tout dépendra de votre ordinateur... Un alt + Ctrl + Suppr sera peut-être nécessaire afin d'arrêter votre explorateur !



 


<SCRIPT
LANGUAGE=JavaScript>
function partition()
{
n=5;
n=eval(prompt("Donnez n : ",n))
if(n==null || n<=0 || n!=Math.floor(n)) {alert ("Valeur de n incorrecte."); return}
nbk=1;if(!confirm("Voulez-vous le nombre de partitions de chaque ordre ?"+"\n"+"Ok pour confirmer, cliquer sur Annuler pour refuser.")) nbk=0
z=0;
for (k=1;k<=n;k++)
{
zk=part(n,k);
if (nbk==1){alert("Pour n = "+n+", le nombre de partitions d'ordre "+k+" est "+zk)}
z=z+zk
}
alert("Le nombres de partitions est "+z)
}

function part(n,k)    
// fonction récursive
{
var p,q
p=n;q=k

if(p==q || q==1) {return 1}  
// si p = 1 ou q = 1, on retourne 1
if(p<q) {return 0} else {return part(p-1,q-1)+part(p-q,q)}
}
</SCRIPT>

 Code HTML du formulaire permettant de lancer les calculs à la demande :

<FORM ACTION="" METHOD=POST>
<CENTER>
<HR>
<INPUT TYPE=button
NAME=Bouton
VALUE="Lancer le programme" onclick="partition()">
<HR>
</CENTER>
</FORM>


© Serge Mehl - www.chronomath.com