1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – WaveX Feb 3 at 16:16
  • 1
    $\begingroup$ Are $a_1, a_2,\dots,a_k$ positive integers? non-negative integers? Or something? $\endgroup$ – Bernard Feb 3 at 16:18
  • $\begingroup$ yeah nonegative $\endgroup$ – Toylatte Feb 3 at 16:22
  • $\begingroup$ For $n = 6$ and $k = 2$, are $3 + 2$ and $2 + 3$ distinct solutions? $\endgroup$ – John Hughes Feb 3 at 16:35
  • $\begingroup$ the question doesnt specify but yes im pretty sure $\endgroup$ – Toylatte Feb 3 at 16:36
0
$\begingroup$

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

where:
- 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".

$\endgroup$
  • $\begingroup$ @G Cab could you elaborate on the double convolution formula and how you got the last two equations? $\endgroup$ – Toylatte Feb 3 at 21:48
  • $\begingroup$ @Toylatte: I expanded the explanation of the passages: let me know if you still have doubts. $\endgroup$ – G Cab Feb 3 at 23:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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