Composition (combinatoire)

Bijection entre entiers en écriture binaire et compositions de 4.

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.

Définition

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

Exemples

Les 32 compositions de 6. L'absence d'une barre de séparation est notée en rouge.

Les 11 partitions de 6. Une partition est une composition dont les parts sont décroissantes.

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 ${\displaystyle n}$ est ${\displaystyle 2^{n-1}}$.

Voici une démonstration de cette propriété utilisant la méthode des étoiles et des barres. On considère une suite de ${\displaystyle n}$ points (ou étoiles), et on choisit de placer ou de ne pas placer une barre verticale entre des points. Par exemple, pour ${\displaystyle n=8}$, on peut placer trois barres comme suit :

${\displaystyle \bullet \bullet \mid \bullet \bullet \mid \bullet \mid \bullet \bullet \bullet }$

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

La démonstration montre aussi que le nombre de compositions d'un entier ${\displaystyle n}$ formées de ${\displaystyle k}$ parts est égal à ${\displaystyle {\binom {n-1}{k-1}}}$. Donald Knuth, dans le volume 4a de son traité[2], 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) »).

Voir aussi

• Partition d'entier
• Méthode des étoiles et des barres
• Combinaison avec répétition (une ${\displaystyle n}$-combinaison avec répétition de ${\displaystyle k}$ objets est une suite ${\displaystyle (p_{1},\ldots ,p_{k})}$ d'entiers positifs ou nuls tels que ${\displaystyle n=p_{1}+\cdots +p_{k}}$).

Notes

Les compositions d'entiers sont un objet combinatoire simple, et se trouvent dans de nombreux livres de combinatoire de base. Louis Comtet en parle dans le premier volume de son livre[3]. Knuth[2] y consacre une section. Un ouvrage entier a été consacré aux compositions et à ses variantes[4].

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Composition (combinatorics) » (voir la liste des auteurs).

1. De manière plus formelle, il y a bijection entre les compositions ${\displaystyle (p_{1},\ldots ,p_{k})}$ de ${\displaystyle n}$ et les suites ${\displaystyle (p_{1},p_{1}+p_{2},\ldots ,p_{1}+\cdots +p_{k-1})}$ avec ${\displaystyle p_{1}+\cdots +p_{k-1}<n}$, et celles-ci sont en bijection avec les sous-ensembles de ${\displaystyle \{1,\ldots ,n-1\}}$.
2. Knuth 2011, Section7.2.1.3. Generation all combinations, p. 355-389.
3. Comtet 1970, tome I, ex. 22, p. 132.
4. Heubach et Mansour 2009.

Bibliographie

• Louis Comtet, Analyse combinatoire, Tomes I et II, Paris, Presses Universitaires de France, coll. « Sup - Le Mathématicien », 1970

• Donald E. Knuth, The Art of Computer Programming, vol. 4A : Combinatorial Algorithms, Part 1, Addison-Wesley, 2011 (ISBN 978-0-201-03804-0 et 0-201-03804-8, présentation en ligne)

• Silvia Heubach et Toufik Mansour, Combinatorics of Compositions and Words, Boca Raton, FL, CRC Press, coll. « Discrete Mathematics and its Applications », 2009, 504 p. (ISBN 978-1-4200-7267-9, zbMATH 1184.68373)

Liens externes

• Partition and composition calculator
• Partitions d'entiers sur le site Math en jeans.