# An alternative approach to finding the number of integer solutions of $x_1+\cdots+x_k=n,\ x_i>0.$

To find the number of integer solutions of the equation $$x_1+\ldots+x_k=n,\ x_1,\ldots,x_k>0,$$

we can draw $n$ dots in a row obtaining $n-1$ spaces between each two consecutive dots. Then we can count the number of ways in which we can insert $k-1$ indistinguishable vertical lines into these spaces in such a way that no two lines share a space. We can notice that it can be done in exactly as many ways as there are $k-1$-element subsets of an $n-1$-element set, that is $n-1\choose k-1$.

But it is a known identity that $${n-1\choose k-1}={k\over n}{n\choose k}.$$ This makes me think that there should be a solution to this problem in which we first choose $k$ dots from the $n$ dots and then do something equivalent to the multiplication by $k\over n$ to obtain the right number. But I can't see this solution. Could you help me?

-

Imagine the $n$ dots in a row and select $k$ of them. A selection is valid if the first dot was selected and exactly $\frac{k}{n}$ of the $\binom{n}{k}$ selections are valid. We have that the positive integer solutions of the equation correspond exactly to the valid selections - the value of a variable $x_i$ is the number of dots from the $i$-th selection to the $i+1$-st (including the $i$-th selection, but not the $i+1$-st).

-

You could think of it as follows, though it's not that natural an interpretation.

Start out with the not quite correct counting plan that each way to choose (or circle) $k$ of the $n$ dots will give a solution: the $i$-th circled dot is the start of $x_i$. For $n=5$ and $k=3$, circling dots 1, 3, and 4 makes $\underbrace{\odot\quad\cdot\quad}_{x_1=2}\underbrace{\odot\quad}_{x_2=1}\underbrace{\odot\quad\cdot\quad}_{x_3=2}$, and circling dots 1, 2, and 5 makes $\underbrace{\odot\quad}_{x_1=1}\underbrace{\odot\quad\cdot\quad\cdot\quad}_{x_2=3}\underbrace{\odot\quad}_{x_3=1}$ .

Soon you would realize this is wrong, because $x_1$ has to begin with the first dot. Of the $n\choose k$ ways to circle $k$ dots, only those choices where the first dot is circled will yield a solution. You're circling $k \over n$ of the dots, so $k\over n$ of your choices will have the first dot circled.

If you really thought it out this way and realized your mistake, it's a stretch to think you'd just throw in the factor of $k\over n$. Instead, you'd likely realize that the number of solutions is the number of ways to circle the first dot and $k-1$ of the remaining $n-1$ dots, or $n-1\choose k-1$.

-