Enumerate solution of $x_{1} + x_{2} + ... + x_{r} = n$ I'm doing a problem about matrices and meet the difficulies related to combinatorics which I can't find the solution. I'm very grateful if anyone can help me solve this:

How many positive integer solutions ($x_{1}, x_{2}, ..., x_{r}$) are there to this equation: $$x_{1} + x_{2} + ... + x_{r} = n?$$ Here $n$ is a positive integer, and there are two cases for $r$:

*

*$r$ is a given number;

*$r$ is not fixed.


Thanks
 A: I take it you are looking for positive solutions. For fixed $r$, the problem is extensively discussed in Wikipedia under the name Stars and Bars. It will turn out that the answer is $\binom{n-1}{r-1}$.   The idea is that you have $n$ identical candies, to distribute among $r$ kids. Line up the candies in a row, with a little space between each candy. There are $n-1$ inter-candy gaps. Choose $r-1$ of these gaps to put a separator into. Kid $1$ gets all the candies ($x_1$) up to the first separator, Kid $2$ gets all the candies ($x_2$) between the first separator and the second, and so on.  
If $r$ is not fixed, line up $n$ candies as before.  These candies determine $n-1$ gaps. Choose any subset of this set of gaps to put a separator into. There are $2^{n-1}$ ways to do this. Each determines an ordered decomposition of $n$ as a sum.
Remark: We can solve the first problem for non-negative integer solutions as follows. Start from $n+r$ candies, and give these to $r$ kids, at least one to each. Then take away a candy from each kid. So you will have distributed $n$ candies, with some kids possibly getting none. The previous analysis shows there are $\binom{n+r-1}{r-1}$ ways to do it. 
The second problem does not make sense if we drop the "positive" part, since we can pad positive solution with arbitrary numbers of $0$'s.
A: There is a nice way to find the number of partitions (this is the name) of a number $n$. Consider $n$ balls and $r-1$ bars. Any sequence of balls and bars represents a partition. For example 1+5+3+2 = 10 can be represented as:
o | o o o o o | o o o | o o

You can easily count the number of such sequences, they are $\binom{n+r-1}{r-1}$. 
This way you also admin to have $0$ in the sum. To avoid this you should count the partitions of $n-r$ and then add $1$ to every addend.
