Partition d'un entier

En mathématiques, une partition d'un entier (parfois aussi appelée partage d'un entier) est une décomposition de cet entier en une somme d'entiers strictement positifs (appelés parties ou sommants), à l'ordre près des termes (à la différence du problème de composition tenant compte de l'ordre des termes). Une telle partition est en général représentée par la suite des termes de la somme, rangés par ordre décroissant. Elle est visualisée à l'aide de son diagramme de Ferrers, qui met en évidence la notion de partition duale ou conjuguée.

• 5
• 4+1
• 3+2
• 3+1+1
• 2+2+1
• 2+1+1+1
• 1+1+1+1+1

Les sept partitions de l'entier 5.

Pour un entier naturel fixé, l'ensemble de ses partitions est 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. Hardy et 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 suite A000041 de l'OEIS.

Diagrammes de Ferrers des partitions des entiers jusqu'à 8.

Présentation

À l'aide des diagrammes de Ferrers

4→ O O O O 4→ O O O O 3→ O O O 1→ O 1→ O

Diagramme de Ferrers de la partition (4, 4, 3, 1, 1) du nombre 13.

Un diagramme de Ferrers 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 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 $n$ peut alors être conçue comme un diagramme de Ferrers avec $n$ points, chaque ligne du diagramme représentant une partie par son cardinal. En particulier, le diagramme de Ferrers vide représente l'unique partition de l'entier 0.

Ces diagrammes sont généralisés en combinatoire par les 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. Comme les permutations 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 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 $\{\{2,1,1\}\}$.
• Une autre approche, qui fait le lien avec les partitions d'ensemble, consiste à définir une partition de $n$ comme une orbite de l'ensemble des partitions de l'intervalle d'entiers {1, ..., n} sous l'action du groupe symétrique. Dans l'exemple précédent, la partition (d'entier) serait formée de la partition (d'ensemble) {{1,2},{3},{4}} et des partitions obtenues par permutation des nombres 1,2,3,4.

Relations

Relation d'ordre

L'ensemble des partitions de $n$ 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 $k$ exclu, alors celle qui a un plus grand terme au rang $k$ est supérieure à l'autre, quels que soient leur nombre de termes et leurs valeurs ensuite.

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

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

Dualité

O O O O O O O O O O O O O

Diagramme de Ferrers de la partition (5 ; 3 ; 3 ; 2) 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 (ou duale^{[réf. souhaitée]}). Géométriquement, cela revient à effectuer une symétrie par rapport à la diagonale. En particulier, cela implique que cette dualité est involutive : toute partition est duale de sa partition duale.

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

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

Partition autoduale

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 O O O O O O O O O O O O O O O O O O O O O O O O
Diagrammes de Ferrers 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 $2k+1$, avec une première partie valant $k+1$ et toutes les autres valant 1. D'autres exemples sont donnés pour les carrés et les nombres triangulaires.

O O O O O O T T T T O T X X O T X O T	O O O O O O O O O T T T T T T T X X X
Correspondance entre partition autoduale et partition à parties impaires distinctes.

La représentation par les diagrammes de Ferrers permet de prouver que l'ensemble des partitions autoduales est en bijection avec l'ensemble des partitions à parties 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 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 $n$ en $k$ parties, dans l'ensemble des partitions de $(n+k)$ en $k$ parties.

Ensemble des partitions d'un entier

Finitude

Pour chaque partition de $n$, définie par la suite de ses termes dans l'ordre décroissant, la série associée (qui la caractérise) est strictement croissante, à valeurs entières strictement positives et de dernier terme $n$. Chaque partition peut donc être représentée par l'ensemble des valeurs de cette série. L'ensemble des partitions de $n$ s'injecte donc dans l'ensemble des parties de l'intervalle d'entiers {1, ..., n}, de cardinal $2^{n}$.

En pratique, la valeur $n$ é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 à $n$, ce qui divise par deux la majoration du cardinal de l'ensemble des partitions.

Algorithme de construction

La liste de toutes les partitions de $n$ 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 $(a_{i})$ dont au moins un terme est strictement supérieur à 1, la partition suivante $(b_{i})$ est construite comme suit :

On note $k$ le rang du dernier terme strictement supérieur à 1 et $N$ le nombre de termes qui valent 1 dans $(a_{i})$.

Pour tout $j<k$, on définit $b_{j}=a_{j}$.

On définit $b_{k}=a_{k}-1$.

En notant $N+1=b_{k}q+r$ la division euclidienne de $N+1$ par $b_{k}$, on définit les termes $b_{j}$ pour $k<j<k+q+1$ par $b_{j}=b_{k}$.

Si $r$ est non nul, on définit un dernier terme $b_{k+q+1}=r$.

Dénombrement

Le nombre de partitions de l'entier $n$ est classiquement noté $p(n)$. Il est nul si $n<0$, mais $p(0)=1$, puisque 0 possède exactement une partition : la somme vide. Pour de petites valeurs de $n$, $p(n)$ 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 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 complexité algorithmique quadratique en fonction de n, en additionnant toutes les valeurs de p(n, k) lorsque k varie entre 1 et n.

Premières valeurs de la fonction récursive et nombre de partitions des premiers entiers.

p(n,k)	k								Total
n	1	2	3	4	5	6	7	8
1	1								1
2	1	1							2
3	1	1	1						3
4	1	2	1	1					5
5	1	2	2	1	1				7
6	1	3	3	2	1	1			11
7	1	3	4	3	2	1	1		15
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'Euler. Celui-ci donne une relation de récurrence qui s'écrit :

$p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n-12)+p(n-15)+\dots =\sum _{k\geq 1}(-1)^{k-1}p\left(n-k(3k\pm 1)/2\right)$.

