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.

Calculs

La valeur de la fonction est facile à calculer. Une façon de faire est de définir une fonction intermédiaire, notons-la p_k, 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 $\left(n_1, n_2, \cdots, n_k\right)$. Nous comptons les partages avec la fonction p_k 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 $\left(n_1, \cdots, n_{k-1}\right)$ telles que $n_1+\cdots+n_{k-1}=n-1$, c'est-à-dire autant que de partages de l'entier n-1 en exactement k-1 entiers, soit p_k-1(n-1),

Il y a autant de partages dans le second ensemble que de k-uplets décroissants $\left(n_1, n_2, \cdots, n_k\right)$ tels que $n_1+\cdots+n_{k}=n$, soit puisque tous les entiers sont strictement supérieurs à 1, autant que k-uplets de la forme $\left(n_1-1, n_2-1, \cdots, n_k-1\right)$ tels que $(n_1-1)+\cdots+(n_{k}-1)=n-k$ et donc autant que de partages de l'entier n-k en k entiers soit p_k(n-k). Puisque les deux ensembles sont disjoints, le nombre de partages de l'entier n en somme de k entiers est égal à p_k-1(n-1)+p_k(n-k). D'où la relation :

p_k(n)=p_k-1(n-1)+p_k(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 :

$p(n)=\sum_{k=1}^n p_{k}(n)$

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

$(-1)^{(k+1)} p(n-{k(3k-1) \over 2 })$ lorsque cette expression a un sens, avec k entier relatif. Les nombres $k(3k-1)\over 2$ 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 :

$p(n) \sim A_n e^{\pi \sqrt{\frac{2}{3}(n-\frac{1}{24})}}\ ,$

quand

$A_n = \frac{1}{2n\sqrt{2}}\left(\frac{\pi}{\sqrt{6(\frac{n-1}{24})}}-\frac{1}{2(\frac{n-1}{24})^\frac{3}{2}}\right)$

La correction très énigmatique $\left(-\frac{1}{24}\right)$, 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:

$p(n) = \frac{1}{\pi \sqrt{2}} \sum_{k=1}^{\infty}{A_k(n)\sqrt{k} \frac{d}{dn}\left( \frac{\sinh \left( \frac{\pi}{k} \sqrt{\frac{2}{3} \left( n-\frac{1}{24}\right)}\right)}{\sqrt{n-\frac{1}{24}}}\right)}$

avec $A_k(n) = \sum_{0 \leq h \leq k, (h,k)=1}{e^{\pi i\; s(h,k) - 2 \pi i n h/k}}$ 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

• Partition d'un entier

Références

• Tom Apostol, Modular Functions and Dirichlet Series in Number Theory, Springer

Ce document provient de « Fonction partage d%27un entier ».