Voir la source de Partition d'un entier

{{Confusion|texte=En particulier en mathématiques, ne pas confondre avec la notion de [[Glossaire topologique#P|partition de l'unité]] ni celle de [[partition (mathématiques)|partition d'un ensemble]], ni celle de [[Composition (combinatoire)|composition d'entier]].}}
{{Exemple flottant|align=left|contenu='' ''
* 5
* 4+1
* 3+2
* 3+1+1
* 2+2+1
* 2+1+1+1
* 1+1+1+1+1
|légende = Les sept partitions de l'entier [[5 (nombre)|5]].}}
En [[mathématiques]], une '''partition d'un entier''' (parfois aussi appelée '''partage d'un entier'''<ref>Voir par exemple l'article de G. Th. Guilbaud, [http://archive.numdam.org/ARCHIVE/MSH/MSH_1966__17_/MSH_1966__17__13_0/MSH_1966__17__13_0.pdf ''Pour le deux cent cinquantième anniversaire de la mort de G. W. Leibniz''], Mathématiques et sciences humaines, tome 17 (1966).</ref>{{,}}<ref>{{Article|auteur1=Édouard Thomas|titre=Les partages d'entiers|périodique=Hors Série Bibliothèque Tangente|numéro=33|date=2019|pages=100-103}}</ref>) est une décomposition de cet [[entier naturel|entier]] en une [[somme (arithmétique)|somme]] d'entiers [[strict]]ement positifs (appelés ''parties'' ou ''sommants''), à l'[[relation d'ordre|ordre]] près des termes (à la différence du problème de [[Composition (combinatoire)|composition]] tenant compte de l'ordre des termes). Une telle partition est en général représentée par la [[suite (mathématiques)|suite]] des termes de la somme, rangés par ordre décroissant. Elle est visualisée à l'aide de son '''diagramme de Ferrers'''<ref>{{MathWorld|nom_url=FerrersDiagram|titre=Ferrers Diagram}}.</ref>, qui met en évidence la notion de partition duale ou conjuguée.

Pour un entier naturel fixé, l'[[ensemble]] de ses partitions est [[ensemble fini|fini]] et muni d'un [[ordre lexicographique]].

La suite du nombre de partitions des entiers naturels successifs est déterminée par un [[Algorithme récursif#Un autre exemple : le nombre de partitions d'un entier naturel en au plus q parties|algorithme récursif]]. [[Godfrey Harold Hardy|Hardy]] et [[Srinivasa Ramanujan|Ramanujan]] en ont donné un [[développement asymptotique]] en 1918, puis [[Hans Rademacher]] en a donné une formule exacte en 1937. Elle est répertoriée comme {{OEIS|A000041}}.
[[Fichier:Ferrer partitioning diagrams.svg|vignette|droite|Diagrammes de Ferrers des partitions des entiers jusqu'à 8.]]

== Présentation ==
=== À l'aide des diagrammes de Ferrers ===
{|class="wikitable right"
|-
|
{|border ="0" cellspacing = "0" style="width:7em;font-size:smaller;"
 |-
 |4→||O||O||O||O
 |-
 |4→||O||O||O||O
 |-
 |3→||O||O||O|| 
 |-
 |1→||O|| || || 
 |-
 |1→||O|| || ||
 |}
|-
|Diagramme de Ferrers<br /> de la partition (4, 4, 3, 1, 1)<br /> du nombre 13.
|}
Un diagramme de Ferrers<ref>Nommé ainsi d'après le mathématicien britannique [[Norman Macleod Ferrers]].</ref> est constitué d'un ensemble de points disposés aux sommets d'un [[quadrillage]] sur lequel sont spécifiées une première ligne et une première colonne [[orientation (mathématiques)|orientées]]. La seule condition exigée est que tout point du quadrillage précédant un point du diagramme, sur une même ligne ou une même colonne, doit aussi appartenir au diagramme.

Une partition d'un entier <math>n</math> peut alors être conçue comme un diagramme de Ferrers avec <math>n</math> points, chaque ligne du diagramme représentant une ''partie'' par son [[cardinal d'un ensemble fini|cardinal]]. En particulier, le diagramme de Ferrers [[ensemble vide|vide]] représente l'unique partition de l'entier [[zéro|0]].

Ces diagrammes sont généralisés en [[combinatoire]] par les [[tableau de Young|tableaux de Young]].

=== Définitions formelles ===
Il existe plusieurs manières équivalentes de définir formellement une partition d'un entier naturel.

* Par exemple à l'aide d'une suite finie d'entiers strictement positifs<ref>Il est possible aussi de considérer des suites infinies d'entiers positifs ou nuls, dont seulement un nombre fini de termes seront non nuls.</ref>. Comme les [[permutation]]s des termes ne modifient pas la partition, la suite est par défaut présentée dans un ordre fixe, en général décroissant. Par exemple, (2,1,1) est une telle partition du nombre 4.  Le choix arbitraire de cet ordre peut être évacué en utilisant une [[relation d'équivalence]] sur l'ensemble des suites finies par permutation des termes. Une partition est alors définie comme une classe d'équivalence de suites.
* Il est aussi possible de caractériser chaque partition à l'aide d'une [[mesure (mathématiques)|mesure]] indiquant pour chaque entier strictement positif le nombre de termes de cette valeur, ce qui revient à considérer une partition comme un [[multiensemble]]. La partition précédente s'écrirait ici <math>\{\{2,1,1\}\}</math>.
* Une autre approche, qui fait le lien avec les [[partition (mathématiques)|partitions d'ensemble]], consiste à définir une partition de <math>n</math> comme une [[action de groupe (mathématiques)|orbite]] de l'ensemble des partitions de l'intervalle d'entiers {{math|{1, ..., ''n''}<nowiki/>}} sous l'[[action de groupe (mathématiques)|action]] du [[groupe symétrique]]. Dans l'exemple précédent, la partition (d'entier) serait formée de la partition (d'ensemble) <nowiki>{{1,2},{3},{4}}</nowiki> et des partitions obtenues par permutation des nombres 1,2,3,4.

== Relations ==
=== Relation d'ordre ===
L'ensemble des partitions de <math>n</math> est muni d'un [[ordre lexicographique]], c'est-à-dire que si deux partitions sont représentées par des suites décroissantes qui coïncident jusqu'au rang <math>k</math> exclu, alors celle qui a un plus grand terme au rang <math>k</math> est supérieure à l'autre, quels que soient leur nombre de termes et leurs valeurs ensuite.

La partition composée du seul terme <math>n</math> est donc supérieure à toutes les autres partitions de <math>n</math>, tandis que la plus petite est celle qui est composée de <math>n</math> termes qui valent tous 1.

Cet ordre est [[ordre total|total]], c'est-à-dire que toutes les partitions d'un même entier peuvent être comparées entre elles.

=== Dualité ===
{|class="wikitable right"
|-
|
{|border ="0" cellspacing = "0" style="width:7em;font-size:smaller;"
 |-
 |O||O||O||O||O
 |-
 |O||O||O|| ||
 |-
 |O||O||O|| ||
 |-
 |O||O|| || ||
 |}
|-
|Diagramme de Ferrers<br /> de la partition (5 ; 3 ; 3 ; 2)<br /> duale de la partition (4 ; 4 ; 3 ; 1 ; 1).
|}

Le fait de lire en colonnes un diagramme de Ferrers tracé en lignes, ou réciproquement, permet de définir la partition ''conjuguée<ref>{{Harvsp|Hardy|Wright|2007|p=354}} ; {{Harvsp|Apostol|1976|p=307}}.</ref>'' (ou {{refsou|date=27/9/16|''duale''}}). Géométriquement, cela revient à effectuer une [[symétrie axiale|symétrie]] par rapport à la diagonale. En particulier, cela implique que cette dualité est [[involution (mathématiques)|involutive]] : toute partition est duale de sa partition duale.

Formellement, si une partition est représentée par une suite finie <math>\lambda = (\lambda_i)</math>, la partition duale est définie par la suite <math>\lambda^*</math> où <math>\lambda^*_k</math> est le nombre de termes de <math>\lambda</math> supérieurs ou égaux à <math>k</math>. Si la suite <math>\lambda</math> est décroissante au sens large, le nombre d'éléments de <math>\lambda^*</math> égaux à <math>i</math> est <math>\lambda_i-\lambda_{i+1}</math> (ou <math>\lambda_i</math> si <math>\lambda_i</math> est le dernier terme de la suite <math>\lambda</math>).

La dualité permet de mettre en évidence une bijection entre l'ensemble des partitions en exactement <math>k</math> parties et l'ensemble des partitions dont la première partie (la plus grande) est <math>k</math>. Cette propriété est à la base d'une formule récursive permettant de dénombrer les partitions d'un entier {{infra|Dénombrement}}.

=== Partition autoduale ===
{|class="wikitable right"
|-
|
{|border ="0" cellspacing = "0" style="width:7em;font-size:smaller;"
 |-
 |O||O||O||O||O
 |-
 |O|| || || ||
 |-
 |O|| || || ||
 |-
 |O|| || || ||
 |-
 |O|| || ||
 |}
|
{|border ="0" cellspacing = "0" style="width:7em;font-size:smaller;"
 |-
 |O||O||O||O||O
 |-
 |O||O||O||||
 |-
 |O||O||O|| ||
 |-
 |O|||| || ||
 |-
 |O|| || || ||
 |}
|
{|border ="0" cellspacing = "0" style="width:7em;font-size:smaller;"
 |-
 |O||O||O||O||O
 |-
 |O||O||O||O||O
 |-
 |O||O||O||O||O
 |-
 |O||O||O||O||O
 |-
 |O||O||O||O||O
 |}
|-
|colspan="3"|Diagrammes de Ferrers<br/>de quelques partitions autoduales.
|}
Une partition qui est égale à sa partition duale est dite ''autoduale'' ou ''autoconjuguée''. Un exemple simple de partition autoduale est donné par un diagramme en « L », définis pour tout entier impair de la forme <math>2k+1</math>, avec une première partie valant <math>k+1</math> et toutes les autres valant 1. D'autres exemples sont donnés pour les [[nombre carré|carrés]] et les [[nombre triangulaire|nombres triangulaires]].
{{clr}}
{|class="wikitable right"
|-
|
{|border ="0" cellspacing = "0" style="width:7em;font-size:smaller;"
 |-
 |O||O||O||O||O
 |-
 |O||T||T||T||T 
 |-
 |O||T||X||X|| 
 |-
 |O||T||X|| || 
 |-
 |O||T|| || ||
 |}
|
{|border ="0" cellspacing = "0" style="width:7em;font-size:smaller;"
 |-
 |O||O||O||O||O||O||O||O||O
|-
 |T||T||T||T||T||T||T|| || 
|-
 |X||X||X|| || || || || || 
 |}
|-
| colspan="2"|Correspondance entre partition autoduale<br /> et partition à parties impaires distinctes.
|}


La représentation par les diagrammes de Ferrers permet de [[preuve sans mots|prouver]] que l'ensemble des partitions autoduales est en [[bijection]] avec l'ensemble des partitions à parties [[nombre impair|impaires]] distinctes. En effet, le diagramme de chaque partition autoduale peut être décomposé en une suite de diagrammes en « L » de taille strictement décroissante mais toujours impaire. Réciproquement, les parties impaires d'une partition (à parties distinctes) peuvent être associées à des diagrammes en « L », dont la juxtaposition dans l'ordre décroissant forme le diagramme de Ferrers d'une partition autoduale.

=== Injections ===
Les diagrammes de Ferrers permettent de visualiser certaines relations entre les ensembles de partitions d'entiers. Notamment, l'adjonction d'une partie valant 1 induit une [[injection (mathématiques)|injection]] de l'ensemble des partitions d'un entier dans l'ensemble des partitions de l'entier suivant. Un autre exemple est donné par l'[[incrémentation]] de toutes les parties, qui induit une injection de l'ensemble des partitions d'un entier <math>n</math> en <math>k</math> parties, dans l'ensemble des partitions de <math>(n+k)</math> en <math>k</math> parties.

== Ensemble des partitions d'un entier ==
=== Finitude ===
Pour chaque partition de <math>n</math>, définie par la suite de ses termes dans l'ordre décroissant, la [[série (mathématiques)|série]] associée (qui la caractérise) est strictement croissante, à valeurs entières strictement positives et de dernier terme <math>n</math>. Chaque partition peut donc être représentée par l'ensemble des valeurs de cette série. L'ensemble des partitions de <math>n</math> s'injecte donc dans l'[[ensemble des parties]] de l'intervalle d'entiers {{math|{1, ..., ''n''}<nowiki/>}}, de [[cardinal d'un ensemble fini|cardinal]] <math>2^n</math>.

En pratique, la valeur <math>n</math> étant toujours atteinte par la série, il est possible de ne considérer que l'ensemble des valeurs de la série qui soient strictement inférieures à <math>n</math>, ce qui divise par deux la majoration du cardinal de l'ensemble des partitions.

=== Algorithme de construction ===
La liste de toutes les partitions de <math>n</math> dans l'ordre décroissant est donnée par un [[algorithme]] itératif. Si une partition est représentée par une suite finie décroissante <math>(a_i)</math> dont au moins un terme est strictement supérieur à 1, la partition suivante <math>(b_i)</math> est construite comme suit :
:On note <math>k</math> le rang du dernier terme strictement supérieur à 1 et <math>N</math> le nombre de termes qui valent 1 dans <math>(a_i)</math>.
:Pour tout <math>j<k</math>, on définit <math>b_j = a_j</math>.
:On définit <math>b_k = a_k-1</math>.
:En notant <math>N+1 = b_k q + r</math> la [[division euclidienne]] de <math>N+1</math> par <math>b_k</math>, on définit les termes <math>b_j</math> pour <math>k < j < k+q+1</math> par <math>b_j = b_k</math>.
:Si <math>r</math> est non nul, on définit un dernier terme <math>b_{k+q+1} = r</math>.

=== Dénombrement ===
Le nombre de partitions de l'entier <math>n</math> est classiquement noté <math>p(n)</math>. Il est nul si <math>n<0</math>, mais <math>p(0)=1</math>, puisque 0 possède exactement une partition : la [[somme vide]]. Pour de petites valeurs de <math>n</math>, <math>p(n)</math> peut être obtenu en décomptant les partitions produites par l'algorithme ci-dessus, mais il peut aussi être calculé à l'aide de méthodes plus calculatoires.

==== Par une fonction récursive ====
En notant, pour ''n'' et ''k'' entiers strictement positifs, ''p''(''n'',''k'') le nombre de partitions de ''n'' en ''k'' parties, la fonction ''p'' est [[algorithme récursif|récursive]] et vérifie
* la relation suivante pour tous ''n'' > ''k'' > 1 :
:''p''(''n'', ''k'') = ''p''(''n'' – 1, ''k'' – 1) + ''p''(''n – k'', ''k'') ;
* les conditions initiales :
** ''p''(''n'', ''k'') = 0 si ''n'' < ''k'' ,
** ''p''(''n'', ''n'') = ''p''(''n'', 1) = 1.
La relation provient d'une disjonction de cas parmi ces partitions :
* soit la dernière partie (la plus petite) vaut 1, auquel cas la partition est obtenue à partir d'une partition de ''n'' – 1 en ''k'' – 1 parties, par adjonction de cette dernière partie ;
* soit toutes les parties valent au moins 2, auquel cas la partition est obtenue à partir d'une partition de ''n – k'' en ''k'' parties, par augmentation de chaque partie d'une unité.

À condition de faire de la [[mémoïsation]], ce procédé permet de calculer le nombre de partitions d'un entier avec une [[Théorie de la complexité (informatique théorique)|complexité algorithmique]] quadratique en fonction de ''n'', en additionnant toutes les valeurs de ''p''(''n'', ''k'') lorsque ''k'' varie entre 1 et ''n''.

{| class="wikitable centre" style="width:40%;text-align:center"
|+ Premières valeurs de la fonction récursive et nombre de partitions des premiers entiers.
| ''p''(''n'',''k'')
| colspan=8 | ''k''
| rowspan=2 scope="col" | Total
|- bgcolor="#cbe2fc"
| scope="col" bgcolor="#ffffff" | ''n'' || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8
|-
| scope="row" bgcolor="#cbe2fc" | 1 || 1
| colspan=7 |
| 1
|-
| scope="row" bgcolor="#cbe2fc" | 2 || 1 || 1
| colspan=6 |
| 2
|-
| scope="row" bgcolor="#cbe2fc" | 3 || 1 || 1 || 1
| colspan=5 |
| 3
|-
| scope="row" bgcolor="#cbe2fc" | 4 || 1 || 2 || 1 || 1
| colspan=4 |
| 5
|-
| scope="row" bgcolor="#cbe2fc" | 5 || 1 || 2 || 2 || 1 || 1
| colspan=3 |
| 7
|-
| scope="row" bgcolor="#cbe2fc" | 6 || 1 || 3 || 3 || 2 || 1 || 1
| colspan=2 |
| 11
|-
| scope="row" bgcolor="#cbe2fc" | 7 || 1 || 3 || 4 || 3 || 2 || 1 || 1
| colspan=1 |
| 15
|-
| scope="row" bgcolor="#cbe2fc" | 8 || 1 || 4 || 5 || 5 || 3 || 2 || 1 || 1
| 22
|}

==== Relation de récurrence ====
Une méthode de calcul plus efficace du nombre de partitions d'un entier se déduit du [[théorème des nombres pentagonaux]] d'[[Leonhard Euler|Euler]]. Celui-ci donne une [[relation de récurrence]] qui s'écrit :
:<math>p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + p(n-15)+\dots=\sum_{k\ge1}(-1)^{k-1}p\left(n-k(3k\pm1)/2\right)</math>.
Les nombres <math>k(3k\pm1)/2</math> sont les [[Nombre pentagonal|nombres pentagonaux]] généralisés.

== Suite des nombres de partitions ==
=== Propriétés ===
Les techniques des diagrammes de Ferrers permettent aussi de prouver des résultats comme les suivants :
* pour tout entier ''n''<!--même négatif, cf. début du § Dénombrement-->, il y a ''p''(''n'') – ''p''(''n'' – 1) partitions de ''n'' dans lesquelles chaque partie est supérieure ou égale à 2<ref>{{Ouvrage|langue=en|auteur1=R.B.J.T. Allenby|auteur2=Alan Slomson|titre=How to Count|sous-titre=An Introduction to Combinatorics|éditeur=[[CRC Press]]|année=2011|numéro d'édition=2|passage=94|isbn=|lire en ligne={{Google Livres|1oyMQGHqv_0C|page=93}}}}, th. 6.10 ; {{Harvsp|Bóna|2011|p=101}}, th. 5.20.</ref> ;
* pour tout entier ''n'' ≥ 0, ''p''(1) + ''p''(2) + … + ''p''(''n'') < ''p''(2''n'')<ref>{{Harvsp|Allenby|Slomson|2011|p=93}}, th. 6.8.</ref>.

Ramanujan a démontré [[Congruences de Ramanujan|trois congruences]], dont la première est que ''p''(5''n'' + 4) est [[divisible]] par 5. Plus précisément<ref>{{Ouvrage|langue=en|auteur1=Hei-Chi Chan|titre=An Invitation to q-Series : From Jacobi's Triple Product Identity to Ramanujan's “Most Beautiful Identity”|éditeur=[[World Scientific]]|année=2011|passage=147-148|isbn=|lire en ligne={{Google Livres|BUamL5b59oAC|page=147}}}}.</ref> : <math>\sum_{n=0}^\infty p(5n+4)q^n=5\frac{(q^5)_\infty^5}{(q)_\infty^6}</math>, où <math>(\cdot)_\infty</math> est le [[q-symbole de Pochhammer|''q''-symbole de Pochhammer]] : <math>(a)_\infty:=\prod_{k=0}^{\infty}(1-aq^k)</math>.

=== Fonction génératrice associée ===
Euler a remarqué que la [[série formelle]] [[série génératrice|génératrice]] de ''p'',
:<math>S(X)=\sum_{n\in\N}p(n)X^n</math>
est égale au [[produit infini]] suivant<ref>[[Trivial]]ement convergent, cf. {{en}} [[Richard Peter Stanley|R. P. Stanley]], [http://math.mit.edu/~rstan/ec/ec1.pdf ''Enumerative Combinatorics''], prop. 1.1.9.</ref> de [[Série formelle#Propriétés algébriques|séries (formelles) géométriques]] :
:<math>S(X)=\prod_{k\in\N^*}\frac1{1-X^k}=\prod_{k\in\N^*}\sum_{m\in\N}X^{km}.</math>

En effet, dans ce produit, le coefficient du terme de degré <math>n</math> est le nombre de suites <math>(m_k)_{k\in\N^*}</math> d'entiers naturels telles que <math>\sum_{k\in\N^*}k~m_k=n</math>. Ces suites correspondent aux partitions de <math>n</math> définies en termes de mesure {{supra|Définitions formelles}}.

=== Estimation asymptotique ===
La croissance de la suite ''p''(''n'') est très rapide :
:''p''(1) = 1, ''p''(2) = 2, ''p''(3) = 3, ''p''(4) = 5, ''p''(5) = 7, ''p''(6) = 11, ''p''(7) = 15, ''p''(8) = 22, ''p''(9) = 30, ''p''(10) = 42,
:''p''(50) = 204226, ''p''(100) = 190 569 292, ''p''(200) = 3 972 999 029 388<ref>Pour les {{nombre|10000}} premières valeurs, voir la {{OEIS|A000041}}.</ref>.

Introduisant la [[méthode du cercle]] et utilisant la [[Forme modulaire|modularité]] de la [[fonction êta de Dedekind]]<ref>{{Chapitre|lang=en|url=http://www.mast.queensu.ca/~murty/partition.pdf|auteur=M. Ram Murty|titre=The partition function revisited|titre ouvrage=The Legacy of Srinivasa Ramanujan|collection=RMS-Lecture Notes|numéro dans collection=20|année=2013|passage=261-279}}.</ref>, [[Godfrey Harold Hardy|Hardy]] et [[Srinivasa Ramanujan|Ramanujan]] ont présenté en [[1918]]<ref name=HR1918>{{Article|lang=en|auteur=G. H. Hardy|auteur2=S. Ramanujan|titre=Asymptotic formulae in combinatory analysis|revue=Proc. London Math. Soc.|vol=17|numéro=2|année=1918|passage=75-115|url=http://ramanujan.sirinudi.org/Volumes/published/ram36.pdf}}.</ref> l'[[équivalent]] suivant<ref>Un calcul bien plus élémentaire permet de majorer ''p''(''n'') par <math>\left(\pi/\sqrt{6(n-1)}\right)\exp\left(\pi\sqrt{2n/3}\right)</math> : {{Harvsp|Apostol|1976|p=316-318}}, {{Harvsp|van Lint|1974|p=34-36}}.</ref> de ''p''(''n'') :
:<math>p(n) \sim \frac1{4n\sqrt3}\exp\left({\pi\sqrt{\frac{2n}3}}\right)</math>.
Cette formule donne par exemple une erreur de 1,4 % pour ''n'' = {{formatnum:1000}}.

Plus précisément, ils donnèrent le [[développement asymptotique]] suivant :
:<math>p(n)=\frac1{2\sqrt2}\sum_{k=1}^{\infty}\sqrt k\, A_k(n)\,
\frac{\rm d}{{\rm d}n}\exp \left( {\frac{\pi}k
    \sqrt{\frac23\left(n-\frac1{24}\right)}}\,\right)
</math>
avec
:<math>A_k(n) = \sum_{0 \,\le\, m \,<\, k; \; (m,\, k) \,=\, 1}
e^{ \pi i \left[ s(m,\, k) \;-\; \frac1k 2nm \right] }</math>,
où la notation (''m'',&nbsp;''k'')&nbsp;=&nbsp;1 signifie que ''m'' ne doit prendre que les valeurs [[Nombres premiers entre eux|premières avec ''k'']], et où la fonction ''s''(''m'',&nbsp;''k'') est une [[somme de Dedekind]].
La correction énigmatique –1/24, découverte par Ramanujan, fait que ''p''(200) est la partie entière de cette expression en ne prenant que les cinq premiers termes du développement<ref name=HR1918/>.

=== Série de Rademacher ===
En affinant la méthode employée par Hardy et Ramanujan, [[Hans Rademacher]] obtint en 1937 la [[série convergente]] suivante<ref name=And69>{{en}} [[George Andrews (mathématicien)|George Andrews]], ''Number Theory'', W. B. Saunders Company, Philadelphie, 1971. Dover edition, {{p.|69}}.</ref> :

<math>p(n)=\frac1{\pi \sqrt2}\sum_{k=1}^{\infty}{A_k(n)\sqrt k\frac{\rm d}{{\rm d}n}\left( \frac{\sinh \left(\frac{\pi}k\sqrt{\frac23\left(n-\frac1{24}\right)}\right)}{\sqrt{n-\frac1{24}}}\right)}</math>

avec la même valeur de <math>A_k(n)</math> que ci-dessus. La démonstration de cette formule fait intervenir les [[suite de Farey|suites de Farey]], les [[cercle de Ford|cercles de Ford]], et l'[[analyse complexe]].

=== Autres formules de récurrence ===
{{pertinence section|date=novembre 2017}}
On peut obtenir une première relation de récurrence avec la fonction [[somme des diviseurs]] σ<ref>{{Harvsp|Apostol|1976|p=323}}, Example 1.</ref> :
:<math>p(n)=\frac1n\sum_{k=1}^n\sigma(k)p(n-k)</math>.

En notant <math>q(n)</math> le nombre de partitions de <math>n</math> en entiers distincts (égal au nombre de partitions de <math>n</math> en entiers impairs)<ref>{{MathWorld|nom_url=PartitionFunctionQ|titre=Partition Function Q}} et « [[#Liens externes|Partition Function P]] ».</ref> :
:<math>p(n) = \sum_{k = 0}^{\lfloor n/2 \rfloor} q(n-2k)p(k)</math>.

Le nombre <math>p_m(n)</math> de partitions d'un entier <math>n\ge1</math> en entiers supérieurs ou égaux à <math>m</math> (qui vaut donc <math>p(n)</math> si <math>m=1</math> et qui est nul si <math>m>n</math>) vérifie<ref>{{Article|lang=en|auteur=V. V. Kruchinin|titre=The number of partitions of a natural numbers <math>n</math> into parts, each of which is not less than <math>m</math>|revue=[[Mathematical Notes|Math. Notes]]|vol=86|numéro=3-4|année=2009|passage=505-509|doi=10.1134/S0001434609090260|math reviews=2591345}}.</ref> :
:<math>p_m(n)=p_m(n-m)+p_{m+1}(n)</math>,
ainsi que la relation de récurrence
:<math>\forall n\ge m\ge1\quad p_m(n)=1+\sum_{m\le k\le n/2}p_k(n-k)</math>.

== Maximisation du produit ==
Étant donné un entier ''n'' > 1, le produit ''m''{{ind|1}} × … × ''m{{ind|k}}'' d'une partition ''n'' = ''m''{{ind|1}} + … + ''m{{ind|k}}'' est maximum<ref>Pour une approche heuristique et progressive, voir {{Chapitre|lang=en|auteur=Barry V. Kissane|titre=Mathematical Investigation: Description, Rationale, and Example|titre ouvrage=Problem Posing: Reflections and Applications|auteurs ouvrage=Stephen I. Brown et [[Marion Walter]]|éditeur=Psychology Press|année=2013|année première édition=1993|isbn=978-1-31771737-9|url={{Google Livres|LCSZAgAAQBAJ|page=182}}|page=[https://books.google.fr/books?id=0GSYAgAAQBAJ&pg=PA190 {{p.|189-203}}]}} qui fait, en conclusion, apparaître le lien avec le [[e (nombre)|nombre {{math|e}}]].</ref>{{,}}<ref>Voir la {{OEIS|id=A000792}} et ses références et liens.</ref> [[Condition suffisante|si]] tous les ''m{{ind|i}}'' sont égaux à 3, sauf zéro, un ou deux d'entre eux (selon la [[Congruence sur les entiers|classe de ''n'' modulo 3]]) qui valent 2. En effet<ref>{{Lien web|lang=en|auteur=John Scholes|titre=Problem 4|url=http://www.cs.cornell.edu/~asdas/IMO/imo/isoln/isoln764.html}} (18th [[Olympiades internationales de mathématiques|IMO]] 1976) et {{Lien web|titre=Problem A1|url=http://mks.mff.cuni.cz/kalva/putnam/psoln/psol791.html}} (40th [[William Lowell Putnam Mathematical Competition|Putnam]] 1979).</ref> :
* aucun ''m{{ind|i}}'' ne doit être égal à 1 car 1 × ''m'' < ''m'' + 1 ;
* aucun ''m{{ind|i}}'' ne doit être supérieur ou égal à 5 car on aurait 3(''m{{ind|i}}'' – 3) > ''m{{ind|i}}'' (ou encore : 2(''m{{ind|i}}'' – 2) > ''m{{ind|i}}'') ;
* chaque 4 peut être remplacé par deux 2 ;
* il y a au plus deux 2 car 2{{3}} < 3{{2}}.

== Notes et références ==
{{Références|colonnes=1}}

=== Sources ===
* {{Ouvrage|langue=en|auteur1=Miklós Bóna|titre=A walk through combinatorics|sous-titre=an introduction to enumeration and graph theory|lieu=New Jersey|éditeur=[[World Scientific]]|année=2011|numéro d'édition=3|année première édition=2002|pages totales=546|isbn=978-981-4335-23-2|lire en ligne={{Google Livres|TzJ2L9ZmlQUC}}}}{{Commentaire biblio SRL|Contient une introduction élémentaire à la notion de partition d'un entier, incluant les diagrammes de Ferrers.}}
* [[Louis Comtet]], ''Analyse combinatoire, tome I'', [[PUF]], 1970{{Commentaire biblio SRL|Le chapitre II est consacré aux partitions d'entiers.}}
* {{Ouvrage|langue=en|auteur1=[[Tom M. Apostol]]|titre=Modular Functions and Dirichlet Series in Number Theory|éditeur=[[Springer Verlag|Springer]]|année=1990|pages totales=204|isbn=}}

== Voir aussi ==
=== Articles connexes ===
* [[Fonction de Landau]]
* [[Graphe partitionnable]]
* [[Problème de la somme de sous-ensembles]]
* [[q-symbole de Pochhammer|''q''-symbole de Pochhammer]]
*[[Coefficient binomial de Gauss|Coefficients binomiaux de Gauss]]
* [[Nombre de Bell]] qui est le nombre de partitions d'un ensemble à ''n'' éléments ''discernables'', tandis que le nombre de partitions d'un entier correspond au nombre de partitions d'un ensemble à ''n'' éléments ''indiscernables''.
* {{Lien|langue=en|trad=Glaisher's theorem|fr=Théorème de Glaisher}}
* [[Décomposition en produit de facteurs premiers]], correspondant à la décomposition [[Multiplication|multiplicative]] d'un entier qui, elle, est unique via l'utilisation des [[nombre premier|nombres premiers]].
* [[Congruences de Ramanujan]]
*{{Lien|trad=Newman's conjecture|Conjecture de Newman}}
*[[Nombre poli]], ayant une partition en sommants consécutifs
*[[Suite d'Alcuin]]

=== Bibliographie ===
* {{Article|lang=en|auteur=[http://www.maa.org/remembering-henry-l-alder-1922-2002 Henry L. Alder]|titre=Partition Identities — from Euler to the Present|revue=[[The American Mathematical Monthly|Amer. Math. Monthly]]|vol=76|année=1969|passage=733-746|url=https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/HLAlder.pdf}}{{Commentaire biblio SRL|[[Prix Lester Randolph Ford]] 1970.}}
* {{Ouvrage|langue=en|auteur1=[[George Andrews (mathématicien)|George E. Andrews]]|titre=The Theory of Partitions|éditeur=[[Cambridge University Press|CUP]]|année=1998|année première édition=1976|isbn=|lire en ligne={{Google Livres|Sp7z9sK7RNkC}}}}
* {{Ouvrage|langue=en|auteur1=Tom M. Apostol|titre=Introduction to Analytic Number Theory|éditeur=Springer|année=1976|passage=304-328|isbn=|doi=10.1007/978-1-4757-5579-4|numéro chapitre=14}}
* {{Ouvrage|langue originale=en|auteur1=[[Godfrey Harold Hardy|G. H. Hardy]]|auteur2=[[Edward Maitland Wright|E. M. Wright]]|traducteur=F. Sauvageot|titre=Introduction à la théorie des nombres|titre original=[[Modèle:HardyWright|An Introduction to the Theory of Numbers]]|éditeur=[[Vuibert]]-Springer|année=2007|passage=353-382|isbn=|numéro chapitre=19}}
* {{Article|lang=en|auteur={{Lien|langue=en|fr=Igor Pak}}|titre=Partition bijections, a survey|revue=The Ramanujan Journal|vol=12|numéro=1|année=2006|passage=5-75|url=http://www.math.ucla.edu/~pak/papers/psurvey.pdf}}
* {{Ouvrage|langue=en|auteur1=[[Jacobus van Lint]]|titre=Combinatorial Theory Seminar [[Université technique d'Eindhoven|Eindhoven University of Technology]]|éditeur=Spinger Verlag|collection=Lecture Notes in Mathematics|numéro dans collection=382|année=1974|passage=33-39|isbn=|doi=10.1007/BFb0057323|chapitre=4|titre chapitre=Partitions}}

=== Liens externes ===
* {{Lien web|lang=en|url=http://www.numericana.com/answer/numbers.htm#partitions|titre=Partition Function|site=numericana.com}}
* {{mathWorld|nom_url=PartitionFunctionP|titre=Partition Function P}}
* {{Lien web|lang=en|url=http://www.se16.info/js/partitions.htm|titre=Partition and composition calculator|auteur=H. Bottomley|site=Henry Bottomley's Java and JavaScript examples}}

{{Portail|mathématiques}}

[[Catégorie:Arithmétique]]
[[Catégorie:Combinatoire|Partition]]