NOMBRES - Curiosités, théorie et usages

 

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

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

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

            

Théorie des Nombres

 

Débutants

Nombres

COURS

 

Glossaire

Nombres

 

 

INDEX

 

Sommaire

 

Partitions

Accueil

Nombres

Partition (1/2)

Partition (2/2)

Partition PG

Partition en couleurs

Terminale

 

Sommaire de cette page

>>> Quantité de partitions

>>> Partitions en 3 sommants

>>> Partitions en k sommants

>>> Compositions à k sommants

>>> Curiosité avec Fibonacci

>>> Anglais

 

 

 

 

 

PARTITIONS des nombres

Quantité et polynômes générateurs

 

Revue des polynômes dont les coefficients indiquent la quantité de partitions d'un nombre dans certaines conditions.

Surprise de rerouver la suite de Fibonacci ou ses cousines les k-bonacci.

 

On notera bien la distinction entre:

*    PARTITION de N: toutes les sommes donnant N sans tenir compte de l'ordre des termes, ici appelés: sommants.

*    COMPOSITION de N: toutes les partitions y compris leurs permutations avec les nombres de 1 à k.

Anglais: partition, composition, sommand or addend

 

 

Quantité de partitions

Euler (1707-1783) introduit une formule de calcul des partitions des nombres entiers qui fait intervenir les nombres polygonaux généralisés.

 

 

 

 

Partitions en 3 sommants

But

Voyons la partition du nombre 7.
Parmi ses 15 partitions, il y en a quatre avec trois sommants.

On cherche à connaitre cette quantité pour tous les nombres.

 

Partition de 7

[1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 2],

[1, 1, 1, 2, 2], [1, 1, 1, 1, 3],

[1, 2, 2, 2],  [1, 1, 2, 3], [1, 1, 1, 4],

[2, 2, 3], [1, 3, 3], [1, 2, 4], [1, 1, 5],

[3, 4], [2, 5], [1, 6],

[7]

 

Programme

 

Commentaires

Le programme est en deux parties:

*      une procédure de calcul de la quantité k de sommants d'un nombre n et

*      du programme principal demandant ce calcul pour des valeurs données de n.

 

La procédure commence en faisant appel au logiciel spécialisé en combinatoire et en calcul de partitions (combinat).

Le compteur de partitions kt est initialisé à 0.

On place la liste des partitions dans PN et on calcule la quantité de terme (qPN).

La boucle sert à reconnaitre les partitions à k termes. Chaque partition PN[i] est examinée. La quantité de nombres qI est comparée à k pour faire progresser le compteur kt.

La procédure retourne ce nombre kt, quantité de fois où le nombre de termes de la partition est égal à k.

 

Le programme principal calcule la suite la quantité de partitions (QP) du nombre n en k sommants pour tous les nombres de n égal 1 à 50.

 

Résultat

Liste pour les nombres de 1 à 50 des quantités de partitions de trois termes.

Pour le nombre 7, on retrouve bien kt = 4 en septième position.

 

 

 Voir ProgrammationIndex

Programmation de la quantité de partitions avec formule récursive

 

 

Polynôme générateur

Ce polynôme engendre la suite des quantités de partions de trois termes

 

 

 

En le développant en série
Notez que les deux premiers nombres en 0 sont exclus.

 

 

Partitions en k sommants

Pour 2 sommants

 

P(7, 2) = 3

 

Liste

0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10 …

 

Polynôme générateur

Pour 3 sommants

 

P(7, 3) = 4

 

Liste

0, 0, 1, 1, 2, 3, 4, 5, 7, 8, 10, 12, 14, 16, 19, 21, 24, 27, 30, 33…

 

Polynôme générateur

Pour 4 sommants

 

P(7, 4) = 3

 

Liste

0, 0, 0, 1, 1, 2, 3, 5, 6, 9, 11, 15, 18, 23, 27, 34, 39, 47, 54, 64 …

 

Polynôme générateur

Pour k sommants

 

Polynôme générateur

 

 

 

Compositions à k sommants

 

But

Voyons la partition du nombre 7.
Parmi ses 15 partitions, il y en a quatre formées avec les seuls nombres 1et 2. En comptant les permutations:

