partition d'un entier

Prenons quatre jetons identiques et notons seulement la taille de groupes non vides. On peut garder les quatre ensemble, faire des groupes de trois et un, deux et deux, deux puis un et un, ou quatre groupes d'un. L'ordre dans lequel on pose les groupes ne crée pas une nouvelle possibilité. Ainsi, « trois puis un » et « un puis trois » décrivent la même partition de 4.

Une partition d'un entier positif est une écriture de cet entier comme somme d'entiers strictement positifs. Les termes peuvent se répéter. Leur ordre ne compte pas : les écritures 3 + 1 et 1 + 3 déterminent donc une seule partition de 4. Pour éviter les doublons lors d'une énumération, on peut ranger les termes du plus grand au plus petit. Ce rangement est une convention pratique, pas une donnée supplémentaire de la partition.

Le nombre de partitions de l'entier positif appelé n se note p(n). Par exemple, p(4) = 5, car les cinq possibilités sont 4, 3 + 1, 2 + 2, 2 + 1 + 1 et 1 + 1 + 1 + 1. Cette fonction de comptage est étudiée en combinatoire et en théorie des nombres.

On cherche toutes les partitions de 4. Les données sont l'entier 4, des termes entiers strictement positifs et la règle selon laquelle deux ordres différents ne comptent qu'une fois. Pour organiser la recherche, les termes seront écrits du plus grand au plus petit.

1. Avec un seul terme, on obtient 4.
2. Avec deux termes, on obtient 3 + 1 et 2 + 2.
3. Avec trois termes, on obtient 2 + 1 + 1.
4. Avec quatre termes, la seule possibilité est 1 + 1 + 1 + 1.

Les cinq sommes sont bien égales à 4 :Il y a donc exactement cinq partitions et p(4) = 5. Pour contrôler qu'il n'en manque aucune, on fixe le nombre de termes : il ne peut aller que de un à quatre, et chaque cas a été épuisé sans compter deux ordres séparément.

Une partition sert lorsque seul compte le découpage d'un total en tailles de groupes positives. Pour un total de 4, on conserve 3 + 1 une seule fois, même si le groupe de taille 1 est cité avant celui de taille 3.

Pour dénombrer les possibilités, on range les termes par ordre décroissant puis on vérifie chaque nombre possible de termes. Si la succession des groupes porte une information, ce critère observable impose d'utiliser des compositions plutôt que des partitions.

Une composition d'un entier tient compte de l'ordre des termes, contrairement à une partition. Le test consiste à permuter deux termes : 3 + 1 et 1 + 3 sont deux compositions distinctes de 4, mais une seule partition. La représentation par groupes de jetons rend visible cette absence d'ordre.

La définition donnée ici porte sur un entier positif et emploie uniquement des termes strictement positifs. Introduire 0 permettrait d'ajouter indéfiniment des zéros à une même somme ; il faut donc conserver la condition de positivité.

Un terme unique est autorisé. Ainsi, 4 est lui-même une partition de 4 ; l'écarter ferait tomber le décompte de cinq à quatre. À l'autre extrême, la partition comportant le plus de termes est 1 + 1 + 1 + 1.

Les répétitions sont permises, mais les permutations ne créent pas de nouvelles partitions. Il faut donc garder 2 + 2 et 2 + 1 + 1, tout en refusant de recompter 1 + 2 + 1 ou 1 + 1 + 2.

L'analyse combinatoire élargit la perspective : elle présente les principes de dénombrement auxquels appartient le calcul du nombre de partitions.