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 $\left(\genfrac{}{}{0px}{}{n}{k_0,\dots ,k_{m-1}}\right)$ 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\}\mathrm{.}$

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 \left({\sum }_{k<n}{a}_k\right)={\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 $\mid A^B\mid =\mid A{\mid }^{\mid B\mid }$, and A subset of a finite set is finite, with $\mid B\mid \le \mid A\mid$, 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

$\mid \mathcal{W}(0,0)\mid =1,\mid \mathcal{W}(n,0)\mid =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 $\left(\genfrac{}{}{0px}{}{n+m-1}{m-1}\right)$, and the number of compositions is $\left(\genfrac{}{}{0px}{}{n-1}{m-1}\right)$ 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$. $\mid \mathcal{W}(n,1)\mid =1$, the unique weak composition being $k_0=n$; and $\mid \mathcal{C}(n,1)\mid =1$ for $n\ge 1$ while $\mathcal{C}(0,1)=\mathrm{\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!\mathrm{/}{\prod }_{i<m}{k}_i!$, and $(x_0+\cdots +x_{m-1}{)}^n=\sum \iota \text{\hspace{0.17em}⁣}\left(\genfrac{}{}{0px}{}{n}{k}\right){\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 $\left(\genfrac{}{}{0px}{}{n+m-1}{m-1}\right)$, and the number of compositions is $\left(\genfrac{}{}{0px}{}{n-1}{m-1}\right)$ 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.