Composition (combinatoire)
# Composition (combinatoire)

En mathématiques, et notamment en combinatoire, une composition d'un entier positif n est une représentation de n comme somme d'une suite 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 suites sans tenir compte de l'ordre de leurs termes.

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

## Définition

Une composition d'un entier naturel positif $n>0$ est une suite $(p_{1},\ldots ,p_{k})$ d'entiers positifs tels que $n=p_{1}+\cdots +p_{k}$. Chaque $p_{i}$ est une part, et l'entier $k$ est la longueur.

## Exemples

Les seize compositions de 5 sont :

* 5
* 4 + 1
* 3 + 2
* 3 + 1 + 1
* 2 + 3
* 2 + 2 + 1
* 2 + 1 + 2
* 2 + 1 + 1 + 1
* 1 + 4
* 1 + 3 + 1
* 1 + 2 + 2
* 1 + 2 + 1 + 1
* 1 + 1 + 3
* 1 + 1 + 2 + 1
* 1 + 1 + 1 + 2
* 1 + 1 + 1 + 1 + 1.

Les sept partitions de 5:

* 5
* 4 + 1
* 3 + 2
* 3 + 1 + 1
* 2 + 2 + 1
* 2 + 1 + 1 + 1
* 1 + 1 + 1 + 1 + 1.

## Nombre de compositions

Le nombre de composition de l’entier $n$ est $2^{n-1}$.

Voici une démonstration de cette propriété. On considère une suite de $n$ points, et on choisit de placer ou de ne pas placer une barre verticale entre des points. Par exemple, pour $n=8$, on peut placer trois barres comme suit :

    $\bullet \bullet \mid \bullet \bullet \mid \bullet \mid \bullet \bullet \bullet$

Une part d'une composition est formé du nombre de points qui sont contigus. Dans l'exemple, la composition est (2,2,1,3). De manière générale, il y a $n-1$ positions où on peut choisir de placer ou de ne pas placer une barre de séparation; ceci fait $2^{n-1}$ choix possibles de séparations et comme les choix déterminent les compositions, cela fait $2^{n-1}$ compositions.

La démonstration montre que le nombre de compositions d'un entier $n$ formées de $k$ parts est ${\binom {n-1}{k-1}}$. Donald Knuth, dans le volume 4a de son traité, s'intéresse à la génération de toutes les compositions, sous des contraintes variées.

## Bijection avec les écritures binaires

Pour noter la représentation graphique ci-dessus, on peut convenir d'écrire un « 1 » s'il n'y a pas de barre de séparation, et un « 0 » dans le cas contraire. Ainsi, la composition (2,2,1,4) de 9 est représenté par la suite de 8 chiffres binaires 10100111 (il y a autant de 0 dans « 10100111 » qu'il y a de virgules dans « (2,2,1,4) »).

