Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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).

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.