# Thread: Number of Integer solutions to certain Diophantine Equations

1. ## Number of Integer solutions to certain Diophantine Equations

My question: Is there a known closed form for the following:

Let $m,n \in \mathbb{Z}^+$. Let $(a_0, a_1, \cdots, a_m) \in \mathbb{Z}^{m+1}$ be a tuple of positive integers such that $\displaystyle \sum_{i=0}^m a_i = n$. Let $k \in \mathbb{Z}$ such that $0 \le k \le n$.
Given the equation $b_0+b_1+\cdots + b_m = k$ and the conditions $\forall i, 0 \le b_i \le a_i$. If I wanted to calculate the number of integer solutions to this Diophantine equation, I would start with the following:

$\displaystyle \binom{m+k}{m}$

This is the number of integer solutions with $0\le b_i$, but the variables have no upper limit. So, I have to subtract the number of cases where the upper limit(s) is/are violated. I can calculate this using the inclusion/exclusion principle. First, I calculate the number of ways that a single variable's upper limit is violated:

$\displaystyle \sum_{i = 0}^m \left\{\begin{matrix}\binom{m+k-a_i}{m}, & \text{if } a_i \le k \\ 0, & \text{if } a_i > k\end{matrix}\right.$

I subtract this sum from the original binomial. Then, I add back when exactly two upper limits are violated, then subtract when exactly three upper limits are violated, etc.

If $[m] = \{0,1,\ldots,m\}$, then we can write this as:

$\displaystyle \sum_{A \subseteq [m]} \left\{\begin{matrix}(-1)^{|A|}\begin{pmatrix}m+k- \displaystyle \sum_{i \in A} a_i \\m\end{pmatrix}, & \text{if } \displaystyle \sum_{i \in A} a_i \le k \\ 0, & \text{if } \displaystyle \sum_{i \in A} a_i > k\end{matrix}\right.$

Is this the best we can do for a closed form?

2. ## Re: Number of Integer solutions to certain Diophantine Equations

There is a bijection between the set of solutions to

$\sum _{i=0}^m b_i=k$ where $0\leq b_i\leq a_i$

and the set of solutions to

$\sum _{i=0}^m c_i=n-k$ where $c_i\geq 0$

given by

$c_i=a_i-b_i$

3. ## Re: Number of Integer solutions to certain Diophantine Equations

Very true. Solving for $b_i$, we get $b_i = a_i-c_i$. Plugging that into the inequality for $b_i$ we get $0 \le a_i-c_i$ and $a_i-c_i \le a_i$ which yields $0 \le c_i \le a_i$. Essentially, you proved that:

$\displaystyle \sum_{A \subseteq [m]} \left\{\begin{matrix}(-1)^{|A|}\begin{pmatrix}m+k- \displaystyle \sum_{i \in A} a_i \\m\end{pmatrix}, & \text{if } \displaystyle \sum_{i \in A} a_i \le k \\ 0, & \text{if } \displaystyle \sum_{i \in A} a_i > k\end{matrix}\right. = \displaystyle \sum_{A \subseteq [m]} \left\{\begin{matrix}(-1)^{|A|}\begin{pmatrix}m+n-k- \displaystyle \sum_{i \in A} a_i \\m\end{pmatrix}, & \text{if } \displaystyle \sum_{i \in A} a_i \le n-k \\ 0, & \text{if } \displaystyle \sum_{i \in A} a_i > n-k\end{matrix}\right.$

4. ## Re: Number of Integer solutions to certain Diophantine Equations

What is interesting is that this problem actually came up at work. I have a complicated problem that I need to solve. I have two algorithms. One algorithm gives me an exact result while the other gives an approximate result. I understand the computational complexity for the algorithm that gives the approximate result. I am trying to understand the complexity for the exact result. When $m,n$ are sufficiently small, the algorithm for the exact result is by far less complex. I need to figure out at what point the calculations become too cumbersome for an exact result, and the approximate result should suffice instead. So, in reality, I am looking for an easier-to-calculate closed form for the following:

$\displaystyle \sum_{k=0}^n\left( \sum_{A\subseteq [m]}\left\{ \begin{matrix}\displaystyle (-1)^{|A|}\begin{pmatrix}m+k-\displaystyle \sum_{i \in A} a_i \\ m\end{pmatrix}, & \text{if } \displaystyle \sum_{i \in A} a_i \le k \\ 0, & \text{if } \displaystyle \sum_{i \in A} a_i > k\end{matrix} \right. \right)$

Basically, I need to know the conditions on $m,n$ and the $a_i$'s so that sum is less than 5,000.

5. ## Re: Number of Integer solutions to certain Diophantine Equations

Hmm, it may take some time to see if this works, but I think that sum winds up being:

$\displaystyle \prod_{i=0}^m(a_i+1)$

If that is true, that is a really easy formula to calculate, and I may have found my solution! I may have just needed a sounding board. Thanks, Idea, for thinking about it!

6. ## Re: Number of Integer solutions to certain Diophantine Equations

Yes, this is the solution. Essentially, by adding up the number of solutions for each $0\le k\le n$, I am calculating the number of integral solutions to the following inequality:

$\displaystyle \sum_{i=0}^m b_i \le n,\qquad \forall i: 0\le b_i \le a_i$

Now, there are $a_0+1$ possible solutions for $b_0$, there are $a_1+1$ possible solutions for $b_1$, etc. Thus, the product I gave above is correct. I am closing this thread.