Les nombres $k(3k\pm 1)/2$ sont les 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, il y a p(n) – p(n – 1) partitions de n dans lesquelles chaque partie est supérieure ou égale à 2 ;
• pour tout entier n ≥ 0, p(1) + p(2) + … + p(n) < p(2n).

Ramanujan a démontré trois congruences, dont la première est que p(5n + 4) est divisible par 5. Plus précisément : $\sum _{n=0}^{\infty }p(5n+4)q^{n}=5{\frac {(q^{5})_{\infty }^{5}}{(q)_{\infty }^{6}}}$, où $(\cdot )_{\infty }$ est le q-symbole de Pochhammer : $(a)_{\infty }:=\prod _{k=0}^{\infty }(1-aq^{k})$.

Fonction génératrice associée

Euler a remarqué que la série formelle génératrice de p,

$S(X)=\sum _{n\in \mathbb {N} }p(n)X^{n}$

est égale au produit infini suivant de séries (formelles) géométriques :

$S(X)=\prod _{k\in \mathbb {N} ^{*}}{\frac {1}{1-X^{k}}}=\prod _{k\in \mathbb {N} ^{*}}\sum _{m\in \mathbb {N} }X^{km}.$

En effet, dans ce produit, le coefficient du terme de degré $n$ est le nombre de suites $(m_{k})_{k\in \mathbb {N} ^{*}}$ d'entiers naturels telles que $\sum _{k\in \mathbb {N} ^{*}}k~m_{k}=n$. Ces suites correspondent aux partitions de $n$ définies en termes de mesure (voir supra).

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.

Introduisant la méthode du cercle et utilisant la modularité de la fonction êta de Dedekind, Hardy et Ramanujan ont présenté en 1918 l'équivalent suivant de p(n) :

$p(n)\sim {\frac {1}{4n{\sqrt {3}}}}\exp \left({\pi {\sqrt {\frac {2n}{3}}}}\right)$.

Cette formule donne par exemple une erreur de 1,4 % pour n = 1 000.

Plus précisément, ils donnèrent le développement asymptotique suivant :

$p(n)={\frac {1}{2{\sqrt {2}}}}\sum _{k=1}^{\infty }{\sqrt {k}}\,A_{k}(n)\,{\frac {\rm {d}}{{\rm {d}}n}}\exp \left({{\frac {\pi }{k}}{\sqrt {{\frac {2}{3}}\left(n-{\frac {1}{24}}\right)}}}\,\right)$

avec

$A_{k}(n)=\sum _{0\,\leq \,m\,<\,k;\;(m,\,k)\,=\,1}e^{\pi i\left[s(m,\,k)\;-\;{\frac {1}{k}}2nm\right]}$,

