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.

Given a linear Diophantine equation, how can I count the number of positive solutions?

More specifically, I am interested in the number of positive solutions for the following linear Diophantine equation:

$3w + 2x + y + z = 47$

Update: I am only interested in non-zero solutions.

share|improve this question
1  
Regarding your update, as hinted at by chandok, you can replace your equation with an equivalent equation $3a+2b+c+d=40$ by setting $a=w-1$, $b=x-1$, $c=y-1$, $d=z-1$. Then every non-negative integer solution of this equation corresponds to a positive integer solution of the original equation. –  András Salamon Apr 3 '11 at 17:18
    
Thanks for the clarification. It wasn't clear to me what he meant by "shifting the variables". –  davitenio Apr 3 '11 at 20:29

2 Answers 2

up vote 5 down vote accepted

The number of solutions of (some linear expression) = n, is always something that looks like a polynomial (see http://en.wikipedia.org/wiki/Ehrhart_polynomial) You can compute them recursively or compute enough small values for it so that it determines the polynomial.

Let me do the recursive method here. First, it's simpler for me to allow $0$ as a value, I am not sure if you allow them, if you don't, then by shifting the variables, it is the same as looking a sum that gives $40$ instead of $47$, allowing things like $x=0$ and then adding $1$ to everyone.

For any $n \ge 0$, the number of solutions of $z=n$ is $P_1(n) = 1$.

For any $n \ge 0$, the number of solutions of $y+z=n$ is $P_2(n) = P_1(n) + P_1(n-1) + \ldots P_1(0) = (n+1)*1 = n+1$.

For any $n \ge 0$, the number of solutions of $2x+y+z=n$ is $P_3(n) = P_2(n) + P_2(n-2) + \ldots $. It starts to get tricky : I have to separate two cases accorging to the parity of $n$ : $$ P_3(2m) = (2m+1) + (2m-1) + \ldots + (1) = (m+1)^2 = (n^2+4n+4)/4 $$ $$ P_3(2m+1) = (2m+2) + (2m) + \ldots + (2) = (m+1)(m+2) = (n^2+4n+3)/4$$

For the last step, you have to split into 6 cases so I will only do the one you need : $$P_4(6m+4) = P_3(6m+4) + P_3(6m+1) + \ldots + P_3(1) = \Sigma_{k=0}^m P_3(6k+1) + P_3(6k+4) $$ $$ = \Sigma_{k=0}^m ((6k+1)^2 + 4(6k+1)+3 + (6k+4)^2 + 4(6k+4)+4)/4 = \Sigma_{k=0}^m 18k^2+27k+11 $$ $$ = 3m(m+1)(2m+1)+27m(m+1)/2+11(m+1) = (12m^3 + 45m^2 + 55m +22)/2 $$

So $P_4(40) = P_4(6*6+4) = 2282$.

share|improve this answer
    
Sorry, you lost me at the last step. Why are there 6 cases and what are these 6 cases? –  davitenio Apr 3 '11 at 20:31
    
We have 3 tiny variations according to n mod 3, which are wether the sum starts at P3(0), P3(1), or P3(2), because whenever we add 1 to w, we decrease n by 3 because of the coefficient 3 in front of w. But we also have to carry the 2 tiny variations from earlier. According to n mod 2, we start with an "even" case or an "odd" case for P3, and this will make a tiny difference somewhere. So what happens in the small details depends on n mod 6. –  mercio Apr 3 '11 at 20:45
    
Ok, thanks. So I suppose that the 6 cases would be to split $n$ into $6m$, $6m + 1$, $6m + 2$, $6m + 3$, $6m + 4$, and $6m + 5$. Correct? –  davitenio Apr 4 '11 at 5:27

Let $\mathbb{N} := \{0, 1, 2, ...\}$ be the set of natural numbers (i.e nonnegative integers). Given $N\in\mathbb{N}\backslash\{0\}$, $n\in\mathbb{N}$, and $(a_1, a_2, ..., a_N) \in\mathbb{N}^N$, let $P_{N}(a_1, a_2, ..., a_N, n)$ be the number of solutions to the linear Diophatine equation \begin{equation} \sum_{k=1}^N{a_kx_k} = n, \space x\in\mathbb{N}^N \end{equation}

Note that $P_{N}$ defines a function from $\mathbb{N}^{N+1}$ to $\mathbb{N}\backslash\{0\}$.

Then, the following recursive formula is easily established by induction on $N$ (for $N>2$, fix $x_1\in[0, n/a_1]\cap \mathbb{N}$, and solve for $(x_2$, ..., $x_N)\in\mathbb{N}^{N-1}$) \begin{equation} \begin{split} P_1(a_1, n) = 1, \text{if $n$ is a multiple of $a_1$, $0$ otherwise;}\\ P_N(a_1, a_2, ..., a_N, n) = \sum_{x_1\in [0, n/a_1]\cap \mathbb{N}}P_{N-1}(a_2, ..., a_N, n - x_1a_1)\text{, if $N>1$} \end{split} \end{equation}

The following (naive) code snippet in Python will solve any instance of the problem in finite time.

def diophantine_count(a, n):
"""Computes the number of nonnegative solutions (x) of the linear
Diophantine equation
    a[0] * x[0] + ... a[N-1] * x[N-1] = n

Theory: For natural numbers a[0], a[2], ..., a[N - 1], n, and j,
let p(a, n, j) be the number of nonnegative solutions.

Then one has:
    p(a, m, j) = sum p(a[1:], m - k * a[0], j - 1), where the sum is taken
    over 0 <= k <= floor(m // a[0])

Examples
--------
>>> diophantine_count([3, 2, 1, 1], 47)
3572
>>> diophantine_count([3, 2, 1, 1], 40)
2282
"""

def p(a, m, j):
    if j == 0:
        return int(m == 0)
    else:
        return sum([p(a[1:], m - k * a[0], j - 1)
                    for k in xrange(1 + m // a[0])])

return p(a, n, len(a))

Now that we have the hammer, let's find the nails...

OK, returning to your problem, we have $P_3(3, 2, 1, 1, 47) = 3572$.

N.B: $P_3(3, 2, 1, 1, 40) = 2282$, in accordance with mercio's brute-force computation :)

Cheers,

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.