# Number of compositions [closed]

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

## closed as off-topic by Saad, Riccardo.Alestra, Wouter, José Carlos Santos, StrantsMar 21 at 17:50

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Saad, Riccardo.Alestra, Wouter, José Carlos Santos, Strants
If this question can be reworded to fit the rules in the help center, please edit the question.

## 2 Answers

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, $$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 We have $$1\leq x_1 < x_1+x_2<\ldots and so $$1\leq y_1 < y_2 < \ldots < y_{k-1} 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\}$$.

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}$$.