Quel est le nombre de compositions d’un entier?

Le nombre de compositions d’un entier est le nombre de façons d’écrire cet entier sous la forme d’une somme (ordonnée).

Par exemple, 4 peut s’écrire comme 1+1+1+1 = 1+1+2 = 2+1+1 = 1+2+1 = 2+2 = 1+3 = 3+1 = 4. Il y a 8 compositions de 4.

On démontre assez simplement qu’il y a 2^n-1 compositions de n.