Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.