Compositions and weak compositions of a natural number into a fixed number of parts

Let $n, m \in \mathbb{N}$.

• A weak composition of $n$ into $m$ parts is a function $k : m \to \mathbb{N}$ with $\sum_{i<m} k_i = n$, the sum being the $\mathbb{N}$-valued one of Finite sums and finite products of natural numbers, $\sum_{k<n} a_k$ and $\prod_{k<n} a_k$ in $\mathbb{N}$. The set of them is the set $\mathcal{W}(n,m)$ introduced in The multinomial coefficient $\binom{n}{k_0,\dots,k_{m-1}}$ as the number of ordered partitions of an $n$-set into blocks of prescribed sizes.
• A composition of $n$ into $m$ parts is a weak composition all of whose parts are nonzero, that is $k_i \ge 1$ for every $i < m$ (Discreteness: $\sigma(n)$ is the immediate successor). Write $\mathcal{C}(n,m) := \{\, k \in \mathcal{W}(n,m) \ :\ k_i \ge 1 \text{ for every } i<m \,\}.$

The parts are ordered: $k$ is a function on $m$, so $(1,2)$ and $(2,1)$ are different compositions of $3$ into $2$ parts.

Both sets are finite. Every $k \in \mathcal{W}(n,m)$ has $k_i \le n$ for each $i$, because a term of a sum of naturals is at most the sum (clause 4 of Laws of finite sums and products in $\mathbb{N}$, and $\iota\big(\sum_{k<n} a_k\big) = \sum_{k<n} \iota(a_k)$); so $\mathcal{W}(n,m)$ is a subset of the set of functions $m \to \sigma(n)$, which is finite by The set $A^{B}$ of functions $B \to A$ between finite sets is finite, with $\lvert A^{B}\rvert = \lvert A\rvert^{\lvert B\rvert}$, and A subset of a finite set is finite, with $\lvert B\rvert \le \lvert A\rvert$, and equality holds if and only if $B = A$ applies. $\mathcal{C}(n,m)$ is a subset of $\mathcal{W}(n,m)$, hence finite too.

The case $m = 0$, which is exactly where the next item's hypothesis lives. There is precisely one function $0 \to \mathbb{N}$, the empty function, and its sum is the empty sum, $0$. Hence

$\lvert\mathcal{W}(0,0)\rvert = 1, \qquad \lvert\mathcal{W}(n,0)\rvert = 0 \ \text{ for } n \ge 1,$

and the same two values for $\mathcal{C}$, since the condition "every part is nonzero" is vacuous for the empty tuple. Saying this here is what lets For $m \ge 1$ the number of weak compositions of $n$ into $m$ parts is $\binom{n+m-1}{m-1}$, and the number of compositions is $\binom{n-1}{m-1}$ for $n \ge 1$ carry the hypothesis $m \ge 1$ honestly: at $m = 0$ the count is not given by the formula, and the true value is recorded above.

Small values of $m$. $\lvert\mathcal{W}(n,1)\rvert = 1$, the unique weak composition being $k_0 = n$; and $\lvert\mathcal{C}(n,1)\rvert = 1$ for $n \ge 1$ while $\mathcal{C}(0,1) = \varnothing$.

• The same object under two names. $\mathcal{W}(n,m)$ is the index set of the outer sum of The multinomial coefficient equals $n!/\prod_{i<m} k_i!$, and $(x_0+\dots+x_{m-1})^{n} = \sum \iota\!\binom{n}{k}\prod_{i<m} x_i^{k_i}$ in $\mathbb{R}$. That theorem and this definition therefore speak about one set, and the count supplied by For $m \ge 1$ the number of weak compositions of $n$ into $m$ parts is $\binom{n+m-1}{m-1}$, and the number of compositions is $\binom{n-1}{m-1}$ for $n \ge 1$ is the number of terms in the multinomial expansion.

• Weak versus strict. Much of the literature reserves composition for tuples of positive parts and says weak composition when zeros are allowed; that is the convention adopted here. The count of the weak ones is the primary result, and the strict count is obtained from it by subtracting $1$ from every part.

• Nothing here is about unordered partitions. The number of ways of writing $n$ as an unordered sum is a different and much harder count, and it is not developed at this point in the reading order.