Composition (combinatoire)

Pour les articles homonymes, voir Composition.

En mathématiques, et notamment en combinatoire, une composition d'un entier positif ${\displaystyle n}$ est une représentation de ${\displaystyle n}$ comme somme d'une suite finie d'entiers strictement positifs. Ainsi, (1,2,1) est une composition de 4=1+2+1. Deux suites qui diffèrent par l'ordre de leurs parts sont considérées comme des compositions différentes. Ainsi, (2,1,1) est une autre composition de l'entier 4. Les compositions diffèrent donc des partitions d'entiers qui considèrent des sommes sans tenir compte de l'ordre de leurs termes.

La propriété principale est que le nombre de compositions d'un entier ${\displaystyle n}$ est ${\displaystyle 2^{n-1}}$, et donc que les compositions sont en bijection avec les parties d'un ensemble à ${\displaystyle n-1}$ éléments.