---
tag: 057H72B2MB
kind: statement
role: theorem
name: Number of compositions
msc: [05A17]
uses: [0J8ANSYKAC]
sources:
  - url: https://en.wikipedia.org/wiki/Composition_(combinatorics)
    locator: Number of compositions
---

## Statement

Let $n$ be a positive integer.
Then the number of [[compositions|0J8ANSYKAC]] of $n$ is $2^{n-1}$.

## Remarks

Proof: write $n$ as a row of $n$ ones. A composition is a choice of where to cut among the $n - 1$ gaps between them.
The number of compositions of $n$ into exactly $k$ parts is $\binom{n-1}{k-1}$.
For $n = 0$ there is one composition, the empty one.

## Explanations

### L1 human

Put $n$ dots in a row. Between two neighbours you either draw a bar or you do not.
There are $n - 1$ gaps with $2$ choices each, so there are $2^{n-1}$ compositions.