NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 01/02/2018

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique       Brèves de Maths    

     

ADDITION

 

Débutants

Addition

PARTITIONS

 

Glossaire

Addition

 

 

INDEX

 

Partition

 

Calculs

 

Approche

En bref et Index

S'y retrouver

Formules de récurrence

Quantité de partitions

Partielles (1/2)     (2 / 2)

Fonction génératrice

P(1) à P(6)

P(7) à P15)

K-Bonacci

Digi-P

Diff-P

Bi-P

Tri-P

Pri-Bi-P

Pri-Tri-P

 

Sommaire de cette page

>>> Formule de récurrence

>>> Démonstration visuelle

>>> Programmation avec la formule en n

>>> Tables des quantités pour les partitions de 1 à 20

 

 

 

 

 

PARTITIONS – Quantité

Formule de récurrence

  

Calcul de la quantité de partitions à partir d'une formule de récurrence.

 

On nomme p(n, k), les partitions du nombre n avec les seulement les nombres de 1 à k. Il s'agit bien de partitions (sans compter les permutations des nombres).

 

 

 

Formule de récurrence

Relation de récurrence

 

p(n, k) = partition de n en k nombres entiers de 1 à k.

 

Voir Pourquoi deux formules

 

Toujours valable, y compris pour les partitions partielles

 

Valable pour le total des partitions uniquement

 

  avec    p(n, k) = 0 si n < k

  et          p(n, n) = p(n, 1) = 1

 

Exemples

 

Valeurs à lire dans les deux tableaux ci-dessus.

 

p(10, 3) = p(9, 2) + p(7, 3)

              =      4     +      4     = 8

p(17, 3) = p(16, 2) + p(14, 3)

              =      8     +      16     = 24

 

Illustration

 

 

Démonstration visuelle

Exemple avec n = 7 et m = 3. On cherche à calculer p(7, 3), la quantité de toutes les partitions du nombre 7 avec les nombres de 1 à 3.

 

On liste ces permutations en ordre décroissant des sommants (jaune). On les reporte à droite en distinguant deux groupes.

 

En haut (bleu), il s'agit des permutations du nombre 4 avec les nombres de 1 à 3.

En bas (rouge), on reconnait la partition du nombre 6 avec les nombres de 1 à 2.

 

Le total des deux groupes donne la quantité des partitions de 7 avec les nombres de 1 à 3.

 

 

Les partitions sont reportées à droite en isolant, en haut, le plus grand nombre k = 3 et en bas, le plus petit, le 1.

Cette façon de faire isole des sous- partitions plus petites dont la somme des quantités est la quantité cherchée

Attention.jpg

 

 

Pourquoi deux formules?

On trouve souvent la première formule en n – 1 dans la littérature. Elle marche bien pour calculer le total des partitions. Elle est fausse pour le calcul des partitions partielles avec les nombres de 1 à k seulement.

Cet exemple montre comment la configuration  6 = 2 + 2 + 2 est ignorée par la formule en n – 1. 

 

Le programme qui suit utilie la formule en n.
Il est rapide de vérifier que la formule en n – 1 ne fonctionne pas.

 

 

Programmation avec la formule en n

Programme mis en forme

 

Programme pour copie dans Maple

QP := proc (n, k) if n = k then return 1+QP(n, k-1) end if; if k = 0 or n < 0 then return 0 end if; if n = 0 or k = 1 then return 1 end if; return QP(n, k-1)+QP(n-k, k) end proc;

QP(7, 3); seq(QP(n, 3), n = 1 .. 10); seq(QP(7, k), k = 1 .. 7);

 

 

Commentaires

D'abord une procédure reprenant la formule de récurrence, puis le programme principale qui appelle la procédure.

 

La procédure est récursive: elle s'appelle elle-même.

L'algorithme considère:

*      le cas général qui met en jeu la formule récursive (5e ligne);

*      le cas où, n = k qui incrémente le compteur du compte des partitions;

*      le cas où n= 0 ou k<0, témoignant d'une fin de récursivité et laissant le compte où il en est; et

*      le  cas rare où n = 0, pour lequel le compte est mis à 1.

 

Le programme principal donne trois exemples:

*      La quantité de partitions du nombre 7 avec 1, 2 et 3 , égale à 8;

*      Ces valeurs pour les nombres de 1 à 10; et

*      Celles du nombre 7 pour les nombres de 1 à 7. La dernière valeur étant la quantité totale de partitions du nombre 7.

 

 

 

Trace du calcul de P(5, 3) par le programme décrit ci-dessus

Rencontre à cinq reprise du nombre 1: P(5, 3 ) = 5

Explications

Partant de 5,3, la procédure passe les premiers tests  pour arriver à la formule de récurrence. Il retient les deux résultats: P(5, 2) et (2, 3). Poursuite du travail avec le premier et mise en mémoire du second.

Appel à la procédure pour (5, 2) et création de deux nouvelles valeurs: (5,1) et (3,2). Travail avec le premier et mémorisation du second. Etc.

Avec (5, 0), la deuxième condition est activée et le programme passe son chemin sans action (0).

Seul le cas m = k entraine une incrémentation de la quantité de partitions. On en trouve 3 pour la partition de (5, 2) et 2 pour celle de (2, 3). Un total de 5.

 

P(5, 3) = 5

Voir Récursivité / Quantité de partitions (programme) / ProgrammationIndex

 

 

Table obtenue avec le programme mentionné ci-dessus

 

 

 

Table établie avec un tableur qui donne P(n, k = m)

Même tableau que ci-dessus mais avec la quantité de partitions pour chaque k

Ex: p(20, k = 4) ) = 64 (voir cases encadrées)

Voir  Tableur  / TableIndex

 

 

 

 

 

Retour

*    Partitions particulières – S'y retrouver

Suite

*    Quantité de partitions

*    PartitionsIndex

Voir

*    Bipartition

*    Carrés magiques

*    Conjecture de Goldbach

*    Multi-somme de puissances

*    Somme de deux nombres (bipartition)

*    Somme de trois nombres (triparttion)

*    Totient d'Euler

*    Tripartition

Sites

Voir liste générale >>>

Cette page

http://villemin.gerard.free.fr/Wwwgvmm/Addition/PttRecur.htm