NOMBRES - Curiosités, théorie et usages Accueil DicoNombre Rubriques Nouveautés Édition du: 26/10/2020 Orientation générale  DicoMot Math Atlas Actualités M'écrire Barre de recherche DicoCulture Index alphabétique Références Brèves de Maths
	Partitions
Débutants Algèbre	Fonctions GÉNÉRATRICES				Glossaire Partition
INDEX Suites Partition	Introduction	Nombres entiers	Diviseurs	Principales FG
		Partitions	K termes	Distincts = Impairs
		Sommaire de cette page >>> Relation d'Euler >>> PARTITIONS complètes des entiers >>> PARTITIONS formées de nombres différents >>> PARTITIONS avec k nombres différents >>> La complète

FONCTIONS GÉNÉRATRICES

des QUANTITÉS de PARTITIONS des NOMBRES

Nous savons qu'une fraction polynomiale simple engendre tous les nombres entiers.

Existe-t-il une telle fraction qui donnerait des renseignements sur les partitions des nombres? OUI, elle existe, mais la formule se complique juste un petit peu.

Fonction génératrice d'Euler et son théorème

Voyons cela pas à pas…

Relation d'Euler

Euler montre l'égalité des deux séries suivantes: Développement pour n = 5 S(x) = 1 + x + 2x^2 + 3x^3 + 5x^4 + 7x^5 Exemple de calculs jusqu'à 6 En jaune, le développement pertinent compte tenu du nombre de facteurs dans le produit. Nous reconnaissons bien la quantité de partitions. Voici le développement pour n = 16 Le O(x^13) final indique que le terme suivant sera en puissance 13. Utilisation Nous allons utiliser cette relation et des semblables pour dénombrer les partitions: complète ou alors avec sommants diiférents.

Voir Identité d'Euler avec les nombres premiers / Identités classiques / k-bonacci et partitions

