# 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

**How to Cite This Entry:**

Composition (combinatorics).

*Encyclopedia of Mathematics.*URL: http://encyclopediaofmath.org/index.php?title=Composition_(combinatorics)&oldid=54402