NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 02/05/2016

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

Barre de recherche          DicoCulture              Index alphabétique                               

     

PARTITION

 

Débutants

Addition

Somme d'entiers

 

Glossaire

Addition

 

 

INDEX

 

 

Partition

 

Introduction

S'y retrouver

BI partition

TRI partition

Quantité de partitions

Digi partition

Prim BI partition

Prim TRI partition

Formule récurrence

Diff. Partition

 

Sommaire de cette page

>>> Approche – Somme de deux nombres

>>> Approche – Somme de deux nombres

>>> Formule de récurrence

>>> Bilan

>>> Table

 

 

 

 

 

 

PARTITIONS

Formule de récurrence

  

Calcul du nombre de partitions à partir d'une formule de récurrence.

 

 

Approche – Somme de deux nombres

Combien de sommes de deux nombres pour faire 10 ?

 

5 possibilités

 

Combien de sommes de deux nombres pour faire 100?

 

50 possibilités

 

Ensuite …

Évolution: incrémentation de 1 à chaque nombre pair.

 

 

Approche – Somme de trois nombres

Combien de sommes de trois nombres pour faire 10 ?

 

8 possibilités

 

Combien de sommes de trois nombres pour faire 100 ?

 

833 possibilités

Évolution

N le nombre; k la quantité de partitions en trois nombres; dk le supplément de partitions par rapport au nombre précédent.

 

 

Formule de récurrence

Relation de récurrence

 

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

 

p(n, k) = p(n–1, k-1) + p(n–k, k)

  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

Comprendre

 

 

Comprendre la formule

 

Prenons les tripartitions de 3 à 10

 

 

La partie jaune correspond aux partitions commençant par 1.

La partie blanche se retrouve pour n – 3 en ajoutant 1 à chaque nombre: le (1, 1, 1) du 3 se retrouve en (2, 2, 2) du 6; les trois partitions du 7 se retrouvent, incrémentée de 1, dans la zone blanche du 10.

 

 

Zone jaune

En oubliant le 1, ce sont les bipartitions de n – 1,
soit p(n–1, k–1); la première partie de la formule.

Zone blanche

Nous avons constatez qu'il s'agit de la tripartition des nombres n – 3, incrémentés de 1. En quantité, c'est la même chose,
soit p(n–k,  3), la seconde partie de la formule.

 

Bilan

De proche en proche, à la main, avec un tableur ou par programmation, il est possible de quantifier toutes les partitions des nombres.

 

 

Table établie avec un tableur

Ex: p(20, 4) ) = p(19, 3) + p(16, 3) = 64 (voir cases encadrées)

Voir  Tableur  / TableIndex

 

 

 

 

 

 

Suite

*    Bipartition

*    Tripartition

*    Initiation à la théorie des nombres – Partitions

*    S'y retrouver

Voir

*    Addition - Glossaire

*    Addition des carrés

*    Addition des entiers

*    Addition des puissances

*    Carrés magiques

*    Conjecture de Goldbach

*    Multi-somme de puissances

*    Totient d'Euler

Site

*    Partition d'un entier – Wikipédia

*    Integer Partition Table (de 0 à 34) – Wikipedia

*    Lectures of Integer partitions – Herbert Wilf  - niveau avancé

*    Table des quantités de partitions de 0 à 4096

*    OEIS A000041 – Quantité de partitions

*    OEIS A046063 – Quantité de partitions premières

Cette page

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