Partition: quantité de partitions, dénombrement

NOMBRES - Curiosités, théorie et usages Accueil DicoNombre Rubriques Nouveautés Édition du: 10/06/2014 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	Digi partition	Diff. Partition
	S'y retrouver	BI partition	TRI partition
	Quantité de partitions	Prim BI partition	Prim TRI partition
	Sommaire de cette page >>> Quantité de partitions de 1 à 100 Formules >>> Quantité totale >>> Quantité propre de partitions >>> Formule citée par Nathanson >>> Relation d'Euler

PARTITION - Quantité

Décomposition d'un nombre en sommes de nombres.

Combien ?

Formule ?

QUANTITÉ DE PARTITIONS de 1 à 100

n	Quantité de partitions	n	Quantité de partitions
1	1	51	239 943
2	2	52	281 589
3	3	53	329 931
4	5	54	386 155
5	7	55	451 276
6	11	56	526 823
7	15	57	614 154
8	22	58	715 220
9	30	59	831 820
10	42	60	966 467
11	56	61	1 121 505
12	77	62	1 300 156
13	101	63	1 505 499
14	135	64	1 741 630
15	176	65	2 012 558
16	231	66	2 323 520
17	297	67	2 679 689
18	385	68	3 087 735
19	490	69	3 554 345
20	627	70	4 087 968
21	792	71	4 697 205
22	1 002	72	5 392 783
23	1 255	73	6 185 689
24	1 575	74	7 089 500
25	1 958	75	8 118 264
26	2 436	76	9 289 091
27	3 010	77	10 619 863
28	3 718	78	12 132 164
29	4 565	79	13 848 650
30	5 604	80	15 796 476
31	6 842	81	18 004 327
32	8 349	82	20 506 255
33	10 143	83	23 338 469
34	12 310	84	26 543 660
35	14 883	85	30 167 357
36	17 977	86	34 262 962
37	21 637	87	38 887 673
38	26 015	88	44 108 109
39	31 185	89	49 995 925
40	37 338	90	56 634 173
41	44 583	91	64 112 359
42	53 174	92	72 533 807
43	63 261	93	82 010 177
44	75 175	94	92 669 720
45	89 134	95	104 651 419
46	105 558	96	118 114 304
47	124 754	97	133 230 930
48	147 273	98	150 198 136
49	173 525	99	169 229 875
50	204 226	*100*	190 569 292

Voir Tables

QUANTITÉ TOTALE (toutes les possibilités)

Dénombrement

Le nombre de sommes pour partitionner n est 2^n-1.

Exemple

3 = 1 + 1 + 1 = 1 + 2 = 2 + 1

4 possibilités (dont le nombre lui-même)

Soit: 4 = 2^3-1

Démonstration

On écrit tous les " 1 " pour faire n en les ajoutant.

On forme les nombres à ajouter en mettant un espace entre les " 1 " souhaités et un signe + entre les blocs ainsi constitués

Exemple

1 1 1 + 1 1 + 1 => 3 + 2 + 1

On dénombre les combinaisons de + ou espaces entre ces " 1 ".

Il y a deux signes pour n-1 positions, soit 2^n-1 possibilités.

Note

Il s'agit de toutes les possibilités imaginables, y compris, les permutations.
Comme 5 = 3 + 2 = 2 + 3 qui comptent pour 2 partitions.

QUANTITÉ PROPRE DE PARTITIONS

Quantité de partitions

Il n'existe pas de formule simple donnant la quantité p(n) de décompositions d'un nombre n en somme de nombres.
Vers 1918, Ramanujan et Hardy trouve une limite asymptotique qui conduit à la formule:

Eux-mêmes, puis d'autres comme Rademacher en 1937, donnèrent d'autres formules plus précises, mais beaucoup plus compliquées.

Que donne la formule ?

n	p(n)	Calcul	Écart en ‰
10	42	48	145
20	627	692	104
30	5 604	6 080	85
40	37 338	40 080	73
50	204 226	217 590	65
100	190 569 292	199 280 893	45
200	3 972 999 029 388	0, 41 10^13	32
300	9 253 082 936 723 602	0, 95 10^16	26
400	6 727 090 051 741 041 926	0, 69 10^19	22
500	2 300 165 032 574 323 995 027	0, 234 10^22	20
1 000	24 061 467 864 032 622 473 692 149 727 991	0, 244 10^32	14
2 000	4 720 819 175 619 413 888 601 432 406 799 959 512 200 344 166	0, 477 10^46	10

La quantité de partitions croît vertigineusement.

Plus de 10⁴⁰ dès le nombre 2 000.

La formule converge très lentement.

Encore 10 pour mille (soit 1%) pour n = 2000.

Formule citée par Nathanson

La quantité de partitions p(n) d'un nombre positif n satisfait la formule asymptotique suivante:

Avec:

= 2,5650996603237281911…

On en déduit que:

Hardy et Ramanujan et aussi Uspensky ont trouvé cette formule indépendamment. Leurs démonstrations font usage des variables complexes et les fonctions modulaires. Plus tard, Erdös trouvera une démonstration plus directe, mais … très ardue. Méthode appliquant une démonstration par induction à une formule récursive.

D'après Elementary Methods in Number Theory - Melvyn B. Nathanson - Springer - 2000

Relation d'Euler

Euler montre l'égalité des deux séries suivantes:

Développement pour n = 5

S(x) = 1 + x + 2x² + 3x³ + 5x⁴ + 7x⁵

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¹³) final indique que le terme suivant sera en puissance 13.

Voir Identité d'Euler avec les nombres premiers / Identités classiques

Suite	Digipartition 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
DicoNombre	Nombre 2, 565…
Cette page	http://villemin.gerard.free.fr/Wwwgvmm/Addition/PttQte.htm