View source for Composition (combinatorics)

{{TEX|done}}{{MSC|05A17|11P81}}

A composition of a natural number $n$ is an expression of $n$ as an ordered sum of positive integers.  Thus the compositions of $4$ are $4, 3+1, 1+3, 2+2, 2+1+1, 2+1+1, 1+1+2, 1+1+1+1$. The underlying [[partition]] of a composition is the corresponding unordered sum.  

A composition on $n$ may be represented as a sequence of $n$ dots separated by bars with no two bars adjacent: thus $4 = 1+2+1$ is represented by $( \bullet \vert \bullet\bullet \vert \bullet )$.  The number of compositions of $n$ into $k$ parts is thus $\left({ \begin{array}{cc} n-1 \\ k-1 \end{array} }\right)$ and the total number of compositions of $n$ is $2^{n-1}$

====References====
* Luoto, Kurt; Mykytiuk, Stefan; van Willigenburg, Stephanie, "An introduction to quasisymmetric Schur functions. Hopf algebras, quasisymmetric functions, and Young composition tableaux", Springer  (2013) ISBN 978-1-4614-7299-5  {{ZBL|1277.16027}}
* Riordan, John "Introduction to Combinatorial Analysis", Wiley [1958] Dover (2002) ISBN 0-486-42536-3 {{ZBL|0078.00805}}