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
    2,029
    Thanks
    804

    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?
    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
    661
    Thanks
    302

    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
    Thanks from SlipEternal
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,029
    Thanks
    804

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

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,029
    Thanks
    804

    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.
    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
    2,029
    Thanks
    804

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

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,029
    Thanks
    804

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