- Fonction partage d'un entier
-
Fonction partage d'un entier
En théorie des nombres, la fonction partage d'un entier, notée p(n), est une fonction qui, pour n entier, donne le nombre de toutes les façons possibles de partager l'entier naturel n, en entiers supérieurs ou égaux à 1, autrement dit le nombre de façons distinctes (ne dépendant pas de l'ordre des termes) de représenter n comme une somme d'entiers naturels. Elle n'est pas une fonction multiplicative.
Signalons que certains l'appellent « fonction de partition d'un entier » : il s'agit d'un anglicisme.
Sommaire
Calculs
La valeur de la fonction est facile à calculer. Une façon de faire est de définir une fonction intermédiaire, notons-la pk, qui à un entier n fait correspondre le nombre de façons d'écrire cet entier sous forme de sommes d'exactement k termes; c'est aussi le nombre de partages de n en sommes ayant un plus grand terme égal à k.
Nous pouvons représenter un partage d'un entier n en exactement k entiers, par une k-liste décroissante . Nous comptons les partages avec la fonction pk en partitionnant l'ensemble des partages de l'entier n en k entiers, en deux sous-ensembles :
1. l'un formé des partages de n en exactement k entiers, tels que le kème entier soit égal à 1,
2.l'autre formé des partages en exactement k entiers dont le dernier est strictement supérieur à 1.
Il y a autant de partages dans le premier ensemble que de (k-1)-listes telles que , c'est-à-dire autant que de partages de l'entier n-1 en exactement k-1 entiers, soit pk-1(n-1),
Il y a autant de partages dans le second ensemble que de k-uplets décroissants tels que , soit puisque tous les entiers sont strictement supérieurs à 1, autant que k-uplets de la forme tels que et donc autant que de partages de l'entier n-k en k entiers soit pk(n-k). Puisque les deux ensembles sont disjoints, le nombre de partages de l'entier n en somme de k entiers est égal à pk-1(n-1)+pk(n-k). D'où la relation :
- pk(n)=pk-1(n-1)+pk(n-k)
Ce que nous pouvons écrire :
- p(k,n)=p(k-1,n-1)+p(k,n-k)
Les conditions initiales de cette fonction p récursive sont les suivantes :
- p(k,n) = 0 si k > n
- p(k,n) = 1 si k = n
Donnons les exemples de calcul pour n de 1 à 8 :
n k pk(n) écritures n k pk(n) écritures 1 1 1 1="1" 6 1 1 6="6" 6 2 3 6="5"+1="4"+2="3"+3 2 1 1 2="2" 6 3 3 6="4"+1+1="3"+2+1="2"+2+2 2 2 1 2="1"+1 6 4 2 6="3"+1+1+1="2"+2+1+1 6 5 1 6="2"+1+1+1+1 3 1 1 3="3" 6 6 1 6="1"+1+1+1+1+1 3 2 1 3="2"+1 3 3 1 3="1"+1+1 7 1 1 7="7" 7 2 3 7="6"+1="5"+2="4"+3 4 1 1 4="4" 7 3 4 7="5"+1+1="4"+2+1="3"+3+1="3"+2+2 4 2 2 4="3"+1="2"+2 7 4 3 7="4"+1+1+1="3"+2+1+1="2"+2+2+1 4 3 1 4="2"+1+1 7 5 2 7="3"+1+1+1+1="2"+2+1+1+1 4 4 1 4="1"+1+1+1 7 6 1 7="2"+1+1+1+1+1 7 7 1 7="1"+1+1+1+1+1+1 5 1 1 5="5" 5 2 2 5="4"+1="3"+2 8 1 1 8="8" 5 3 2 5="3"+1+1="2"+2+1 8 2 4 8="7"+1="6"+2="5"+3="4"+4 5 4 1 5="2"+1+1+1 8 3 5 8="6"+1+1="5"+2+1="4"+3+1="4"+2+2="3"+3+2 5 5 1 5="1"+1+1+1+1 8 4 5 8="5"+1+1+1="4"+2+1+1="3"+3+1+1="3"+2+2+1="2"+2+2+2 8 5 3 8="4"+1+1+1+1="3"+2+1+1+1="2"+2+2+1+1 8 6 2 8="3"+1+1+1+1+1="2"+2+1+1+1+1 8 7 1 8="2"+1+1+1+1+1+1 8 8 1 8="1"+1+1+1+1+1+1+1 etc.
Pour obtenir p(n), il suffit ensuite de calculer la somme :
Dans notre exemple, les valeurs de p(1) à p(8) sont donc :
- p(1) = 1
- p(2) = 1 + 1 = 2
- p(3) = 1 + 1 + 1 = 3
- p(4) = 1 + 2 + 1 + 1 = 5
- p(5) = 1 + 2 + 2 + 1 + 1 = 7
- p(6) = 1 + 3 + 3 + 2 + 1 + 1 = 11
- p(7) = 1 + 3 + 4 + 3 + 2 + 1 + 1 = 15
- p(8) = 1 + 4 + 5 + 5 + 3 + 2 + 1 + 1 = 22
Les valeurs suivantes de p(n) sont :
- p(9) = 30
- p(10) = 42
- p(50) = 204226
- p(100) = 190569292
- p(200) = 3972999029388
- p(1000) = 24061467864032622473692149727991
Il a été démontré que si n se termine par 4 ou 9, alors p(n) est divisible par 5.
Méthode plus rapide
Il existe une autre méthode de calcul du nombre de partitions d'un entier qui se base sur le Théorème du nombre pentagonal d'Euler. Celui-ci donne une relation amusante qui lie p(n) aux p(i) pour i < = n.
Cette relation est :
p(n) = p(n − 1) + p(n − 2) − p(n − 5) − p(n − 7) + p(n − 12) + p(n − 15)... où les termes de cette somme sont
lorsque cette expression a un sens, avec k entier relatif. Les nombres sont les nombres pentagonaux généralisés.
Estimation asymptotique
Hardy et Ramanujan ont présenté en 1918 une fonction approximative de p(n) ; à savoir :
quand
La correction très énigmatique , inventée par Ramanujan, fait que p(200) est exact !
Plus tard, ils obtinrent une égalité stricte pour calculer p(n).
Série de Rademacher
En affinant la méthode employée par Hardy et Ramanujan, Rademacher démontra en 1937 la formule suivante:
avec et s(h,k) la somme de Dedekind. Le démonstration de cette formule fait intervenir les suites de Farey, les cercles de Ford, et l'analyse complexe.
Articles connexes
Références
- Tom Apostol, Modular Functions and Dirichlet Series in Number Theory, Springer
- Portail des mathématiques
Catégorie : Fonction arithmétique
Wikimedia Foundation. 2010.