C(7, 2) = 21

 

Pour [1, 1, 1, 2, 2], il y a 5! permutations, mais 3! sont identiques avec les 1 et 2! avec les 2. Si bien que la quantité de permutations effective est:

 

Ces calculs sont traités en détail sur les pages Escalier 2 et Escalier 3

 

 

Partition de 7

[1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 2],

[1, 1, 1, 2, 2], [1, 1, 1, 1, 3],

[1, 2, 2, 2],  [1, 1, 2, 3], [1, 1, 1, 4],

[2, 2, 3], [1, 3, 3], [1, 2, 4], [1, 1, 5],

[3, 4], [2, 5], [1, 6],

[7]

 

Composition de 7 par 1 et 2

[1, 1, 1, 1, 1, 1, 1] => 1 permutation

[1, 1, 1, 1, 1, 2] => 6 permutations

[1, 1, 1, 2, 2] => 10 permutations

[1, 2, 2, 2] => 4 permutations

Total:  21 permutations

            =  quantité de compositions

 

Polynômes générateurs

Ces polynômes donnent à la fois les quantités de compositions et les nombres de Fibonacci généralisés comme les tribonacci et tous les k-bonacci.

 

Ils sont étudiés et programmés en: Polynômes générateurs des nombres k-bonacci.

 

Polynômes générateurs

 

 

 

 

 Curiosité avec Fibonacci

C(3,3) = [ [1 + 1 + 1], [1 + 2], [2 + 1], [3] ]

Transformation en somme de produit

E = (1 x 1 x 1) + (1 x 2) + (2 x 1) + (3) = 1 + 2 + 2 + 3 = 8

Or 8 est le sixième (2x3) nombre de Fibonacci (1, 1, 2, 3, 5, 8 …)

 

C(4,4) = [ [1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4] ]

Transformation en somme de produit en tenant compte des permutations

E = (1 x 1 x 1 x 1) + 3(1 x 1 x 2) + (2 x 2) + 2(1, 3) + 4 = 21

Or 21 est le huitième (2x4) nombre de Fibonacci (… 5, 8, 13, 21 …)

 

On note la relation:            C(n, n) = F2n

La quantité de compositions complètes de n est égale au nombre de Fibonacci de rang double. 

Source: Relationship between Ordered Compositions and Fibonacci Numbers – Soumendra Bera - 2015

 

 

 

English corner

 

Partitions of a positive integer n including permutations of the parts or summands are called compositions of n. 

There exists a definite order of the compositions of n, which has close connection with the Fibonacci sequence.

The partition function gives the number of ways of writing the integer n as a sum of positive integers, where the order of addends is not considered significant. 

 

For example, eight compositions of 4 are: [4],

[3 + 1], [1 + 3], [2 + 2],

[2 + 1 + 1], [1 + 2 + 1],

[1 + 1 + 2], [1 + 1 + 1 + 1].

 

 

 

 

Retour

*         Partition

Suite

*         Quantité de partitions – Quantité avec sommants différents

*        Partition en couleurs

*        Polynômes générateurs – Programmation

En savoir plus

*         AdditionGlossaire  

*         Conjecture de Goldbach

*         Escalier et partitions

*         Nombre d'Ulam

*         Nombres (représentation)

*         Nombres quatrops

*         Partition des nombres de 1 à 10

*        Partition en couleurs

*         PartitionsDéveloppements 

*         Partitions – Fonctions génératrices

*         Partitions et jeu de dés – Formule et calculs

*         Polygones à périmètre magique

*         Rectangles magiques à répétitions

*         Somme des nombres impairs

Références

*         DicoMot

*         DicoNombre

*         Glossaire mathématique

Voir

*         CalculIndex

*           Conjecture de Goldbach

*         Jeux et puzzlesIndex

*         Nombres modulo

*         Nombres par leur petit nom

*         Systématique Index

*           Théorie des NombresIndex

Site

*         Partition d'un entier – Wikipédia

*         Partition Function P – Wolfram MathWorld

*         OEIS A000041a(n) = number of partitions of n (the partition numbers).

Cette page

http://villemin.gerard.free.fr/Referenc/Prof/APROF/PartitiG.htm