NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 27/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

      

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

>>> Quantité de partitions – Approche

 

Formules

>>> Quantité de compositions

>>> Quantité de partitions – Estimation

>>> Formule citée par Nathanson

>>> Quantité de partitions – Calcul par récurrence

>>> Fondement du théorème – Une approche 

 

>>> Quantité de partitions de 1 à 100

 

 

 

 

 

 

PARTITION - Quantité

 

 

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

Combien ? Formule ?

 

P(n) est la quantité de partitions du nombre entier n

                   Par définition: P(0) = 1  et P(n<0) = 0

 

Historique te point des recherches

Euler s'est intéressé le premier à la partition des nombres, notamment avec sa fonction génératrice.

Savoir ce que devient P(n) pour n grand a beaucoup intrigué les mathématiciens. Hardy, Ramanujan et Rademacher tentèrent de donner des formules d'approximation de P(n).

Encore aujourd'hui, on ne sait pas décider si P(n) est pair ou impair.

Un sujet souvent traité consiste à trouver des identités (bijections) entre sous-ensembles de partitions. Le diagramme de Ferrers s'est avéré un précieux outil.

 

 

 

Quantité de partitions - Approche

On peut compter les partitions ou se référer à une liste établie (Tableau).

 

Voir l'encyclopédie des suites de nombres: A000041 – a(n) = number of partitions of n (the partition numbers).

 

 

Avoir recours à un logiciel de calcul mathématique:

 

Exemple avec Maple et son logiciel spécialisé: combinat (combinatoire). L'instruction numbpart fournit immédiatement la quantité de partitions.

L'instruction seq demande de calculer la même chose pour n de 1 à 30.

Faire une division de polynôme.

 

Conclusions

 

Pas facile de dénombrer les partitions d'un nombre entier ! >>>

 

Par contre, compter les compositions (partitions, y compris les permutations) est assez simple >>>

 

 

 

Quantité totale (toutes les compositions)

 

Dénombrement

Les compostions sont toutes les partitions déclinées avec leurs permutations.

 

La quantité de compositions pour partitionner n est:   2n-1.

Toutes les partitions, permutations comprises.

 

Exemple

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

4 possibilités

(dont le nombre lui-même)

 

Soit: 4 = 23 – 1

 

 

Démonstration

Le nombre à décomposer est écrit sous forme de bâtons: 6 = I I I I I I

Les compositions sont formée en plaçant le signe + ou le signe espace entre les "I" de toutes les façons possibles: I I I + I I I représente 3 + 3.

Pour le nombre n, il y a n – 1 intervalles et donc 2n – 1 façons de placer les deux symboles.

 

 

Exemple avec n = 6

Remarquez qu'en plaçant 0 et 1 à la place des deux symboles "plus" et "espace", on retrouve les nombres en binaire.

 

Compositions du nombre 6

 

 

D(6) = 25

 

 

 

Quantité de PARTITIONS propres – Estimation

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, permutations exclues.

Vers 1918, Ramanujan et Hardy trouvent 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 ?

 

La quantité de partitions croît vertigineusement.

Plus de 1040 dès le nombre 2 000.

La formule converge très lentement.

