Partition d'un entier

Pour les articles homonymes, voir Partition.

• 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.

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), à l'ordre près 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.

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

La suite des nombres de partitions pour les entiers naturels successifs est déterminée par une fonction récursive. Hardy et Ramanujan en ont donné un équivalent en 1918, puis Hans Rademacher en a donné une formule exacte en 1937.

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

Présentation

À l'aide des diagrammes de Ferrers

o o o o
o o o o
o o o
o
o

Diagramme de Ferrers
de la partition (5 ; 3 ; 3 ; 2)
représentée en colonnes.

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 colonne 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. 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.

• 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.

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 (4 ; 4 ; 3 ; 1 ; 1)
duale de la partition (5 ; 3 ; 3 ; 2).

Le fait de lire en lignes un diagramme de Ferrers tracé en colonnes, ou réciproquement, permet de définir la partition duale (ou conjuguée). Géométriquement, ce la 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$.

La dualité permet de montrer 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 plus bas).

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$ 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 * * * *
o * x x
o * x
o *

o * x
o * x
o * x
o *
o *
o *
o *
o
o

Correspondance entre partitions autoduales
et partitions à parties impaires distinctes.

La représentation par les diagramme 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)$. Pour de petites valeurs de $n$, il 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é.

Ce procédé permet de calculer le nombre de partitions d'un entier avec une complexité algorithmique quadratique, 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 autre méthode de calcul du nombre de partitions d'un entier se déduit du théorème du nombre pentagonal 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)...$

où les termes de cette somme sont de la forme $(-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.

Suite des nombres de partitions

Propriétés

Les techniques des diagrammes de Ferrers permettent aussi de prouver des résultats comme le suivant :

• Il y a p(n) - p(n-1) partages de n dans lesquels chaque partie est supérieure à 2.
• p(1) + p(2) + ... + p(n) < p(2n)

Il a été démontré que si n se termine par 4 ou 9, alors p(n) est divisible par 5.

• 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) = 3972999029388
• p(1 000) = 24061467864032622473692149727991
• p(10 000) = 36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435144

Fonction génératrice associée

Euler a remarqué (sans trop se soucier de considérations de convergence) que la série génératrice de p,

$S(x)=p(0)+p(1)x+p(2)x^2+\dots=\sum_{n\ge0}p(n)x^n$

est égale au produit infini suivant :

$S(x)=\frac{1}{1-x}\cdot\frac{1}{1-x^2}\cdot\frac{1}{1-x^3}\dots=\prod_{n\ge1}\frac{1}{1-x^n}.$

En effet, en développant chaque facteur comme une série géométrique, le produit infini se réécrit :

$(1 + x + x^2 + x^3 + ...)(1 + x^2 + x^4 + x^6 + ...)(1 + x^3 + x^6 + x^9 +...)...$

et le coefficient du terme de degré $n$ est le nombre de suites d'exposants dont la somme vaut $n$, chaque exposant étant un multiple de son rang. Ces suites correspondent à la définition des partitions d'un entier sous forme d'une mesure (voir plus haut).

La formulation de la fonction génératrice est similaire à la formulation du produit de plusieurs formes modulaires, en donnant une certaine idée de la connexion entre les deux.

Estimation asymptotique

Hardy et Ramanujan ont présenté en 1918 une fonction approximative de p(n) ; à savoir :

$p(n) \sim A_n \mathrm{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, Hans 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}{\mathrm{e}^{\pi \mathrm{i}\; s(h,k) - 2 \pi \mathrm{i} n h/k}}$ et $s(h,k)$ la somme de Dedekind. La notation $(h,k)=1$ signifie qu'on ne prend que les valeurs de h pour lesquelles h et k sont premiers entre eux. Le démonstration de cette formule fait intervenir les suites de Farey, les cercles de Ford, et l'analyse complexe.

Voir aussi

Liens internes

• Graphe partitionable
• Problème de la somme de sous-ensembles
• Nombre de Bell qui est le nombre de partitions d'un ensemble à n éléments.

Liens externes

• Partition and composition calculator
• First 4096 values of the partition function
• An algorithm to compute the partition function
• Details in Math World

Référence bibliographiques

• Miklós Bóna, A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory, World Scientific Publishing, 2002. ISBN 981-02-4900-4 (contient une introduction élémentaire à la notion de partition d'un entier, incluant les diagrammes de Ferrers)
• Louis Comtet, Analyse combinatoire, tome I, Presses Universitaires de France 1970 (le chapitre II est consacré aux partitions d'entiers).
• Tom M. Apostol, Modular Functions and Dirichlet Series in Number Theory, Springer 1990 - 204 pages.