# Let $n$ be a positive integer. Determine the number of solutions to $x_1 + \cdots + x_k \leq n$ with nonnegative integer solutions.

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?

• en.wikipedia.org/wiki/Stars_and_bars_(combinatorics). Just add another non-negative variable to make it into an equality. Commented Feb 13, 2021 at 16:45
• Do you understand why the number of positive solutions to $x_1 + \cdots + x_k = m$ is $$\binom{m-1}{k-1}?$$
– user
Commented Feb 13, 2021 at 17:21
• @user Yes, the number of ordered $k$-partitions of $n$ equals $\binom{n-1}{k-1}$. Commented Feb 13, 2021 at 18:07

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$$.
• @AlexisSandoval The number of the compositions of a number $n$ into $k$ non-negative parts is equal to the number of the compositions of a number $n+k$ into $k$ positive parts. Think about subtracting 1 from the every part of the latter.