# How many non-negative integer solutions to $a_1+a_2+\cdots+a_k\leq n$ with given $n$ and $k$?

I want to count the non-negative integer solutions to the following inequality: $$a_1+\cdots+a_k\leq n$$ where $$n$$ and $$k$$ are given nonnegative integers.

I tried using stars and bars for each integer less than $$n$$ ($$n-1,n-2,n-3\dots 3,2,1$$), but that didn't help since I only got a sigma.

Btw the answer cannot involve a sigma or a ...

• Do you mean $a_1+a_2+...$ ? And if you do mean that then the solution highly depends on what these values are. A generalized answer wouldn't be possible, but one could find an upper bound for certain $n$ and $k$ – WaveX Feb 3 at 16:16
• Are $a_1, a_2,\dots,a_k$ positive integers? non-negative integers? Or something? – Bernard Feb 3 at 16:18
• yeah nonegative – Toylatte Feb 3 at 16:22
• For $n = 6$ and $k = 2$, are $3 + 2$ and $2 + 3$ distinct solutions? – John Hughes Feb 3 at 16:35
• the question doesnt specify but yes im pretty sure – Toylatte Feb 3 at 16:36

You precise in a comment that the $$a_i$$ are non-negative integers.
In that case the number of solutions to the inequality corresponds to the number of weak compositions of $$m$$ into exactly $$k$$ parts, with $$0 \le m \le n$$.
Now, the number of weak compositions of $$m$$ into $$k$$ parts is $$\binom{m+k-1}{m}$$ and the sum on $$m$$ gives \eqalign{ & N(n) = \sum\limits_{m = 0}^n {\binom{m+k-1}{m}} = \cr & = \sum\limits_{\left( {0\, \le } \right)\,m\,\left( { \le \,n} \right)} {\binom{n-m}{n-m}\binom{m+k-1}{m}} = \binom{n+k}{n} \cr}
- the first step is to replace the summation bounds with the binomial $$\binom{n-m}{n-m}$$ that contains the upper bound implicitely, while the lower bound is implicit in the original binomial;
- the second step is to apply the "double convolution" , which in general reads \eqalign{ & \sum\limits_{\left( { - m\, \le } \right)\,k\,\left( { \le \,n} \right)\,} {\binom{r+k}{m+k} \binom{s-k}{n-k}} = \sum\limits_{\left( { - m\, \le } \right)\,k\,\left( { \le \,n} \right)\,} {\left( { - 1} \right)^{m + k} \binom{m-r-1}{m+k} \left( { - 1} \right)^{n - k} \binom{n-s-1}{n-k} } = \cr & = \left( { - 1} \right)^{m + n} \sum\limits_{\left( { - m\, \le } \right)\,k\,\left( { \le \,n} \right)\,} {\binom{m-r-1}{m+k} \binom{n-s-1}{n-k}} = \left( { - 1} \right)^{m + n} \binom{m+n-r-s-2}{m+n} \cr & = \binom{r+s+1}{m+n} \quad \left| \matrix{ \;r,s \in \mathbb C \hfill \cr \,m,n \in \mathbb Z \hfill \cr} \right. \cr} applying the "upper negation" and the (standard) "convolution".