v1.1.4
Olivier Gibaud
Mai 2021
N=
Nombre de partitions
Liste des partitions
Informations
...
...
Partitions : décomposition additive d'un nombre entier Mode d'emploi : * Choisir un nombre n (5 par défaut, de 1 à 100) * Demander son nombre de partitions OU la liste de ses partitions * Conseil : commencer avec des nombres inférieurs à 20 * ******************************************************************* Définitions et caractéristiques : * Le nombre de partitions d'un nombre n c'est le nombre de façons d'obtenir ce nombre par additions d'1 à n nombres. * L'ordre d'une partition c'est son nombre de termes : il varie entre 1 et n. * Les deux partitions triviales sont : le nombre n lui-même (ordre 1) la partition qui contient 1, n fois (ordre n). Exemple pour 5 : 5 (ordre 1) et 1+1+1+1+1 (ordre 5) * Les partitions d'ordre 2 sont tous les compléments à n Exemple pour 10 : 19+1, 8+2, 7+3, 6+4, 5+5 ******************************************************************* * P(n) : nombre de partitions de l'entier n * P(1) = 1, P(2) = 2, P(3) = 3, P(4) = 5, P(5) = 7, * P(6) = 11, P(7) = 15, P(8) = 22, P(9) = 30, P(10) = 42 ******************************************************************* * Formule d'Euler : * Le produit de 1/1-x n, avec n puissance qui varie de 1 à l'infini * est égal à : 1 + P(1)x 1 + P(2)x 2 + P(3) x 3 + ... P(n) x n + .... * soit : 1 + 1 x 1 + 2 x 2 + 3 x 3 + 5 x 4 + 7 x 5 + 11 x 6 + 15 x 7 + 22 x 8 + 30 x 9 + 42 x 10 + ... * Attention : dans ces polynomes ce qui suit x est une puissance qui varie de 1 à l'infini * Les coefficients sont les P(n) ******************************************************************* Temps de calcul : algorithme linéaire (? ...) n ==> Durée ==> P(n)=Nombre de partitions de n ==> Durée Liste des partitions 10 ==> 0 ms ==> 42 ==> 1 ms 20 ==> 1 ms ==> 627 ==> 4 ms 30 ==> 1 ms ==> 5 604 ==> 60 ms 40 ==> 4 ms ==> 37 338 ==> 1000 ms = 1 s 50 ==> 17 ms ==> 204 226 ==> 10 s 80 ==> 1 s ==> 15 796 476 ==> !!! (estimé : 10 min ?) 100 == 13 s ==> 190 569 292 ==> !!!! (estimé : 2 h ?) > 100 ==> Explosion combinatoire ! Remarque : les temps de calcul sont approximatifs et dépendent évidemment du navigateur et de l'ordinateur.