Voir la source de Composition (combinatoire)

{{Voir homonymes|Composition}}
[[File:Binary and compositions 4.svg|thumb|upright=2.5|[[Bijection]] entre entiers [[Système binaire|en écriture binaire]] et compositions de 4.]]
En [[mathématiques]], et notamment en [[combinatoire]], une '''composition''' d'un [[Entier naturel|entier positif]] <math>n</math> est une représentation de <math>n</math> comme [[Somme (arithmétique)|somme]] d'une suite finie d'[[Entier naturel|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 [[partition d'entier | 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 <math>n</math> est <math>2^{n-1}</math>, et donc que les compositions sont en bijection avec les parties d'un ensemble à <math>n-1</math> éléments.

== Définition ==
Une ''composition'' d'un entier naturel positif <math>n>0</math> est une suite <math>(p_1,\ldots,p_k)</math> d'entiers strictement positifs tels que <math>n=p_1+\cdots+p_k</math>. Chaque <math>p_i</math> est une ''partie'' ou un ''sommant'' de la composition et l'entier <math>k</math> est sa longueur.

== Exemples ==
[[File:Compositions of 6.svg|thumb|Les 32 compositions de 6. L'absence d'une barre de séparation est notée en rouge.]]
[[File:Partitions of 6.svg|thumb|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 <math>n</math> est <math>2^{n-1}</math>.''

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

:<math>\bullet \bullet\mid \bullet \bullet\mid \bullet\mid \bullet \bullet \bullet</math> 

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 <math>n-1</math> positions où l'on peut choisir de placer ou de ne pas placer une barre de séparation ; ceci fait <math>2^{n-1}</math> choix possibles de séparations et comme les choix déterminent les compositions, cela fait <math>2^{n-1}</math> compositions<ref>De manière plus formelle, il y a bijection entre les compositions <math>(p_1,\ldots,p_k)</math> de <math>n</math> et les suites <math>(p_1,p_1+p_2,\ldots,p_1+\cdots+p_{k-1})</math> avec <math>p_1+\cdots+p_{k-1}<n</math>, et celles-ci sont en bijection avec les sous-ensembles de <math>\{1,\ldots,n-1\}</math>.</ref>.

La démonstration montre aussi que le nombre de compositions d'un entier <math>n</math> formées de <math>k</math> parts est égal à <math>\binom{n-1}{k-1}</math>. [[Donald Knuth]], dans le volume 4a de son traité<ref name=knuth/>, 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 <math>n</math>-combinaison avec répétition de <math>k</math> objets est une suite <math>(p_1,\ldots,p_k)</math> d'entiers positifs '''ou nuls''' tels que <math>n=p_1+\cdots+p_k</math>).

== 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<ref>{{harvsp|Comtet|1970|loc= tome I, ex. 22|p=132}}.</ref>. Knuth<ref name=knuth>{{harvsp|Knuth|2011|loc=Section7.2.1.3. Generation all combinations|p=355-389}}.</ref> y consacre une section. Un ouvrage entier a été consacré aux compositions et à ses variantes<ref>{{harvsp|Heubach|Mansour|2009}}.</ref>.

== Références ==
{{Traduction/Référence|en|Composition (combinatorics)|617967811|type=note}}
{{Références}}

== Bibliographie ==

* {{Ouvrage | prénom1=Louis | nom1=Comtet | titre=Analyse combinatoire, Tomes I et II | éditeur=Presses Universitaires de France | collection=Sup - Le Mathématicien | lieu=Paris | année=1970 | isbn=}} 

* {{Ouvrage | auteur1=[[Donald E. Knuth]] | titre=[[The Art of Computer Programming]] | volume=4A | titre volume=Combinatorial Algorithms, Part 1 | éditeur=Addison-Wesley | année=2011 | isbn=978-0-201-03804-0 | isbn2=0-201-03804-8 | présentation en ligne=http://www-cs-faculty.stanford.edu/~knuth/taocp.html}}

* {{Ouvrage | prénom1=Silvia | nom1=Heubach | prénom2=Toufik | nom2=Mansour | titre=Combinatorics of Compositions and Words | éditeur=CRC Press | collection=Discrete Mathematics and its Applications | lieu=Boca Raton, FL | année=2009 | pages totales=504 | isbn=978-1-4200-7267-9 | zbl=1184.68373}}

== Liens externes ==
* [http://www.se16.info/js/partitions.htm Partition and composition calculator]
*  [http://mathenjeans.free.fr/amej/edition/9910part/99_parti.html Partitions d'entiers] sur le site ''Math en jeans''.

{{Portail|Mathématiques}}
[[Catégorie:Théorie des nombres]]
[[Catégorie:Combinatoire]]