Les partitions d'entiers
De combien de façons peut-on écrire 5 comme somme d'entiers positifs, sans tenir compte de l'ordre ? 5, 4 + 1, 3 + 2, 3 + 1 + 1, 2 + 2 + 1, 2 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1 : sept façons. Ce nombre, noté p(n), croît d'abord doucement, puis à une vitesse vertigineuse : p(100) dépasse 190 millions. Euler l'a dompté par une série infinie, Hardy et Ramanujan par une formule asymptotique, Rademacher par une formule exacte. En chemin apparaissent des identités surprenantes et des divisibilités inattendues.
Vue d'ensemble
Une partition de n est une suite décroissante d'entiers positifs, les parts, dont la somme vaut n. Contrairement aux compositions (où 2 + 1 et 1 + 2 sont différentes), l'ordre ne compte pas. Quelques valeurs :
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 10 | 20 | 50 | 100 | 200 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| p(n) | 1 | 2 | 3 | 5 | 7 | 11 | 15 | 42 | 627 | 204 226 | 190 569 292 | 3 972 999 029 388 |
Diagrammes de Ferrers et conjugaison
Un dessin rend visibles des égalités qu'aucun calcul ne laisse deviner.
On représente la partition 5 + 3 + 3 + 1 par quatre lignes de 5, 3, 3 et 1 cases alignées à gauche : c'est son diagramme de Ferrers (ou de Young). En lisant les colonnes au lieu des lignes, on obtient la partition conjuguée, ici 4 + 3 + 3 + 1 + 1. Le diagramme est retourné par la diagonale. Conséquence immédiate : le nombre de partitions de n en au plus k parts est égal au nombre de partitions de n dont toutes les parts valent au plus k. Les partitions égales à leur conjuguée (symétriques) sont aussi nombreuses que les partitions en parts impaires et distinctes : on « déplie » chaque équerre en une ligne impaire.
Parts impaires ou parts distinctes : le théorème d'Euler
Deux familles de partitions qui n'ont rien à voir, et qui ont pourtant la même taille.
Euler démontre en 1748 qu'il y a autant de partitions de n en parts impaires que de partitions de n en parts toutes différentes. Pour n = 6 : 5 + 1, 3 + 3, 3 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1 + 1 d'un côté ; 6, 5 + 1, 4 + 2, 3 + 2 + 1 de l'autre. Sa preuve est un calcul de séries : Π 1/(1 − x2k−1) = Π (1 + xk). Glaisher (1883) en donne une correspondance explicite. Dans une partition en parts impaires, on regroupe deux parts égales en une part double, et l'on recommence tant qu'il reste des doublons. C'est l'écriture en base 2 du nombre de fois où chaque part apparaît.
La fonction génératrice et le théorème pentagonal
Un produit infini dont presque tous les coefficients s'annulent.
Euler remarque que 1/((1 − x)(1 − x²)(1 − x³)⋯) = Σ p(n) xn : chaque facteur 1/(1 − xk) = 1 + xk + x2k + … choisit combien de fois la part k apparaît. Il développe alors l'inverse, Π(1 − xk), et découvre que presque tous les coefficients sont nuls : il ne reste que ±1 aux nombres pentagonaux k(3k − 1)/2 = 1, 2, 5, 7, 12, 15, 22, 26… Il lui faut neuf ans (1741-1750) pour le démontrer. Franklin en donne en 1881 une preuve par les diagrammes. On en tire une récurrence très rapide : p(n) = p(n − 1) + p(n − 2) − p(n − 5) − p(n − 7) + p(n − 12) + p(n − 15) − …, que MacMahon a utilisée en 1918 pour calculer p(n) jusqu'à 200 à la main.
La croissance de p(n) : Hardy, Ramanujan, Rademacher
Une formule approchée d'une précision inouïe, puis une formule exacte.
En 1918, Hardy et Ramanujan montrent que p(n) ~ eπ√(2n/3)/(4n√3). Le nombre de chiffres de p(n) croît donc comme √n. Ils vont plus loin : une série de termes de plus en plus petits, dont le premier donne déjà p(200) = 3 972 999 029 388 à 36 000 près environ, et quelques termes suffisent à retrouver la valeur exacte en arrondissant. En 1937, Rademacher la transforme en une série convergente qui donne exactement p(n). Chaque terme fait intervenir une somme de Kloosterman et les sommes de Dedekind.
Signature : les congruences de Ramanujan, la forme limite, Rogers-Ramanujan
Les partitions cachent des divisibilités, une forme géométrique et des identités étonnantes.
En parcourant la table de MacMahon, Ramanujan remarque en 1919 que p(4), p(9), p(14), p(19)… sont tous divisibles par 5. Il démontre trois congruences : p(5k + 4) ≡ 0 (mod 5), p(7k + 5) ≡ 0 (mod 7), p(11k + 6) ≡ 0 (mod 11). Dyson (1944) cherche une explication combinatoire, le « rang » d'une partition (plus grande part moins nombre de parts). Il répartit les partitions de 5k + 4 en cinq classes égales selon le rang modulo 5. Ono a montré en 2000 qu'il existe des congruences de ce type pour tout module premier supérieur à 3, mais elles sont beaucoup plus cachées.
Tirons au hasard, toutes avec la même probabilité, une partition d'un grand entier n, et réduisons son diagramme d'un facteur √n. Le contour n'est pas quelconque : il se rapproche toujours de la même courbe, e−πx/√6 + e−πy/√6 = 1 (Temperley, 1952 ; Vershik, 1996). Pour tirer une partition au hasard, la page tire indépendamment le nombre de parts égales à 1, à 2, à 3… selon des lois géométriques bien choisies, et recommence tant que la somme ne vaut pas exactement n (méthode de Fristedt, 1993).
L. J. Rogers les publie en 1894 sans être remarqué ; Ramanujan les redécouvre vers 1913, sans démonstration. Il y a autant de partitions de n dont les parts diffèrent deux à deux d'au moins 2 que de partitions de n en parts de la forme 5k + 1 ou 5k + 4. Pour n = 9 : 9, 8 + 1, 7 + 2, 6 + 3, 5 + 3 + 1 d'un côté ; 9, 6 + 1 + 1 + 1, 4 + 4 + 1, 4 + 1 + 1 + 1 + 1 + 1, 1 + 1 + … + 1 de l'autre. Ces identités réapparaissent en physique statistique : Baxter les a retrouvées en 1980 dans la solution du modèle des hexagones durs.
Une brève histoire
En résumé
Des dessins
Les diagrammes de Ferrers et leur conjugaison transforment des égalités de comptage en simples symétries.
Des séries
La fonction génératrice Π 1/(1 − xk) prouve le théorème d'Euler et donne, par les nombres pentagonaux, une récurrence rapide.
Des surprises
Croissance en eπ√(2n/3), formule exacte de Rademacher, congruences de Ramanujan, forme limite : les partitions relient combinatoire, analyse et probabilités.
Pour aller plus loin
Les formes modulaires. La fonction η de Dedekind, η(τ) = q1/24Π(1 − qn), relie la fonction génératrice des partitions aux formes modulaires : c'est la source des formules de Rademacher et des congruences.
En algèbre, les partitions de n décrivent les classes de conjugaison du groupe symétrique Sn, ses représentations irréductibles (par les tableaux de Young) et les classes de matrices nilpotentes (forme de Jordan).
Liens. Dénombrement (combinaisons, nombres de Catalan), suites numériques, réduction de Jordan, modules sur un anneau (groupes abéliens finis et partitions des exposants).