Let $n$ be a positive integer. Determine the number of solutions to $x_1 + \cdots + x_k \leq n$ with nonnegative integer solutions. Determine the number of solutions with positive integer solutions.
I understand why every positive solution of $x_1 + · · · + x_k = m$ corresponds to an ordered partition of $m$. However, I do not understand why the number of positive solutions of $x_1 + \cdots + x_k \leq n$ is
$$\sum_{m=k}^{n}\binom{m-1}{k-1}.$$
Similarly, I do not understand how using multisets we obtain $\binom{n+k}{k}$ for the nonnegative integer solutions. Can someone explain this?
Best Answer
Consider some positive solution of the inequality $$x_1+\cdots+x_k\le n\tag1.$$ It is necessarily a solution of an equation $$x_1+\cdots+x_k=m\tag2$$ for some $m:\ k\le m\le n$. Therefore the number of solutions of the inequality (1) is the sum of the numbers of solutions of the equations (2) for all $m:\ k\le m\le n$: $$\sum_{m=k}^n\binom{m-1}{k-1}=\binom{n}k. $$ The last expression can be obtained also in a direct though somewhat tricky way.
The same formula work for the number of non-negative solutions as well. Just replace $n(m)$ with $n(m)+k$.