PARTITIONS complètes des entiers
Dénombrement Nous nous intéressons aux partitions des nombres: toutes les sommes possibles sans se préoccuper des permutations des nombres (1 + 2 et 2 + 1 comptent pour une seule partition. Constituons la table qui donne la quantité de partitions des nombres de 1 à 7 Par exemple, pour le nombre 6, il ya 11 sommes possibles: P(6) = 11.			Quantité de partitions des nombres de 1 à 7
En résumé
Polynôme générateur Prenons le polynôme suivant: Développons en sachant que le calcul peut se faire en se souvenant que (pour x proche de 0): 1 / (1 – x ) = 1 + x + x^2 + x^3 + x^4 + … 1 / (1 – x^2) = 1 + x^2 + x^4 + x^6 + x^8 +… 1 / (1 – x^3) = 1 + x^3 + x^6 + x^9 +… etc. Conservons les premiers monômes en les ordonnant selon le degré de x (en rouge à droite). Comparez les coefficients obtenus aux nombres du tableau des partitions ci-dessus. Identique! C'est Euler qui a découvert cette relation.				= 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 etc.
Formule pour toutes les partitions Il existe donc un polynôme qui, une fois développé, donne la quantité des partitions Les coefficients de ce polynôme indiquent la quantité de partitions du nombre exposant de x. P(9) = 30.
Généralisation
Programme MAPLE Les quantités de partitions des cent premiers nombres	1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, 6842, 8349, 10143, 12310, 14883, 17977, 21637, 26015, 31185, 37338, 44583, 53174, 63261, 75175, 89134, 105558, 124754, 147273, 173525, 204226, 239943, 281589, 329931, 386155, 451276, 526823, 614154, 715220, 831820, 966467, 1121505, 1300156, 1505499, 1741630, 2012558, 2323520, 2679689, 3087735, 3554345, 4087968, 4697205, 5392783, 6185689, 7089500, 8118264, 9289091, 10619863, 12132164, 13848650, 15796476, 18004327, 20506255, 23338469, 26543660, 30167357, 34262962, 38887673, 44108109, 49995925, 56634173, 64112359, 72533807, 82010177, 92669720, 104651419, 118114304, 133230930, 150198136, 169229875, 190569292 …

PARTITIONS formées de nombres distincts

Dénombrement

Nous nous intéressons aux partitions des nombres et plus particulièrement aux partitions formées de nombres tous différents.

Constituons la table qui donne la quantité de partitions en nombres différents des nombres de 1 à 7

Par exemple 6 se décompose en

1 partition avec 1 chiffre

2 partitions ayant chacune deux nombres différents

1 partition ayant trois nombres différents

Soit P_d(6) = 4

Bilan

n	Partitions	PartDif	Commentaire
1	1	1	Une partition avec 1 nombre
2	2 1 + 1	1	Une partition avec 1 nombre Deux fois le même nombre
3	3 2 + 1 1 + 1 + 1	1 1	Une partition avec 1 nombre Une partition avec 2 nombres différents Trois fois le même nombre
4	4 3 + 1 2 + 2 2 + 1 + 1 1 + 1 + 1 + 1	1 1	etc.
5	5 4 + 1 3 + 2 3 + 1 + 1 2 + 2 + 1 2 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1	1 1 1
6	6 5 + 1 4 + 2 4 + 1 + 1 3 + 3 3 + 2 + 1 3 + 1 + 1 + 1 2 + 2 + 2 …	1 1 1 1	Première partition avec 3 nombres différents
7	7 6 + 1 5 + 2 5 + 1 + 1 4 + 3 4 + 2 + 1 4 + 1 + 1 + 1 3 + 3 + 1 3 + 2 + 2 …	1 1 1 1 1

Polynôme générateur

Prenons le polynôme suivant:

Développons en ordonnant les monômes selon le degré de x

Comparez les coefficients obtenus aux nombres du tableau des partitions ci-dessus

Identique!

C'est encore Euler qui a découvert cette relation.

(1 + x) (1 + x²) (1 + x³) … (1 + x⁸)

1

+ 1 x¹

+ 1 x²

+ 2 x³

+ 2 x⁴

+ 3 x⁵

+ 4 x⁶

+ 5 x⁷

Tableau limité à x⁷

Formule pour des partitions formées de nombres différents

Il existe un polynôme qui, une fois développé,

donne la quantité des partitions formées de nombres différents

Généralisation

PARTITIONS avec k nombres différents

Dénombrement

Reprenons le tableau des partitions en distinguant la quantité de nombres utilisés pour chaque partition et en repérant les cas avec un, deux ou trois nombres différents.

Constituons la table qui donne la quantité de telles partitions pour les nombres de 1 à 7

Construisons la table des quantités:

n	Partitions	1 nbdif	2 nbdif	3 nbdif
1	1	1
2	2 1 + 1	1
3	3 2 + 1 1 + 1 + 1	1	1
4	4 3 + 1 2 + 2 …	1	1
5	5 4 + 1 3 + 2 3 + 1 + 1 …	1	1 1
6	6 5 + 1 4 + 2 4 + 1 + 1 3 + 3 3 + 2 + 1 3 + 1 + 1 + 1 …	1	1 1	1
7	7 6 + 1 5 + 2 5 + 1 + 1 4 + 3 4 + 2 + 1 4 + 1 + 1 + 1 3 + 2 + 2 …	1	1 1 1	1

Polynôme générateur

Prenons le polynôme suivant:

Développons en ordonnant les monômes selon le degré de x en ligne et de z en colonne.

Comparez les coefficients obtenus aux nombres du tableau des partitions ci-dessus

Identique!

C'est encore Euler qui a découvert cette relation.

(1 + xz) (1 + x²z) (1 + x³z) … (1 + x⁸z)

1

+ 1 x¹ . z¹

+ 1 x² . z¹

+ 1 x³ . z¹ + 1 x³ . z²

+ 1 x⁴ . z¹ + 1 x⁴ . z²

+ 1 x⁵ . z¹ + 2 x⁵ . z²

+ 1 x⁶ . z¹ + 2 x⁶ . z² + 1 x⁶ . z³

+ 1 x⁷ . z¹ + 3 x⁷ . z² + 1 x⁷ . z³

Tableau limité à x⁷

Formule pour des partitions formées de nombres différents

Il existe un polynôme qui, une fois développé,

donne la quantité des partitions formées de nombres différents.

Les coefficients (a, , c …) indiquent la quantité de partitions du nombre k en exactement (a, b, c …) nombres différents.

Voir Partitions strictes (avec nombre différents)

La COMPLÈTE – Combien de partitions formées d'une quantité donnée de nombres

Le coefficient j indique la quantité de partitions du nombre k en exactement h nombres.

Table donnant les développements jusqu'à 10

1
+ 1 x^1 . z^1
+ 1 x^2 . z^1	+ 1 x^2 . z^2
+ 1 x^3 . z^1	+ 1 x^3 . z^2	+ 1 x^3 . z^3
+ 1 x^4 . z^1	+ 2 x^4 . z^2	+ 1 x^4 . z^3	+ 1 x^4 . z^4
+ 1 x^5 . z^1	+ 2 x^5 . z^2	+ 2 x^5 . z^3	+ 1 x^5 . z^4	+ 1 x^5 . z^5
+ 1 x^6 . z^1	+ 3 x^6 . z^2	+ 3 x^6 . z^3	+ 2 x^6 . z^4	+ 1 x^6 . z^5	+ 1 x^6 . z^6
+ 1 x^7 . z^1	+ 3 x^7 . z^2	+ 4 x^7 . z^3	+ 3 x^7 . z^4	+ 2 x^7 . z^5	+ 1 x^7 . z^6	+ 1 x^7 . z^7
+ 1 x^8 . z^1	+ 4 x^8 . z^2	+ 5 x^8 . z^3	+ 5 x^8 . z^4	+ 3 x^8 . z^5	+ 2 x^8 . z^6	+ 1 x^8 . z^7	+ 1 x^8 . z^8
+ 1 x^9 . z^1	+ 4 x^9 . z^2	+ 7 x^9 . z^3	+ 6 x^9 . z^4	+ 5 x^9 . z^5	+ 3 x^9 . z^6	+ 2 x^9 . z^7	+ 1 x^9 . z^8	+ 1 x^9 . z^9
+ 1 x^10.z^1	+ 5 x^10.z^2	+ 8 x^10.z^3	+ 10 x^10.z^4	+ 6 x^10.z^5	+ 5 x^10.z^6	+ 3 x^10.z^7	+ 2 x^10.z^8	+ 1 x^10.z^9	+ 1 x^10.z^10

Exemple

Pour n = 6, prendre la ligne x⁶

Le nombre 6 peut être partitionné en:

1 somme de 1 nombre

3 sommes de 2 nombres

3 sommes de 3 nombres

2 sommes de 4 nombres

etc.

Note

Pour ceux qui voudraient effectuer le développement:

1 / (1 – xz ) = 1 + xz + x²z² + x³ z³ + x⁴ z⁴ + …

1 / (1 – x² z) = 1 + x² z + x⁴ z² + x⁶ z³ + x⁸ z⁴ +…

1 / (1 – x³ z) = 1 + x³ z + x⁶ z² + x⁹ z³ + x¹² z⁴ +…
etc.

Bilan

Nous avons mis en correspondance des fractions qui développées donnent les quantités de partitions des nombres.

Ces formules sont intéressantes sur le plan des mathématiques, mais le calcul pour un nombre n, surtout s'il est grand, est fastidieux

Hélas, il n'existe pas de formule donnant immédiatement le résultat.

Suite	Partitions – Quantité fonction du nombre de sommants Fonctions génératrices – Nombres entiers Tables des FG classiques
Voir	Diviseurs – Introduction Diviseurs – Théorie Suites Fractales
Cette page	http://villemin.gerard.free.fr/Wwwgvmm/Suite/FoncGene.htm