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$

The last-part decomposition, valid for every $M \in \mathbb{N}$ and every $n$. The map $k \mapsto \big(\sum_{i<M}k_i,\ k\restriction M\big)$ sends $\mathcal{W}(n,\sigma(M))$ into the union of the pairwise disjoint sets $\{j\}\times\mathcal{W}(j,M)$ for $j < \sigma(n)$: writing $j := \sum_{i<M}k_i$, the recursion clause gives $j + k_M = n$, so $j \le n$ and $k \restriction M \in \mathcal{W}(j,M)$. Its two-sided inverse sends $(j,\kappa)$ to the tuple extending $\kappa$ by the value $n-j$ at $M$, whose sum is $j + (n-j) = n$. Hence $\lvert\mathcal{W}(n,\sigma(M))\rvert = \sum_{j<\sigma(n)}\lvert\mathcal{W}(j,M)\rvert$ by [L5].

Base case, $M = 0$, that is $m = 1$. A weak composition of $n$ into one part is a function $k : 1 \to \mathbb{N}$ with $\sum_{i<1}k_i = k_0 = n$, and there is exactly one such function; so $\lvert\mathcal{W}(n,1)\rvert = 1 = \binom{n+0}{0}$ by [L3].

Inductive hypothesis: fix $M$ and assume $\lvert\mathcal{W}(n,\sigma(M))\rvert = \binom{n+M}{M}$ for every $n \in \mathbb{N}$.

A reindexing identity: $\sum_{j<\sigma(n)}\binom{j+M}{M} = \sum_{i<\sigma(n+M)}\binom{i}{M}$. Split the right-hand side at $p = M$, legitimate since $M \le \sigma(n+M)$: it becomes $\sum_{i<M}\binom{i}{M} + \sum_{j<\sigma(n+M)-M}\binom{M+j}{M}$. The first sum vanishes, every term being $\binom{i}{M} = 0$ for $i < M$ by [L3] and a sum of zeros being $0$ by the constant clause; and $\sigma(n+M)-M = \sigma(n)$, because $M + \sigma(n) = \sigma(M+n) = \sigma(n+M)$.

Inductive step. Applying step 1.1 with $\sigma(M)$ in place of $M$, then the hypothesis of step 1.3, then step 1.4 and finally the hockey-stick identity [L4] with $N = n+M$ and $j = M$: $\lvert\mathcal{W}(n,\sigma(\sigma(M)))\rvert = \sum_{j<\sigma(n)}\lvert\mathcal{W}(j,\sigma(M))\rvert = \sum_{j<\sigma(n)}\binom{j+M}{M} = \sum_{i<\sigma(n+M)}\binom{i}{M} = \binom{\sigma(n+M)}{\sigma(M)} = \binom{n+\sigma(M)}{\sigma(M)}$, the last equality because $\sigma(n+M) = n+\sigma(M)$. That is the claim at $\sigma(M)$.

By step 1.2, step 2.1 and induction, $\lvert\mathcal{W}(n,\sigma(M))\rvert = \binom{n+M}{M}$ for every $M$ and every $n$, which is the first display since $m = \sigma(M)$ and $M = m-1$.

The explicit bijection. For $k \in \mathcal{W}(n,\sigma(M))$ and $i < M$ put $s_i := \big(\sum_{j<\sigma(i)}k_j\big) + i$ and $S(k) := \{\, s_i : i < M \,\}$. The list is strictly increasing, since $s_{\sigma(i)} = \big(\sum_{j<\sigma(i)}k_j + k_{\sigma(i)}\big) + \sigma(i) = s_i + k_{\sigma(i)} + 1$; and $s_i < n+M$, since $\sum_{j<\sigma(i)}k_j \le \sum_{j<\sigma(M)}k_j = n$ by [L2] and $i \le M-1$. So $S(k)$ is a subset of $n+M$ with exactly $M$ elements, and $S$ maps $\mathcal{W}(n,\sigma(M))$ into $[\,n+M\,]^{M}$. It is injective: a strictly increasing list enumerating a finite subset of $\mathbb{N}$ is determined by that subset, since its first entry is the least element and each later entry is the least element strictly above the previous one ([L9] and induction), so $S(k) = S(\tilde k)$ forces $s_i = \tilde s_i$ for all $i < M$; then $k_0 = s_0$ and $k_{\sigma(i)} = s_{\sigma(i)} - s_i - 1$ recover $k$ on $M$, and $k_M = n - \sum_{j<M}k_j$ recovers the last part. Since both sets have $\binom{n+M}{M}$ elements by step 3.1 and [L3], the image of $S$ is a subset of $[\,n+M\,]^{M}$ of the same cardinality, hence all of it by [L6]. So $S$ is a bijection.

The count of compositions, for $m = \sigma(M) \ge 1$ and $n \ge 1$. If $m \le n$, the map $k \mapsto k'$ with $k'_i := k_i - 1$ sends $\mathcal{C}(n,m)$ into $\mathcal{W}(n-m,m)$: each $k_i \ge 1$, so $k_i = k'_i + 1$, and $\sum_{i<m}k_i = \sum_{i<m}k'_i + \sum_{i<m}1 = \sum_{i<m}k'_i + m$ by additivity and the constant clause, whence $\sum_{i<m}k'_i = n-m$. Its two-sided inverse adds $1$ to every part. So $\lvert\mathcal{C}(n,m)\rvert = \lvert\mathcal{W}(n-m,m)\rvert = \binom{(n-m)+M}{M}$ by step 3.1, and $(n-m)+M = n-1$ because $(n-m)+m = n$ and $M = m-1$ with $m \ge 1$. If instead $m > n$, then every $k \in \mathcal{C}(n,m)$ would satisfy $n = \sum_{i<m}k_i \ge \sum_{i<m}1 = m$ by monotonicity, which is false; so $\mathcal{C}(n,m) = \varnothing$, and $\binom{n-1}{m-1} = 0$ as well, since $m > n \ge 1$ gives $m-1 > n-1$. In both cases $\lvert\mathcal{C}(n,m)\rvert = \binom{n-1}{m-1}$.

The count of weak compositions is step 3.1, the bijection realising it is step 4.1, and the count of compositions is step 4.2.