Partition d'un entier - Définition

Introduction

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), à 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

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.

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

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 = b_kq + r la division euclidienne de N 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 et k strictement supérieurs à 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.

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 lorsque cette expression a un sens, avec k entier relatif. Les nombres sont les nombres pentagonaux généralisés.