Article : Partitions d un entier - Lycée Charles Poncet (Cluses) Lycée Camille Sée (Paris)

Prenons un nombre entier positif n. De combien de façons peut-on écrire n , comme somme de nombres entiers positifs ? Le sens de la question varie selon que l'on considère des sommes ordonnées ou non : une composition de n sera une suite d'entiers positifs de somme n (ainsi (1,2,2) et (2,1,2) seront deux compositions distinctes de l'entier 5) tandis qu'une partition de n sera une liste d'entiers positifs, de somme n, rangée par ordre croissant (ainsi 1+2+2 et 2+1+2 seront des écritures différentes de la même partition du nombre 5, soit (1,2,2)). Les auteurs montrent que le nombre A( n) de compositions de n vaut 2^(n-1). Pour le nombre P( n) de partitions de l'entier n, ils donnent une expression simple de la série génératrice correspondante, c'est à dire de la somme infinie 1+ P(1)X^1+ P(2)X^2+ P(3)X^3+ ...