0
$\begingroup$

We want to find the total number of non negative integral solutions with the additional constraint that $$a + b \geq c + d$$

The value of $n = \mathcal{O}(10^6)$ and $a, b, c, d, e \geq 0$

I could use generating functions but I don't know how to solve with keeping the constraint satisfied? One approach that I thought of was first finding the total number of solutions to the equation $5a + 6b + 9c + 2d + e = n$ and then subtracting the ones that don't follow the constraint i.e. $a + b < c + d$. This means that $a + b + k = c + d$ where $k \geq 0$ but I don't know how I can use the slack variable $k$ to create another equation which satisfies all the constraints.

$\endgroup$
4
  • $\begingroup$ Is the value of $n $ specified ?? Otherwise by setting $c=d = 0 $ and changing the values of $a$ and $b$ , we can get infinite solutions. $\endgroup$ Oct 20, 2019 at 12:09
  • $\begingroup$ Yes. The value of $n = \mathcal{O(10^6)}$ and we have to find non-negative integral solutions which means $a, b, c, d, e \geq 0$. $\endgroup$ Oct 20, 2019 at 12:18
  • 1
    $\begingroup$ If I am not mistaken, for a given $n$, there are $$a_n=\sum_{k=0}^{\left\lfloor\frac{ n}5\right\rfloor}\sum_{\substack{{m\equiv n-5k\pmod{7}}\\ {0\leq m\leq n-5k}}}\sum_{c=0}^{\left\lfloor\frac{n-5k-m}{14}\right\rfloor}\Biggl(\min\left\{m,\frac{n+2k-m}{7}-c\right\}+1\Biggr)$$ solutions. I am not sure how to make this simpler. For each $(k,m,c)$, we get $$(a,b,c,d,e)=\left(\frac{n+2k-m}{7}-c-b,b,c,\frac{n-5k-m}{7}-2c,m-b\right),$$ where $$0\leq b \leq \min\left\{\frac{n+2k-m}{7}-c,m\right\}.$$ On the other hand, for each $(a,b,c,d,e)$, $$(k,m,c)=(a+b-c-d,b+e,c).$$ $\endgroup$ Oct 20, 2019 at 13:33
  • $\begingroup$ Is there a way to convert the equation to an equivalent equations satisfying the given constraints? $\endgroup$ Oct 20, 2019 at 14:05

0

You must log in to answer this question.

Browse other questions tagged .