où la notation (m, k) = 1 signifie que m ne doit prendre que les valeurs premières avec k, et où la fonction s(m, 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.

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 :

$p(n)={\frac {1}{\pi {\sqrt {2}}}}\sum _{k=1}^{\infty }{A_{k}(n){\sqrt {k}}{\frac {\rm {d}}{{\rm {d}}n}}\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 la même valeur de $A_{k}(n)$ que ci-dessus. La démonstration de cette formule fait intervenir les suites de Farey, les cercles de Ford, et l'analyse complexe.

Autres formules de récurrence

On peut obtenir une première relation de récurrence avec la fonction somme des diviseurs σ :

$p(n)={\frac {1}{n}}\sum _{k=1}^{n}\sigma (k)p(n-k)$.

En notant $q(n)$ le nombre de partitions de $n$ en entiers distincts (égal au nombre de partitions de $n$ en entiers impairs) :

$p(n)=\sum _{k=0}^{\lfloor n/2\rfloor }q(n-2k)p(k)$.

Le nombre $p_{m}(n)$ de partitions d'un entier $n\geq 1$ en entiers supérieurs ou égaux à $m$ (qui vaut donc $p(n)$ si $m=1$ et qui est nul si $m>n$) vérifie :

$p_{m}(n)=p_{m}(n-m)+p_{m+1}(n)$,

ainsi que la relation de récurrence

$\forall n\geq m\geq 1\quad p_{m}(n)=1+\sum _{m\leq k\leq n/2}p_{k}(n-k)$.

Maximisation du produit

Étant donné un entier n > 1, le produit m₁ × … × m_k d'une partition n = m₁ + … + m_k est maximum si tous les m_i sont égaux à 3, sauf zéro, un ou deux d'entre eux (selon la classe de n modulo 3) qui valent 2. En effet :

• aucun m_i ne doit être égal à 1 car 1 × m < m + 1 ;
• aucun m_i ne doit être supérieur ou égal à 5 car on aurait 3(m_i – 3) > m_i (ou encore : 2(m_i – 2) > m_i) ;
• chaque 4 peut être remplacé par deux 2 ;
• il y a au plus deux 2 car 2³ < 3².

Notes et références

Sources

• (en) Miklós Bóna, A walk through combinatorics : an introduction to enumeration and graph theory, New Jersey, World Scientific, 2011, 3^e éd. (1^re éd. 2002), 546 p. (ISBN 978-981-4335-23-2, lire en ligne) — 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 — Le chapitre II est consacré aux partitions d'entiers.
• (en) Tom M. Apostol, Modular Functions and Dirichlet Series in Number Theory, Springer, 1990, 204 p.

Voir aussi

Articles connexes

• Fonction de Landau
• Graphe partitionnable
• Problème de la somme de sous-ensembles
• q-symbole de Pochhammer
• 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.
• Théorème de Glaisher (en)
• Décomposition en produit de facteurs premiers, correspondant à la décomposition multiplicative d'un entier qui, elle, est unique via l'utilisation des nombres premiers.
• Congruences de Ramanujan
• Conjecture de Newman (en)
• Nombre poli, ayant une partition en sommants consécutifs
• Suite d'Alcuin

Bibliographie

• (en) Henry L. Alder, « Partition Identities — from Euler to the Present », Amer. Math. Monthly, vol. 76,‎ 1969, p. 733-746 (lire en ligne) — Prix Lester Randolph Ford 1970.
• (en) George E. Andrews, The Theory of Partitions, CUP, 1998 (1^re éd. 1976) (lire en ligne)
• (en) Tom M. Apostol, Introduction to Analytic Number Theory, Springer, 1976 (DOI 10.1007/978-1-4757-5579-4), chap. 14, p. 304-328
• G. H. Hardy et E. M. Wright (trad. de l'anglais par F. Sauvageot), Introduction à la théorie des nombres [« An Introduction to the Theory of Numbers »], Vuibert-Springer, 2007, chap. 19, p. 353-382
• (en) Igor Pak (en), « Partition bijections, a survey », The Ramanujan Journal, vol. 12, n^o 1,‎ 2006, p. 5-75 (lire en ligne)
• (en) Jacobus van Lint, Combinatorial Theory Seminar Eindhoven University of Technology, Spinger Verlag, coll. « Lecture Notes in Mathematics » (n^o 382), 1974 (DOI 10.1007/BFb0057323), « Partitions », p. 33-39

Liens externes

• (en) « Partition Function », sur numericana.com
• (en) Eric W. Weisstein, « Partition Function P », sur MathWorld
• (en) H. Bottomley, « Partition and composition calculator », sur Henry Bottomley's Java and JavaScript examples