Encore 10 pour 1000 (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

 

 

Quantité de partitions – Calcul par récurrence

Théorème des nombres pentagonaux (Euler)

Pentagonaux généralisés

 

Les  nombres pentagonaux généralisés

 

Les premiers de la liste: 0, 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, …

 

Polynôme générateur

 

Relation entre puissances successives et puissance en pentagonaux généralisés (PG)

 

Ces nombres se trouvent impliqués ici, via leur polynôme générateur.

 

 

 

On retrouve les nombres pentagonaux généralisés en exposant.

Voir Développements de cette expression

 

Théorème des nombres pentagonaux

(Euler)

 

Cette expression se trouve liée aux partitions des nombres par:

 

Calcul des quantités de partitions par récurrence

 

Note: P0 = 1

 

L'établissement de cette somme à partir de la relation précédente n'est pas évidente. Une approche est proposée ci-dessous. Plus d'explications sur les sites en rérérence.

 

Exemples de calcul d'une partition à partir des précédentes.

 

Anglais  Euler's Pentagonal Number Theorem

 

 

Fondement du théorème – Une approche 

 

Parmi les vingt-deux  partitions du nombre 8, seules six sont formées de nombres distincts:
8, 8 + 1, 7 + 2, 5 + 3, 4 + 2 + 1 et 5 + 2 + 1

 

Leur diagramme de Ferrers  montre qu'il a autant de partions avec une quantité paire de termes qu'impaire (notées P et I).

Il est intéressant de noter que les couples se forment en considérant un échange entre les carrés jaunes: carrés en bout droit (en fait, la diagonale droite lorsqu'elle existe) contre les carrés de la base.

 

Six partitions distinctes du nombre 8

Parmi les quinze partitions du nombre 7, seules cinq sont formées de nombres distincts:
7, 6 + 1, 5 + 2, 4 + 3 et 4 + 2 + 1

 

Leur diagramme de Ferrers  montre que (impair oblige), les quantités P et I sont différentes

Deux couples sont formés. Pour la partition restante (4 + 3), l'inversion de la diagonale droite contre la base conduit à une partition (3 + 2 + 2) qui n'est plus en nombres distincts.

 

 

Cinq partitions distinctes du nombre 7

 

Propriété

Il se trouve que les nombres avec partitions distinctes non équilibrées (paires/impaires) sont les nombres pentagonaux généralisés, comme l'avait découvert Euler.

 

Question

Comment interviennent ces partitions disctinctes dans le calcul de l'expression E (vue ci-dessus) ?

 

Développement  de l'expression E

Voyons la contribution au coefficient de x5

Comparons aux trois partitions distinctes de 5:

*      1            Type I (impair)

*      1 + 4     Type P

*      2 + 3     Type P

Bilan: un impair et deux pairs

Avec ce nombre pentagonal, le bilan est déséquilibré.

 

 

(1 – x) (1 – x2) (1 – x3) (1 – x4) (1 – x5)…

*    (   1)  (–x5) =   x5

*    ( –x)  (–x4) = –x5

*    (–x2)  (–x3) = –x5

Bilan pour x5

*      (2)  (x5) – (1)  (x5) = x5

 

 

Et avec x56

Comparons aux quatre partitions distinctes de x6:

*      6              Type I

*      1 + 5       Type P

*      2 + 4       Type P

*      1 + 2 + 3 Type I

Bilan: autant de pairs que d'impairs

Avec ce nombre pentagonal, le bilan est équilibré.

 

Moralité: tous les x avec une puissance disparaissent de E, sauf pour celles égale à un pentagonal.

 

 

(1 – x) (1 – x2) (1 – x3) (1 – x4) (1 – x5) (1 – x6) …

*    (   1)  (–x6) = –x6

*    ( –x)  (–x5) = +x6

*    (–x2)  (–x4) = +x6

*    (–x3)  (–x2)  (–x) = –x6

Bilan pour x5

*      (2)  (x6) – (1)  (x6) = 0

 

 

Théorème des partitions distinctes

Quantité de partitions distinctes paires (qP) et impaire (qI).

Propriété énoncée par Legendre (1752-1833)

 

 

 

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 TablesIndex

 

 

 

Retour

*    Formules de récurrence

Suite

*    Fonction génératrice

*    Partitions sous contrainte (quantité de sommants)

*    Relation d'Euler – Fonction génératrice

Voir

*    Addition - Glossaire

*    Addition des carrés

*    Addition des entiers

*    Addition des puissances

*    Carrés magiques

*    Conjecture de Goldbach

*    Digipartition

*    Multi-somme de puissances

*    S'y retrouver

*    Totient d'Euler

DicoNombre

*    Nombre 2, 565…

Sites

*    Voir la liste >>>

*      Théorème des nombres pentagonaux – Wikipédia

*    Euler’s Pentagonal Number Theorem – Dan Cranston

*    The Pentagonal Number Theorem and All That – Dick Koch

*    Euler's Pentagonal Number Theorem** – George E. Andrews

Cette page

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