Composition (combinatorics)

2020 Mathematics Subject Classification: Primary: 05A17 Secondary: 11P81 [MSN][ZBL]

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