Calculateur de partitions d'entiers

La fonction de partition d'entiers p(n) répond à une question classique de dénombrement : de combien de manières peut-on écrire un entier non négatif n comme somme d'entiers positifs lorsque l'ordre des termes n'importe pas ? Par exemple, 4 égale 4, 3+1, 2+2, 2+1+1 et 1+1+1+1, si bien que p(4) vaut cinq ; 5 admet sept partitions et 10 en admet quarante-deux. Les partitions apparaissent en théorie des nombres, dans les fonctions génératrices, en mécanique statistique et dans les concours de programmation dès que l'on compte des sommes de multi-ensembles plutôt que des compositions ordonnées ou des partitions d'ensembles étiquetés. Cette capacité accepte un entier non négatif n et renvoie le p(n) exact sous forme de chaîne décimale calculée par programmation dynamique en BigInt, de sorte que des valeurs bien au-delà des limites habituelles d'entiers sûrs restent correctes chiffre par chiffre. Un n négatif est rejeté avec une erreur de validation claire plutôt qu'un zéro silencieux ou une réponse fausse.

Comment la fonction de partition p(n) est définie

Une partition entière non restreinte d'un entier non négatif n est une façon d'écrire n comme somme d'entiers positifs dans laquelle l'ordre des termes est sans importance. Par convention p(0) vaut un, en comptant la partition vide de zéro. Les petites valeurs classiques des manuels sont p(1)=1, p(2)=2 (à savoir 2 et 1+1), p(3)=3, p(4)=5, p(5)=7, p(6)=11 et p(10)=42.

La fonction génératrice ordinaire de la suite est le produit infini, sur k supérieur ou égal à un, de un sur un moins x à la puissance k, qui encode que chaque entier positif peut apparaître un nombre quelconque de fois comme part. Une récurrence pratique utilisée en logiciel est le programme dynamique classique de type rendu de monnaie : on initialise un tableau avec une façon de former la somme zéro, puis pour chaque taille de part de un à n, on ajoute les façons de compléter le reste.

Cette récurrence remplit p(n) de façon exacte et ne compte jamais deux fois les ordres parce que les parts ne sont introduites qu'une seule fois en taille non décroissante.

Des objets voisins mais distincts comprennent les compositions, où l'ordre compte et où il y a deux puissance n moins un compositions de n ; les partitions d'ensembles comptées par les nombres de Stirling de seconde espèce ou les nombres de Bell, qui partitionnent des éléments étiquetés plutôt que d'additionner des entiers positifs non étiquetés ; et les partitions restreintes qui exigent des parts distinctes, des parts impaires seulement, ou un nombre fixe de parts.

Cette implémentation n'utilise jamais d'approximation en virgule flottante, d'échantillonnage Monte-Carlo ni de tables externes : elle remplit un tableau unidimensionnel de BigInt afin que chaque chiffre soit exact. Le chemin est pleinement déterministe — sans graines aléatoires, sans horloges, sans réseau et sans dérive de modèle —, si bien que le même n produit toujours la même chaîne.

Où les partitions d'entiers apparaissent dans le travail réel

Les cours de théorie des nombres et les concours de programmation demandent constamment combien de partitions non restreintes un n donné possède, comment p(n) croît, ou si un tableau de petites valeurs concorde avec les congruences de Ramanujan et d'autres identités classiques. Les concepteurs d'algorithmes utilisent les comptages de partitions pour analyser des espaces d'états de type sac à dos entier, dénombrer des décompositions en multi-ensembles d'un budget de ressources, ou dimensionner des tables de DP dont les dimensions suivent les tailles de parts.

En physique et en combinatoire, p(n) se relie aux fonctions de partition bosoniques et aux coefficients de fonctions génératrices ; les enseignants montrent souvent une courte liste de partitions d'un petit n puis demandent le seul comptage. La préparation aux entretiens et l'entraînement olympique ont fréquemment besoin d'un p(n) fiable sans maintenir à la main de grandes tables ni risquer des comptages de compositions décalés d'une unité.

Si vous avez ensuite besoin de compositions où l'ordre compte, de partitions d'ensembles via les nombres de Stirling de seconde espèce, des seuls nombres de Bell, de partitions restreintes à parts distinctes ou impaires seulement, ou d'une énumération explicite de chaque partition plutôt que du comptage, traitez-les comme des intentions de recherche distinctes plutôt que de surcharger cette page.

Gardez n dans la borne documentée afin que la latence du niveau gratuit reste prévisible, et préférez des consommateurs de chaînes pour la valeur renvoyée car p(n) quitte la plage des entiers sûrs bien avant cinq mille.