|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
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. |
|
|
|||
|
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 >>> |
||
|
|
|||
|
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 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. |
|
|
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 |
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Voir Tables – Index
|
Retour |
|
|
Suite |
|
|
Voir |
|
|
DicoNombre |
|
|
Sites |
|
|
Cette page |
