Results 1 to 6 of 6
Like Tree1Thanks
  • 1 Post By Idea

Thread: Number of Integer solutions to certain Diophantine Equations

  1. #1
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,393
    Thanks
    1351

    Number of Integer solutions to certain Diophantine Equations

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

    Let $\displaystyle m,n \in \mathbb{Z}^+$. Let $\displaystyle (a_0, a_1, \cdots, a_m) \in \mathbb{Z}^{m+1}$ be a tuple of positive integers such that $\displaystyle \displaystyle \sum_{i=0}^m a_i = n$. Let $\displaystyle k \in \mathbb{Z}$ such that $\displaystyle 0 \le k \le n$.
    Given the equation $\displaystyle b_0+b_1+\cdots + b_m = k$ and the conditions $\displaystyle \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 \displaystyle \binom{m+k}{m}$

    This is the number of integer solutions with $\displaystyle 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 \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 $\displaystyle [m] = \{0,1,\ldots,m\}$, then we can write this as:

    $\displaystyle \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?
    Last edited by SlipEternal; Apr 19th 2017 at 04:22 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    824
    Thanks
    375

    Re: Number of Integer solutions to certain Diophantine Equations

    There is a bijection between the set of solutions to

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

    and the set of solutions to

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

    given by

    $\displaystyle c_i=a_i-b_i$
    Thanks from SlipEternal
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,393
    Thanks
    1351

    Re: Number of Integer solutions to certain Diophantine Equations

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


    $\displaystyle \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.$
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,393
    Thanks
    1351

    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 $\displaystyle 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 \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 $\displaystyle m,n$ and the $\displaystyle a_i$'s so that sum is less than 5,000.
    Last edited by SlipEternal; Apr 20th 2017 at 05:42 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,393
    Thanks
    1351

    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 \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!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,393
    Thanks
    1351

    Re: Number of Integer solutions to certain Diophantine Equations

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

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

    Now, there are $\displaystyle a_0+1$ possible solutions for $\displaystyle b_0$, there are $\displaystyle a_1+1$ possible solutions for $\displaystyle b_1$, etc. Thus, the product I gave above is correct. I am closing this thread.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Find the number of integer solutions
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Nov 24th 2011, 05:52 PM
  2. Extra Solutions of a Quadratic Diophantine Equation
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 21st 2011, 05:20 AM
  3. Finding all solutions for diophantine equations
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Oct 25th 2010, 05:33 AM
  4. Solutions to this diophantine equation.
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Oct 25th 2008, 01:19 PM
  5. Finding all solutions to a Diophantine equation
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Oct 10th 2006, 01:10 PM

/mathhelpforum @mathhelpforum