Number of compositions

Question

Could anyone help me? I have an exercise.

The number of all m-parts compositions of the number $n$ is denoted by $c (m, n)$

Prove that

$c(m,n) = \binom{n-1}{m-1}$

Please explain step by step

Thanks for all the help

Answer 1

A $k$-composition of $n$ is a collection of natural numbers $x_1,\ldots,x_k>0$ such that $n=x_1+\ldots+x_k$. Let $p(n,k)$ denote the number of $k$-compositions of $n$. Then $p(n,1)=1=p(n,n)$ and for each $k$ with $1<k<n$, $p(n,k)={n-1\choose k-1}$.

To prove the latter, take a $k$-composition of $n$, $n=x_1+\ldots+x_k$, and define the numbers $y_1,\ldots,y_{k-1}$ where $$y_i = x_1+\ldots+x_i,\; 1\leq i<k.$$ We have $$1\leq x_1 < x_1+x_2<\ldots <x_1+x_2+\ldots+x_{k-1} = n-x_k<n$$ and so $$1\leq y_1 < y_2 < \ldots < y_{k-1}<n.$$ Note that $\{y_1,y_2,\ldots,y_{k-1}\}$ is a $k-1$-subset of $\{1,\ldots,n-1\}$. The number of such subsets is ${n-1\choose k-1}$. Moreover, the above assignment $x\mapsto y$ is a bijection between the $k$-compositions of $n$ and the $k-1$-element subsets of $\{1,\ldots,n-1\}$. Finite sets $X$ and $Y$ for which there is a bijection $X\rightarrow Y$ have the same cardinality. Done.

Here is an example: $n=5$ and $k=3$. The 3-compositions of 5 are $1+1+3$, $1+3+1$, $3+1+1$, $1+2+2$, $2+1+2$, and $2+2+1$.

By the above construction, the 2-subsets of $\{1,2,3,4\}$ are (in turn) $\{1,2\}$, $\{1,4\}$, $\{3,4\}$, $\{1,3\}$, $\{2,3\}$, and $\{2,4\}$.

Answer 2

Make a line of $n$ ones. There are $n-1$ spaces between these ones. Choose $m-1$ of these spaces, and put a divider in the chosen spaces. This divides the line into $m$ contiguous blocks, which defines a composition of $n$ where the $i^{th}$ summand in the composition is the number of ones is the $i^{th}$ block. Every composition is chosen exactly once in this way. The number of ways to choose where the dividers go is $\binom{n-1}{m-1}$.