Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What is the total number of solutions of the equation of the form $$x_1 + x_2 + \dots+ x_r \ge 0 $$ such that $-k_1 \le x_1 \le k_1; -k_2\le x_2 \le k_2; \dots -k_r\le x_r \le k_r$ where $K_i \ge 0 \forall i \in \{1,\dots ,r\}$ .

share|cite|improve this question
Integer solutions? – 1015 Feb 3 '13 at 22:01
$k_1, k_2 \dots, k_r$ are all integers. so yes integer solutions – Aman Deep Gautam Feb 3 '13 at 22:02
up vote 1 down vote accepted

Let $y_i=k_i-x_i$ for $i=1,\dots,r$, and let $k=k_1+\ldots+k_r$, then you’re looking for non-negative integer solutions to $y_1+\ldots+y_r\le k$ subject to the conditions $y_i\le 2k_i$ for $i=1,\dots,r$. Now add an $(r+1)$-st variable $y_0$, and count the solutions to $y_0+y_1+\ldots+y_r=k$ in non-negative integers satisfying $y_i\le 2k_i$ for $i=1,\dots,r$.

Without the upper bounds this would be a standard stars-and-bars problem, and the answer would be $\binom{k+r}r$. With the restrictions it requires an inclusion-exclusion argument that is rather messy. My answer to this problem covers the case in which the $k_i$ are all equal.

share|cite|improve this answer

Your Answer


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.